阶乘之和
时间限制：3000 ms | 内存限制：65535 KB
难度：3
- 描述
-
给你一个非负数整数n，判断n是不是一些数（这些数不允许重复使用，且为正数）的阶乘之和，如9=1！+2!+3!，如果是，则输出Yes，否则输出No；
- 输入
- 第一行有一个整数0<m<100,表示有m组测试数据；
每组测试数据有一个正整数n<1000000; - 输出
- 如果符合条件，输出Yes，否则输出No;
- 样例输入
-
2 9 10
- 样例输出
-
Yes No
-
#include<stdio.h> int fun1(int n) { int i=1,s=1; for(i=1;i<=n;i++) { s=s*i; if(s==n) return 1; else if(s*(i+1)>n) { break; } } if(n>=2*s) return 0; else { n-=s; fun1(n); } } int main() { int m; scanf("%d",&m); while(m--) { int n; scanf("%d",&n); if(fun1(n)) printf("Yes "); else printf("No "); } }这题不愧为贪心算法！我做这题做了两个小时，思路是对的，我就是没处理好阶乘时的问题才没做出来。S是小于等于整数N的第一最近N的某一个数的阶乘。我求这个S时犯了好多错误，千万不要让S=S/(i-1);那种形式，一定要干净利落的写出一个S否则就会出错。这题原理很简单，我们都知道N！必定大于前面N-1项阶乘的和，因为阶乘的倍数增长的太快了。加法就没法和它比，所以，我们就从S出发，当S*N>N-S>=S的时候，你感觉还会N还会是一些数的阶乘吗？肯定不会。如果S==N，那就说明正好有整数的阶乘与其相等，所以我利用递归让N=N-S；直到有N==S或者有N>=S的结果时就可以做出判断了！