给定一个非负整数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 阅读(1980)
评论(0) 编辑 收藏 引用 所属分类:
算法基础