[C/C++ 演算法]- 數字拆解
剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。
拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/SeparateNumber.htm
#include <stdio.h>
#include <stdlib.h>
#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("%2d", table[i][j]);
}
printf("\n");
}
}
|
沒有留言:
張貼留言