C++で1段・2段・3段のステップを使ってn番目の階段に到達する方法の数を数える

階段の総段数 n が与えられ、人は一度に1段、2段、または3段を飛び越えて次の階に進むことができるとします。このとき、そのような移動によって次の階に到達する方法が何通りあるかを求めるのが目的です。

この問題は再帰的な手法で解くことができます。i 番目の段に到達するためには、(i−1) 番目の段から1段跳ぶか、(i−2) 番目の段から2段跳ぶか、(i−3) 番目の段から3段跳ぶかのいずれかしかない、という点に着目します。

具体例で確認してみましょう。

入力例と出力例

例1

入力

N=3 段

出力

1段・2段・3段のステップを使ってn番目の階段に到達する方法の数：4

解説

合計3段あります
スタートから3段跳ぶ：3
1段目から2段跳ぶ：1+2
2段目から1段跳ぶ：2+1
毎回1段ずつ：1+1+1

例2

入力

N=6 段

出力

1段・2段・3段のステップを使ってn番目の階段に到達する方法の数：24

解説

合計6段あります
方法の例：1+1+1+1+1+1、2+1+1+1+1、3+1+1+1、3+1+2、3+2+1、3+3 など。

プログラムで使用するアプローチ

• 整数型の変数 steps を階段の総段数として受け取ります。
• 関数 stairs_step(int steps) は総段数を引数として受け取り、ジャンプを組み合わせて次の階に到達する方法の数を返します。
• 方法の数を格納するため、初期値 count を 0 として用意します。
• 段数が 0 の場合は 1 を返します（何もしないという1通りの到達方法があるとみなす）。
• 段数が 1 の場合は方法は1通りだけです。
• 段数が 2 の場合は2通りです（1+1 または 2）。
• それ以外の場合は、stairs_step(step−3) + stairs_step(step−2) + stairs_step(step−1) として再帰的に計算します。

再帰的な手法による実装

コード例

#include <iostream>
using namespace std;
int stairs_step(int steps){
    if(steps == 0){
        return 1;
    }
    else if(steps == 1){
        return 1;
    }
    else if (steps == 2){
        return 2;
    }
    else{
        return stairs_step(steps - 3) + stairs_step(steps - 2) + stairs_step(steps - 1);
    }
}
int main(){
    int steps = 5;
    cout<<"1段・2段・3段のステップを使ってn番目の階段に到達する方法の数："<<stairs_step(steps);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

1段・2段・3段のステップを使ってn番目の階段に到達する方法の数：13

補足：計算量について

この再帰的な実装はシンプルで理解しやすい一方、同じ値を何度も計算するため指数関数的な時間計算量 O(3ⁿ) となります。段数が大きくなると処理が遅くなるため、実際の開発ではメモ化（動的計画法）を組み合わせて O(n) まで高速化するのが一般的です。各段への到達方法の数を配列に保存し、小さい問題から順に埋めていくことで、効率的に答えを求められます。