首页 > 代码库 > UVA-725除法-Division
UVA-725除法-Division
分析: 枚举0-9的所有排列?没这个必要,只需要枚举fghij就可以计算出abcde(=fghij * n),然后判断是否所有的数字都不相同即可。不仅程序简单,而且枚举量也从10!=3628800降低至不到1万,而且当abcde的位数不等于5的时候,就可以终止枚举了(记住n是大于等于2的哟!)
AC代码如下:用时为1573MS。
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> using namespace std;//n>=2 int vis[10],n,num;//每个数字是否被使用、要输入的数、除数的位数! //除数是用被除数和商得出的! int a[5],have; int getnum(int cnt)//获取当前a数组所存数列所代表的值! { int sum=0,s=0; for(int i=cnt-1; i>=0; i--) sum+=(int)pow(10,s++)*a[i]; return sum; } bool judge(int s)//判断s是否符合要求! { num=0; int vis1[10]; for(int i=0;i<10;i++) vis1[i]=vis[i];//把vis的状态赋给vis1,免得搜索时出错! while(s) { if(!vis1[s%10])//表示s%10这个数还没有出现过! vis1[s%10]=1; else return false; s/=10; num++; } if(num==5)//num只能等于5,可能等于其他数字! return true; return false;//因为num不等于5,表示不符合要求! } void fun(int cnt) { if(cnt>=5) { int chu=getnum(cnt)*n; if(judge(chu)) { have=true; cout<<chu<<" / "; for(int ii=0; ii<cnt; ii++) cout<<a[ii]; cout<<" = "<<n<<endl; } return ; } for(int i=0;i<10;i++) { if(!vis[i]) { vis[i]=1; a[cnt]=i; fun(cnt+1); vis[i]=0; } } } int main() { int x=1; while(cin>>n,n) { have=false; memset(vis,0,sizeof(vis)); if(x>1)cout<<endl; x++; fun(0); if(!have) cout<<"There are no solutions for "<<n<<'.'<<endl; } return 0; }
UVA-725除法-Division
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。