Zi 字媒體

[C/C++ 演算法]- 數字拆解 剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。 拷貝來源：http://openhome.cc/Gossip/AlgorithmGossip/http://openhome.cc/Gossip/AlgorithmGossip/SeparateNumber.htm #include #include #define NUM 10 // 要拆解的數字 #define DEBUG 0 void init(int[][NUM / 2 + 1]); int min(int, int); int f(int[][NUM / 2 + 1], int, int); void dp(int[][NUM / 2 + 1]); int count(int[][NUM / 2 + 1]); void print(int[][NUM / 2 + 1]); int main(void) { int table[NUM][NUM / 2 + 1] = {0}; init(table); dp(table); printf("可拆解出 %d 組數字\n", count(table)); if(DEBUG) { print(table); } return 0; } void init(int table[][NUM / 2 + 1]) { int i; for(i = 0; i < NUM; i++) { table[i][0] = 1; // 任何數用 0 以下的數拆解必只有 1 種 table[i][1] = 1; // 任何數用 1 以下的數拆解必只有 1 種 } } int min(int a, int b) { return a > b ? b : a; } int f(int table[][NUM / 2 + 1], int x, int y) { int c, i; for(c = 0, i = 1 ; i <= y; i++) { c += table[x - i][min(x - i, i)]; } return c; } void dp(int table[][NUM / 2 + 1]) { int x; for(x = 2; x < NUM; x++){ int y; for(y = 2; y < NUM / 2 + 1 && y <= x; y++) if(x + y <= NUM) { table[x][y] = f(table, x, y); } } } int count(int table[][NUM / 2 + 1]) { int i, result; for(i = 1, result = 0 ; i <= NUM; i++) { result += table[NUM - i][(NUM - i >= i) ? i : NUM - i]; } return result; } void print(int table[][NUM / 2 + 1]) { int i; for(i = 0; i < NUM; i++) { int j; for(j = 0; j < NUM/2+1; j++) { printf("-", table[i][j]); } printf("\n"); } }