給定一個非負整數n，判斷n是否表示成若干階乘的和，n = a
1! + a
2! + a
3! + ... + a
i!其中a1、a2、...、ai各不相等。
這里限定n為一個比較小的數，如1000000。
因為n比較小，可以先把i!算出來保存下來，當i為10時，10!已經比1000000大了，所以我們只需要搜索n是否能表示成1!~9！中的若干個階乘之和即可。簡單的搜索題，代碼如下：
#include <cstdio>
#define MAX 100
int a[MAX];
int init() {
int i = 1;
int res = 1;
while (res < 1000000) {
a[i] = res;
i++;
res *=i;
}
return i - 1;
}
int is_factorial_sum(int sum, int index) {
if (sum == 0) {
return 1;
} else if (sum < 0 || index < 0) {
return 0;
}
if (is_factorial_sum(sum - a[index], index - 1)) {
return 1;
}
return is_factorial_sum(sum, index - 1);
}
int main() {
int len = init();
int cases;
scanf("%d", &cases);
while (cases--) {
int n;
scanf("%d", &n);
if (is_factorial_sum(n, len)) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
因為這里的n不大，所以可以直接暴力搜索，但是如果n非常大了怎么辦？
這里提供一個非常棒的思路：
注意到a
i! > a
i-1! + a
i-2! + ... + a
1!
這個式子非常容易證明，因為a
i-1! + a
i-2! + ... + a
1! < (i-1)a
i-1! < ia
i-1! = a
i!
有了這個式子，我們可以非常容易得利用貪心算法，因為對于任意的n，可以從最大的階乘開始枚舉，一旦a
j+1! > n && a
j! < n，那么如果n可以表示成階乘之和的話那么a
j!必然是其中一項！
代碼如下：
1 #include <cstdio>
2
3 #define MAX 100
4
5 int a[MAX];
6
7 int init() {
8 int i = 1;
9 int res = 1;
10 while (res < 1000000) {
11 a[i] = res;
12 i++;
13 res *=i;
14 }
15 return i - 1;
16 }
17
18 int main() {
19 int len = init();
20 int cases;
21 scanf("%d", &cases);
22 while (cases--) {
23 int n, i;
24 scanf("%d", &n);
25 for(i = len; i > 0; --i) {
26 if (n == a[i]) {
27 n = 0;
28 break;
29 } else if (n > a[i]) {
30 n -= a[i];
31 }
32 }
33 if (n == 0) {
34 printf("Yes\n");
35 } else {
36 printf("No\n");
37 }
38 }
39 return 0;
40 }
posted on 2012-09-17 20:45
myjfm 閱讀(2013)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎