場合の数を数える

場合の数を数えるプログラム
（準備中）

1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか
という問題を解くプログラム。
これは京都大学2007年の理系数学で出題された問題です。

この問題の数学的解法は、「場合の数を数える～入試問題」で説明してあります。
そこの解法2として漸化式に持ち込む解法を試しています。

最初に、この漸化式をそのままプログラムに落としたコードを掲載しておきます。
n段目への登り方がA_n通りとすると、A_n=A_n-1+A_n-3 という漸化式になります。
これを、a(n)=a(n-1)+a(n-3)のように素直にコードにしてもいいのですが、ちょっとだけ動的計画法チックな
コードにしてみました。
n段目に登る登り方として、dp[n][s] という配列を用意します。
n　階段の段数
s　0の場合は1段登りで登る、1の場合は2段登りで登る

1段登りでn段目に登る場合は、dp[n][0]=dp[n-1][0]+dp[n-1][1] で計算できます。漸化式のa(n-1)に該当する部分になります。
2段登りでn段目に登る場合は、dp[n][1]=dp[n-2][0] になります。漸化式のa(n-3)に該当する部分です。

2段登りは連続できないという条件が少々理解を難しくしています。「場合の数を数える～入試問題」で漸化式の説明してあります
ので、そちらをご参照下さい。

<step_dp.c>

#include <stdio.h>

int main(void){
int dp[30][2]={0};
int i,n;
        
scanf("%d",&n);
dp[0][0]=1;

for(i=1;i<=n;i++){

    dp[i][0]=dp[i-1][0]+dp[i-1][1];

    if(i>=2)
        {  dp[i][1]=dp[i-2][0];}
}

printf("%d\n",dp[n][0]+dp[n][1]);
}

実行したところ。15段の場合と20段の場合を求めてみた。

c:\bcc55\Bin>step_dp
15
277

c:\bcc55\Bin>step_dp
20
1873

上記のように漸化式をプログラムで使えば簡単に登り方が何通りあるかを求めるプログラムは作れるわけですが、
それでは味気ない（わざわざコンピュータにプログラム組んでやらせる意味がない）ので、問題をもうひとひねりして、
その登り方のパターンを全て列挙するプログラムを作れ、という問題にしたいと思います。つまり深さ優先探索のプログラム。

イメージは２段の場合は、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

ＴｏｐＰａｇｅ