Edison.X. Blog

考慮一個簡單的問題

x+Y <= 3，其中 x, y 為大於等於 0 之整數，要把所有符合條件的 x, y 都列出來。

這問題只是簡單的 trackback ，用 recursive 很快可得到解答，說明有空再寫。

原始碼如下

#include <stdio.h>
#define LIM 3
#define CNT 2

int sol[CNT] = {0};
int sol_cnt;

inline void print_ans()
{
    int i;
    printf("sol_%02d:(", sol_cnt+1);
    for(i=0; i<CNT-1; ++i) printf("%2d,",sol[i]);
    printf("%2d)\n",sol[CNT-1]);
    sol_cnt++;
}

void DFS(int index, int sum)
{
    sum+=sol[index];

    if(sum<=LIM && index==CNT-1) {// 找到解答
           print_ans();
           // 回到上一動作，試下一個解答
           sum = sum-sol[index];
           sol[index]++;
           DFS(index, sum);
    }
    else if(sum<=LIM) { // 暫時符合條件
           DFS(index+1, sum); // 繼續往下找
    }
    else { // 不合條件
           if(index-1<0) return; // 全找遍,結束
           sum = sum-sol[index]; // 
           sol[index]=0; // 目前變數設 0
           sum = sum-sol[index-1];
           sol[index-1]++; // 上一個變數 +1
           DFS(index-1, sum); // 往上個變數跑
    }
}

int main()
{
    DFS(0, 0);
    return 0;
}