阶乘浅析poj1150 3406 zoj1222 2358 - c++编程基础

;i {
a[i]=str[len-1-i]-'0';
}
int ans=getAns(len);
printf("%d\n",ans);
}
return 0;
}

4.数字n是否可以表示为若干个不同的阶乘的和

实际上这个问题跟数论无关，是一道搜索的问题
的第2358题，由于n比较小，只可能是0!~9!的数字和，所以可以直接用dfs搜索。

[cpp]
#include
#include
#include
#include
using namespace std;
int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
int sum;
bool vis[11];
mapmymap;
void dfs(int n)
{
if(n==10)
{
if(mymap.find(sum)==mymap.end())mymap[sum]=1;
return;
}
sum+=a[n];
dfs(n+1);
sum-=a[n];
dfs(n+1);
}
int main()
{
memset(vis,false,sizeof(vis));
sum=0;
mymap.clear();
dfs(0);
int n;
while(~scanf("%d",&n))
{
if(n<0)break;
if(n==0||mymap.find(n)==mymap.end())puts("NO");
else puts("YES");
}
return 0;
}

#include
#include
#include
#include
using namespace std;
int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
int sum;
bool vis[11];
mapmymap;
void dfs(int n)
{
if(n==10)
{
if(mymap.find(sum)==mymap.end())mymap[sum]=1;
return;
}
sum+=a[n];
dfs(n+1);
sum-=a[n];
dfs(n+1);
}
int main()
{
memset(vis,false,sizeof(vis));
sum=0;
mymap.clear();
dfs(0);
int n;
while(~scanf("%d",&n))
{
if(n<0)break;
if(n==0||mymap.find(n)==mymap.end())puts("NO");
else puts("YES");
}
return 0;
}

阶乘浅析poj1150 3406 zoj1222 2358 (三)