话不多说,先上题:
这个题的中文大意是:给你一个N,2<=N<=79,然后根据这个N,求出给定的式子abcde/fghijk=N中那两个五位数的所有可能,而这两个五位数共十位,十个数字0~9不能重复。
通过分析样例我们可以知道,在没有这样的符合条件的数时我们输出如图的那一句话,而存在这样的数时分母的五位数可以是一个前缀0的四位数。
好,条件与注意事项已经全部知道了,怎么办?对于计算机来说,这样的数据量,用枚举显然也是个不错的办法,然而不要暴力枚举,要优雅的枚举,不然坐等时间爆炸。。
那么怎样去优雅的枚举?要尽可能的缩小枚举的数据量,才是优雅。
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n;
int a[10];
int times = 0;
while(cin>>n && n!=0)
{
int x;
int y;
int cnt,cnt1=0;
times++;
if(times > 1)
{
printf("\n");
}
for(x=1234;x<=98765;x++)
//其实这里的数据范围还不是最小,12345>x>9876的这个范围其实也可以
//不用遍历的,因为其中的每个数字总有重复的几位
{
y=x*n;
if(y>=99999) break;
a[5] = x/10000; a[6] = x%10000/1000; a[7] = x%1000/100; a[8] = x%100/10; a[9] = x%10;
a[0] = y/10000; a[1] = y%10000/1000; a[2] = y%1000/100; a[3] = y%100/10; a[4] = y%10;
cnt=0;
for(int i=0;i<9;i++)
{
int j;
for(j=i+1;j<10;j++)
{
if(a[i]==a[j])
{
cnt++;
break;
}
}
}
if(cnt==0)
{
printf("%d / %d%d%d%d%d = %d\n",y,a[5],a[6],a[7],a[8],a[9],n);
cnt1++;
}
}
if(cnt1==0) printf("There are no solutions for %d.\n",n);
//printf("\n");
}
return 0;
}
自认为比较蠢的枚举思路,望大牛们指正。。