九層循環怎麼寫

寫完代碼，問題《九層循環怎麼寫？？？》就被關閉了，把答案放在這裡。

問題：1-9 數字組成3個數 abc, cde, fgh 且 abc:def:ghi=1:2:3。

167個字元的答案：

g(x,y,z){x*2==y&x*3==z&&printf("%d,%d,%d
",x,y,z);}f(i,j,m,r){i?1<<j&m||f(i-1,1,m|1<<j,r*10+j),j<10&&f(i,j+1,m,r):g(r/1000000,r/1000%1000,r%1000);}main(){f(9,1,0,0);}

編譯及輸出：

gcc -w a.c && ./a.out192,384,576219,438,657273,546,819327,654,981

明明就有九層循環。

更新1：如何用遞歸表示 n 層 for 循環

在《Milo Yip：兩個for循環能處理哪些問題？》里，我提到

兩個嵌套 for 循環可把兩個集合 生成 笛卡兒積（Cartesian product）

那麼，要對集合 做九個嵌套 for，可表示為 。

假設我們直接寫成 9 個 for 循環：

#include <stdio.h>void output(const int* a) { for (int i = 0; i < 9; i++) printf("%d ", a[i]); printf("
");}int main() { int a[9]; for (a[8] = 1; a[8] < 10; a[8]++) for (a[7] = 1; a[7] < 10; a[7]++) for (a[6] = 1; a[6] < 10; a[6]++) for (a[5] = 1; a[5] < 10; a[5]++) for (a[4] = 1; a[4] < 10; a[4]++) for (a[3] = 1; a[3] < 10; a[3]++) for (a[2] = 1; a[2] < 10; a[2]++) for (a[1] = 1; a[1] < 10; a[1]++) for (a[0] = 1; a[0] < 10; a[0]++) output(a);}

輸出：

1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 ...1 2 1 1 1 1 1 1 12 2 1 1 1 1 1 1 13 2 1 1 1 1 1 1 1...9 9 9 9 9 9 9 9 9

但我們可以考慮到：

我們可用這種遞歸形式，定義一個函數，裡面只做一個 for 循環去表示上式里的一個笛卡兒積：

#include <stdio.h>void output(const int* a) { for (int i = 0; i < 9; i++) printf("%d ", a[i]); printf("
");}void f(int* a, int n) { for (a[n] = 1; a[n] < 10; a[n]++) if (n == 0) output(a); else f(a, n - 1);}int main() { int a[9]; f(a, 8);}

這是一個通用的方式，把 n 個 for 循環寫成遞歸形式。如果 n 不是常數，用遞歸是簡單的解決方法。

談回到原問題，其實它只需要 的排列（permutation），即 次測試。原答案用了組合（combination），並用位集（bit set）的方式去避免加入重複的數字，但理想的做法是直接生成所有排列[1]。

更新2：原答案的「解壓」版本：

#include <stdio.h>void outputIfValid(int abc, int def, int ghi) { if (abc * 2 == def && abc * 3 == ghi) printf("%d,%d,%d
", abc, def, ghi);}// 第 i 層 for 循環, m 以 bit set 表示已使用的數字, r 為當前排列 abcdefghivoid f(int i, int m, int r) { if (i == 0) outputIfValid(r / 1000000, r / 1000 % 1000, r % 1000); // abcdefghi -> abc, def, ghi else for (int j = 1; j < 10; j++) if (((1 << j) & m) == 0) // 若 j 沒有被使用 f(i - 1, m | (1 << j), r * 10 + j); // m 和 r 都加入 j，進入 i - 1 的循環}int main() { f(9, 1, 0);}

更新3： C++03 版本，採用 std::next_permutation

#include <algorithm>#include <numeric>#include <iostream>using namespace std;int main() { int a[9]; iota(a, a + 9, 1); do { int abc = a[0] * 100 + a[1] * 10 + a[2]; int def = a[3] * 100 + a[4] * 10 + a[5]; int ghi = a[6] * 100 + a[7] * 10 + a[8]; if (abc * 2 == def && abc * 3 == ghi) cout << abc << "," << def << "," << ghi << endl; } while(next_permutation(a, a + 9));}

[1] Knuth, Donald (2011), "Section 7.2.1.2: Generating All Permutations", The Art of Computer Programming, volume 4A.

推薦閱讀：