デラノイ数とは？C++でデラノイ数を求めるプログラムの作成方法

デラノイ数（Delannoy Number）とは

デラノイ数 D とは、長方形のグリッド上において、南西の角 (0,0) から北東の角 (a,b) まで移動する経路の総数を表す数です。ただし、移動に使用できるのは以下の3種類のステップのみとします。

• 東方向への移動（→）
• 北東方向への移動（↗）
• 北方向への移動（↑）

この定義から、デラノイ数は次の漸化式で表すことができます。

D(a,b) = D(a-1, b) + D(a, b-1) + D(a-1, b-1)　※ただし D(0,0) = 1

例えば、デラノイ数 D(3,3) の値は 63 になります。

デラノイ数を求めるアルゴリズム

デラノイ数を計算する手順は以下の通りです。

1. 2つの座標 (a, b) を入力として受け取ります。
2. 座標 a と b を引数にとる整数型関数 generateDelannoy(int a, int b) を定義します。
3. ベースケースとして、座標 a または b のどちらかが 0 の場合には 1 を返します。
4. それ以外の場合は、漸化式 D(a-1,b) + D(a,b-1) + D(a-1,b-1) を用いて再帰的にデラノイ数を生成し、その結果を返します。

C++による実装例

#include<iostream>
using namespace std;

int generateDelannoy(int a, int b){
    int d = 1;
    if((a == 0) || (b == 0)){
        d = 1;
    } else {
        d = generateDelannoy(a-1, b) + generateDelannoy(a, b-1) + generateDelannoy(a-1, b-1);
    }
    return d;
}

int main(){
    int a = 3;
    int b = 3;
    int result = 0;
    result = generateDelannoy(a, b);
    cout << result << endl;
}

実行結果

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

63

与えられた座標 (a,b) = (3,3) に対して、漸化式 D(a-1,b) + D(a,b-1) + D(a-1,b-1) を用いて再帰的に計算を行うことで、デラノイ数「63」が出力されます。

補足：計算量について

この再帰的な実装はシンプルで理解しやすい反面、同じ引数に対する計算が何度も繰り返されるため、指数的な時間計算量となります。a や b が大きくなる場合は、メモ化（動的計画法）を組み合わせることで O(a×b) まで計算量を抑えることが可能です。