简单枚举UVa725-division (abcde / fghij = n)

本文主要是介绍简单枚举UVa725-division (abcde / fghij = n)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目位置：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=666

Write a program that finds and displays all pairs of 5-digit numbers that between them use the digits 0
through 9 once each, such that the first number divided by the second is equal to an integer N, where
2 ≤ N ≤ 79. That is,
abcde
fghij = N
where each letter represents a different digit. The first digit of one of the numerals is allowed to be
zero.
Input
Each line of the input file consists of a valid integer N. An input of zero is to terminate the program.
Output
Your program have to display ALL qualifying pairs of numerals, sorted by increasing numerator (and,
of course, denominator).
Your output should be in the following general form:
xxxxx / xxxxx = N
xxxxx / xxxxx = N
.
.
In case there are no pairs of numerals satisfying the condition, you must write ‘There are no
solutions for N.’. Separate the output for two different values of N by a blank line.
Sample Input
61
62
0
Sample Output
There are no solutions for 61.
79546 / 01283 = 62
94736 / 01528 = 62

开始以为这道题可以暴力枚举，全排列，判断每种情况，结果可想而知，超时。代码也附在下面，像填空题啥的可以用…

看了书之后才发现可以简化很多。具体解释看代码

特别注意，结尾没有空行~！！！

这里是

sprintf(buf,"%05d%05d",abcde,fghij)

先转化成字符串，然后排序，再依次判断对应位置是否为i

同时很巧妙的是提前判断一下长度超过10就肯定不满足，而之后的数也会越来越大，所以直接break;

另外判断是否为0~9，如果是数字的话，还可以按照

1+2+3+4+5+…+9=45

1*2*3*4*5*…*9=362880

来判断

//巧妙的借助fghij可以由ancde获得，减少了循环次数。不用把每种情况列举出来

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;int main(){int n,kase=0;int fghij,abcde;char buf[20];while(scanf("%d",&n)!=EOF&&n){if(kase++) printf("\n");<span style="white-space:pre">		</span>//开头输出\nint num = 0;for(fghij = 1234;fghij<49384;fghij++){      //!!!注意截至条件，98765/2=49384bool ok=1;abcde=fghij*n;sprintf(buf,"%05d%05d",abcde,fghij);if(strlen(buf)>10) break;                //书上是break,如果是有临界条件，continue也可以 sort(buf,buf+10);<span style="white-space:pre">			</span>//排序以后对0~9是否出现进行判断for(int i = 0; i <=9; i++){if(buf[i]!=i+'0'){ok=0;break;}}if(ok){printf("%05d / %05d = %d\n",abcde,fghij,n);num++;}}if(num==0) printf("There are no solutions for %d.\n",n);}return 0;
}

最后也附上超级暴力的枚举，全排序可以借鉴

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;int main(){int n,ok=0,a[10];for(int i=0;i<=9;i++) a[i]=i;while(scanf("%d",&n)!=EOF&&n){ok=0;do{int x=a[9]*10000+a[8]*1000+a[7]*100+a[6]*10+a[5];int y=a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4];if(y*n==x){printf("%d/%d = %d\n",x,y,n);ok=1;}}while(next_permutation(a,a+10));if(ok==0) printf("There are no solutions for %d.\n",n);}return 0;
}