注意0的阶乘是1!
二进制
用二进制的每一位表示状态(1表示选某个数,0表示不选某个数,从而实现枚举每一种情况
核心代码
for(int i = 0; i < 1 << N; i ++){
...
for(int j = 0; j < 10; j ++){
if(i >> j & 1) ...
}
...
}
C++ 代码
#include<iostream>
using namespace std;
int n;
int jc[10] = {1,1,2,6,24,120,720,5040,40320,362880}; //提前列出每个数的阶乘 也可以通过递归或循环计算
int main(){
while(cin >> n, n >= 0){
int flag = 0;
if(n == 0){
cout << "NO" << endl;
continue;
}
for(int i = 0; i < 1 << 10; i ++){
int t = 0;
for(int j = 0; j < 10; j ++){
if(i >> j & 1) t += jc[j];
}
if(t == n) flag = 1;
}
if(flag == 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
dfs
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1000010;
int n;
int jc[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int sum = 0;
int flag = 0;
void dfs(int sum,int u){
if(u == 10){
if(n == sum) flag = 1; //此时u= 10代表以枚举完十个数,若你sum == n说明该数可以被凑出来
return ;
}
dfs(sum,u + 1); // 不选
dfs(sum + jc[u],u + 1); //选
}
int main(){
while(cin >> n, n >= 0){
if(n == 0){
cout << "NO" << endl;
continue;
}
flag = 0;
sum = 0;
dfs(0,0);
if(flag == 1) cout << "YES" << endl;
else if(flag == 0) cout << "NO" << endl;
}
return 0;
}
怎么确定是10个数的
原来如此,多谢群佬
思来想去不知道两层循环的意思,也不知道叫什么,但是我发现这个知识点是在基础课容斥原理里讲的。
大佬大佬 读取数那里为什么要用
我改成
就会一直wa
不是大佬。。
while(cin>>n) 和 while(scanf(“%d,&n”) != EOF)应该是一样的 是没有数据输入时结束
而不是当输入数据为负数时结束
失策了,我以为读到-1结束在下面写了个-1 break。
仔细看题才发现读到负数就结束了