Số Delannoy là gì? Chương trình C++ tìm số Delannoy

Số Delannoy D(a,b): số đường đi từ (0,0) đến (a,b) trên lưới chữ nhật, chỉ được đi: sang phải (→), chéo lên phải (↗), lên (↑).

Công thức truy hồi:

D(a,b) = D(a-1,b) + D(a,b-1) + D(a-1,b-1), với D(0,0)=1

Ví dụ: D(3,3) = 63.

Thuật toán

• Nhập tọa độ (a,b)
• Hàm generateDelannoy(a,b)
• Base case: a==0 || b==0 → return 1
• Đệ quy: return D(a-1,b) + D(a,b-1) + D(a-1,b-1)

Code C++

#include <iostream>
using namespace std;

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

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

Kết quả

63

Với (3,3), số Delannoy = 63.