|
|
問題
7段の階段を登るとき、「1段ずつ登る」、「1段とばしで登る」の2つの登り方があります。
1番下から1番上まで登るとき、「1段ずつ登る」「1段とばしで登る」を混ぜて登ってもよいとします。
このとき、次の問いに答えなさい。
(1) 登り方は何通りありますか。
(2) 5段目に必ず止まる登り方は何通りありますか。
（2001年 日大豊山中）
その１ 漸化式
LET N=7 !段数 ※N≧1
LET A0=1
LET A1=1
FOR i=2 TO N
LET A2=A1+A0
LET A0=A1 !次へ
LET A1=A2
NEXT i
PRINT A1;"通り"
END
その２ 並べる
DEF ReptCOMB(N,R)=COMB(N+R-1,R) !重複組合せ
LET N=7 !段数
LET C=0 !場合の数
LET C1=0
LET C2=0
FOR Y=0 TO INT(N/2) !不定方程式を解く
LET X=N-2*Y
LET C=C+ReptCOMB(X+1,Y)
LET C1=C1+FACT(X+Y)/(FACT(X)*FACT(Y)) !別解
LET C2=C2+COMB(X+Y,Y) !別解
NEXT Y
PRINT C;"通り"
PRINT C1;"通り"
PRINT C2;"通り"
END
問題
1歩で1段または2段のいずれかで階段を昇るとき、
1歩で2段昇ることは連続しないものとすると、15段の階段を昇る昇り方は何通りあるか。
（2007年 京都大学前期数学［理系1問2］）
その１ 漸化式
LET N=15 !段数 ※N≧2
LET A0=1
LET A1=1
LET A2=2
FOR i=3 TO N
LET A3=A2+A0
LET A0=A1 !次へ
LET A1=A2
LET A2=A3
NEXT i
PRINT A2;"通り"
END
その２ 並べる
LET N=15 !段数
LET C=0 !場合の数
FOR Y=0 TO INT(N/2) !不定方程式を解く
LET X=N-2*Y
LET C=C+COMB(X+1,Y)
NEXT Y
PRINT C;"通り"
END
その３ 樹形図で考える
LET N=15 !段数
DIM A(0 TO N) !上り方
LET A(0)=0 !※番兵
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(1,0, N,A)
END
EXTERNAL SUB try(P,S, N,A()) !バックトラック法で検索する
FOR i=1 TO 2
IF i=2 AND i=A(P-1) THEN !1段とばしは連続しない
ELSE
LET A(P)=i !p歩目
LET T=S+i
IF T=N THEN !目的の段数へ到達したなら
LET C=C+1
PRINT "No."; C
FOR K=1 TO P !結果を表示する
PRINT A(K);
NEXT K
PRINT
ELSEIF T<N THEN !次へ
CALL try(P+1,T, N,A)
END IF
END IF
NEXT i
END SUB
|
|