您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

跳馬問題：半棋盤上馬的遞歸路徑計數解法

編輯：關於C

問題描述

在 8×4 的半張中國象棋棋盤上，馬從左下角 (0,0) 跳至右上角 (8,4)。限制條件：只能向右跳（x 增加），不能向左跳。馬的走法為「日」字：水平 1 竖 2 或水平 2 竖 1。求所有合法跳躍方案數。

坐標系與移動向量定義

設當前坐標 (x, y)，目標 (8, 4)。允許的四個相對位移：

dx = {1, 2, 2, 1}
dy = {2, 1, -1, -2}

對應四種「向右」跳法：
① 右 1 上 2 → (x+1, y+2)
② 右 2 上 1 → (x+2, y+1)
③ 右 2 下 1 → (x+2, y-1)
④ 右 1 下 2 → (x+1, y-2)

遞歸算法設計

1. 邊界條件

成功：到達目標點 (x == 8 && y == 4)，方案數 +1。
越界：x < 0 || x > 8 || y < 0 || y > 4，直接返回。

2. 遞歸函數

void jump(int x, int y) {
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        // 邊界檢查
        if (nx < 0 || nx > 8 || ny < 0 || ny > 4) continue;
        // 到達終點
        if (nx == 8 && ny == 4) { count++; continue; }
        // 繼續遞歸
        jump(nx, ny);
    }
}

完整 Pascal 代碼（原始版本）

program tiaoma01;
const
  mbx = 8; mby = 4;
  dx: array[1..4] of integer = (1, 2, 2, 1);
  dy: array[1..4] of integer = (2, 1, -1, -2);
var
  num: integer;

procedure jump(x, y: integer);
var k, x1, y1: integer; t1, t2, t3: boolean;
begin
  for k := 1 to 4 do begin
    x1 := x + dx[k]; y1 := y + dy[k];
    t1 := (x1 >= 0) and (x1 <= mbx);
    t2 := (y1 >= 0) and (y1 <= mby);
    t3 := (x1 = mbx) and (y1 = mby);
    if (t1 and t2) then
      if t3 then inc(num)
      else jump(x1, y1);
  end;
end;

begin
  num := 0;
  jump(0, 0);
  writeln(num);
  readln;
end.

C++ 移植版本

#include 
using namespace std;

const int MAX_X = 8, MAX_Y = 4;
const int dx[4] = {1, 2, 2, 1};
const int dy[4] = {2, 1, -1, -2};
long long count = 0;  // 方案數可能較大

void jump(int x, int y) {
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx > MAX_X || ny < 0 || ny > MAX_Y) continue;
        if (nx == MAX_X && ny == MAX_Y) { count++; continue; }
        jump(nx, ny);
    }
}

int main() {
    jump(0, 0);
    cout << "總方案數: " << count << endl;
    return 0;
}

算法複雜度分析

時間：O(4^d)，d 為路徑深度。實際受棋盤邊界約束，有效狀態遠少於理論上限。
空間：O(d) 遞歸棧深度，最大約 12 步。
優化方向：備忘錄（DP）存儲 (x,y) 到終點的方案數，將指數級降為多項式級 O(X×Y)。

動態規劃優化版（自底向上）

long long dp[9][5] = {0};  // dp[x][y] 從(x,y)到終點的方案數
dp[8][4] = 1;  // 終點初始化

// 逆序填表：x從大到小，y全範圍
for (int x = 8; x >= 0; x--) {
    for (int y = 0; y <= 4; y++) {
        if (x == 8 && y == 4) continue;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx <= 8 && nx >= 0 && ny <= 4 && ny >= 0)
                dp[x][y] += dp[nx][ny];
        }
    }
}
cout << "DP結果: " << dp[0][0] << endl;

DP 版本時間 O(X×Y×4) = O(1)，極快。