場合の数を数える
（準備中）
1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか
という問題を解くプログラム。
これは京都大学2007年の理系数学で出題された問題です。
この問題の数学的解法は、「場合の数を数える～入試問題」で説明してあります。
そこの解法2として漸化式に持ち込む解法を試しています。
その漸化式をプログラムで使えば簡単に登り方が何通りあるかを求めるプログラムは作れるわけですが、
それでは味気ない（わざわざコンピュータにプログラム組んでやらせる意味がない）ので、問題をもうひとひねりして、
その登り方のパターンを全て列挙するプログラムを作れ、という問題にしたいと思います。
つまり２段の場合は、1-1, 2
３段の場合は、1-1-1, 1-2, 2-1 というパターンを全て書き出すプログラムになります。
また、15段だけを求めるのもつまらないので、もっと汎用的に、変数kをインプットし、k段について求める
プログラムとします。
最終段をK段としたとき、
以下のような動作をするstepという関数を考えてみる。この関数stepは次の段の処理をするために再帰的に呼び出す。
① K段目に達していた場合は、そのままreturn
② k-1段目の場合は１段登りで登る。
③ k-2段目以下にいる場合は、(A)今の段に１段登りで登ってきた場合、(A)-1
１段登りで登る、(A)-2 ２段登りで登る
(B)今の段に２段登りで登ってきた場合、１段登りで登る
main関数
最初の登り方として、１段登りと２段登りがあるので、この２パターンを初期値としてstep関数を呼び出す。
（最初の登り方もstep関数の中で処理する作り方もあるとは思うが、step関数が複雑になるので、今回は
main関数から呼び出すときの初期値を２パターンに分けて、step関数はシンプルになるようにした）
ということで作ってみたのがstep.c
#include <stdio.h>
void step(int,int,int);
int count,k;
main()
{
count=0;
scanf("%d",&k);
step(1,1,1);
step(1,2,2);
printf("count:%d\n",count);}
void step(n,s,sum)
int n,s,sum;
{if (sum ==k) {
count=count+1;
printf("(%d)%d:\n",n,s);}
if (sum ==k-1) {
printf("(%d)%d:",n,s);
step(n+1,1,sum+1);}
if (sum < k-1) {
if(s==1) {
printf("(%d)%d:",n,s);
step(n+1,1,sum+1);
step(n+1,2,sum+2);}
else {
printf("(%d)%d:",n,s);
step(n+1,1,sum+1);}
}
return; }
step関数
step関数には引数として、n,s,sumの３つを渡してコールすることとした。
nは何回めの登りか
sは１段登りか⇒1、２段登りか⇒2
sumは到達する階段の段数
各処理の中で、今行った処理をアウトプットするようにした。具体的にはprintfでn,sを出力。
目標のk段目に到達し他た時は、変数countを1増加して、登り方が何通りあるかを計算する。
k-1段の時は、次の登り方として1段登りを行うという処理をする。
すなわちstep(n+1,1,sum+1)としてstep関数を再帰的にコールする。
k-2段以下の場合は、今登ってきたのが１段登りのケースと２段登りのケースに分け、
１段登りの時は、まず次の登り方として１段登りの処理を行う。つまりstep(n+1,1,sum+1)としてstep関数を再帰的にコールする。
その処理が終了したら、２段登りの処理を行う。すなわち、step(n+1,2,sum+2)としてstep関数を再帰的コールする。
２段登りだった場合は、次の登り方として１段登りの処理を行う。つまりstep(n+1,1,sum+1)としてstep関数を再帰的にコールする。
実行してみたところ。
15段で試しています。
c:\bcc55\Bin>step
15
(1)1:(2)1:(3)1:(4)1:(5)1:(6)1:(7)1:(8)1:(9)1:(10)1:(11)1:(12)1:(13)1:(14)1:(15)1
:
(14)2:
(13)2:(14)1:
(12)2:(13)1:(14)1:
(11)2:(12)1:(13)1:(14)1:
(13)2:
(10)2:(11)1:(12)1:(13)1:(14)1:
(13)2:
(12)2:(13)1:
(9)2:(10)1:(11)1:(12)1:(13)1:(14)1:
(13)2:
(12)2:(13)1:
(11)2:(12)1:(13)1:
(8)2:(9)1:(10)1:(11)1:(12)1:(13)1:(14)1:
・・途中略・・
(5)2:(6)1:(7)1:(8)1:(9)1:(10)1:(11)1:(12)1:
(11)2:
(10)2:(11)1:
(9)2:(10)1:(11)1:
(8)2:(9)1:(10)1:(11)1:
(10)2:
(7)2:(8)1:(9)1:(10)1:(11)1:
(10)2:
(9)2:(10)1:
count:277