紫书例题7-1 除法

Posted on | In |

输入正整数n，用0~9这10个数字不重复组成两个五位数abcde和fghij，使得abcde/fghij的商为n，按顺序输出所有结果。如果没有找到则输出“There are no solutions for N.”。这里2<=n<=79。

样例输入： 62

样例输出：

79546/01238=62

94736/01528=62

法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//x用ijkmn表示，若整除n，求出y，而后用abcde表示Y,看是否重复数字 
#include<iostream>
#include<set>
using namespace std;
int main() {
	int i,j,k,m,n;
	int a,b,c,d,e;
	int t;
	cin>>t ;
	

	for(i=0;i<=9;i++){
		for( j=0;j<=9;j++)
		for( k=0;k<=9;k++){
			for(m=0;m<=9;m++)
			for( n=0;n<=9;n++)
			{
				set<int> s;//!!!
					int flag=1;//!!!
				int num=i*10000+j*1000+k*100+m*10+n;
				if(!(num%t))
				{
					int y=num/t;
					a=y/10000,b=y/1000%10,c=y/100%10,d=y/10%10,e=y%10;
					s.insert(a);
					s.insert(b);
					s.insert(c);
					s.insert(d);
					s.insert(e);
					s.insert(i);
					s.insert(j);
					s.insert(k);					
					s.insert(m);
					s.insert(n);	
//					for(set<int>::iterator it=s.begin();it!=s.end();it++)
//					cout<<*it<<" ";
//		break;
							if(s.size()!=10) flag=0;
							if(flag==1) cout<<i<<j<<k<<m<<n<<"/"<<a<<b<<c<<d<<e<<"="<<t<<endl;
					}
				}		
			}
	}
	return 0;
}

法二

暴力枚举法

问题分析：没有什么好办法，就暴力枚举吧！不过还是要下点功夫，否则10！的计算量是不可想象的。

1.因为n>=2，且abcde=fghij×n，满足abcde>fghij。若a=0，则fghij的最小值为12345，abcde<fghij，矛盾。所以a≠0。

2.因为a≠0，所以12345<=abcde<=98765，01234<=fghij。

3.因为2≤n，且abcde≤98765，那么fghij = abcde/n，得fghij≤98765/2=49382，所以01234≤fghij≤49382。

4.因为12345≤abcde≤98765，且01234≤fghij≤49382，所以用fghij进行枚举范围比较小。（这是在任意的n的条件下得出的结论）

5.对于给定的n，因为abcde≤98765，那么fghij = abcde/n，得fghij≤98765/n。结论：01234≤fghij≤98765/n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>  
#include <memory.h>  
#include<iostream>  
#define DIGITNUM 10  
//这里判断两个数的每一位都不相同我用的是采用一个数组，然后把每一个数字在对应的数组中的位置的元素换成1，然后判断数组中的元素是否全部都为1即可。
//数组下标代表0，1，2，3，4，5，6，7，8，9
using namespace std;
//int num[DIGITNUM]={0};
int d,f;
int check(int abcde, int fghij)  
{  int num[DIGITNUM]={0};
	if(fghij < 10000)  
        num[0] = 1;  
  
	while(abcde){
		d=abcde%10;
		if(num[d]) return 0;
		 num[d]=1;
		abcde/=10;
	} 
	while(fghij){
		f=fghij%10;
		if(num[f]) return 0;
	num[f]=1;
		fghij/=10;			
	}
	return 1;}

int main(){
	int n;
	cin>>n;
	int end=98765/n;
	int cnt=0;
	for(int i=1234;i<=end;i++)
	{
		int k=i*n;
			if(k>=12345&&check(k,i)){  
                printf("%05d / %05d = %d\n", k, i, n);  
                cnt++;  
            } 
			
		}
		if(cnt == 0)  
            printf("There are no solutions for %d.\n", n);  
	
	
	
	
	
	
	return 0;
}