Prime Cryptarithm（枚举）

Prime Cryptarithm

The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.

      * * *
   x    * *
    -------
      * * *         <-- partial product 1
    * * *           <-- partial product 2
    -------
    * * * *

Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.

Note that the 'partial products' are as taught in USA schools. The first partial product is the product of the final digit of the second number and the top number. The second partial product is the product of the first digit of the second number and the top number.

Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.

PROGRAM NAME: crypt1

INPUT FORMAT

Line 1:	N, the number of digits that will be used
Line 2:	N space separated digits with which to solve the cryptarithm

SAMPLE INPUT (file crypt1.in)

5
2 3 4 6 8

OUTPUT FORMAT

A single line with the total number of unique solutions. Here is the single solution for the sample input:

      2 2 2
    x   2 2
     ------
      4 4 4
    4 4 4
  ---------
    4 8 8 4

SAMPLE OUTPUT (file crypt1.out)

1

   题意：

   有N个数，使这N个数满足以上的乘法法则，并且乘出来的每个数都在给出的这N个数中。

 

   思路：

   在已给出的数中一个个列举出来再乘起来判断，满足条件则sum积累。

 

   AC：

 

/*
TASK:crypt1
LANG:C++
ID:sum-g1
*/
#include<stdio.h>
#include<stdlib.h>
int number[15];
int n;

int test(int a,int b)
{
	int k,temp=0;
	while(a)
	{
		for(k=0;k<n;k++)
		 if((a%10)==number[k]) {temp++;break;}
		a/=10;
	}
	if(temp==b)  return 1;
	else         return 0;
}
//test用来测试乘起来的这些数是否在已给出的数中
//a代表这个数，b代表位数
int main()
{
freopen("crypt1.in","r",stdin);
freopen("crypt1.out","w",stdout);	
int i,first,second;
	int t1,t2,t3,t4,t5;
	int sum=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&number[i]);
	for(t1=0;t1<n;t1++)
	{
		for(t2=0;t2<n;t2++) 
//一开始手抽写成t2<0，导致循环不能进行，要细心！
		{
			for(t3=0;t3<n;t3++)
			{
				first=number[t1]*100+number[t2]*10+number[t3];
//列举这三位数，使它变成一个整数，非一个个字符
				for(t4=0;t4<n;t4++)
				{
					if(number[t4]*first>999) continue;
					if(!test(number[t4]*first,3)) continue;
					for(t5=0;t5<n;t5++)
					{
					second=number[t4]*10+number[t5];
//列举这两位数，使它变成一个整数，非一个个字符
					if(number[t5]*first>999) continue;
//超过3位数在排除
					if(!test(number[t5]*first,3)) continue;
//不是已给出的数则排除
					if(second*first>9999||!test(second*first,4)) continue;
//乘出来的数不是4位数，或者这个4位数不是已给出的数
					if(second*first<9999&&second*first>1000&&test(second*first,4))  sum++;
//是4位数，且是给出的数，则sum积累
					}
				}
			}
		}
	}
	printf("%d\n",sum);
	exit(0);
}

   更优化的办法：

   换种角度思考来列举，既然已经规定第一个数为3位数，第二个数为2位数，则三位数 i 从100列举到999，二位数 j 从10到99。仅仅只需要两重循环，并且满足条件即可：

   1.判断这个数是否由已给出的数所组成；

   2.判断这个两位数个位和十位分别与 这个满足条件1的三位数 i 相乘是否都是三位数，并且是否满足1条件；

   3.满足1和2条件下，将i与j相乘，得出的数result是否为一个4位数，并且是否满足条件1。

   下面的技巧在于用数组0,1标记这个数是否存在。

/*
TASK:crypt1
LANG:C++
ID:sum-g1
*/
#include<stdio.h>
int hash[15]={0};
int n;

int test(int a)
{
	while(a)
	{
	 if(!hash[a%10]) return 0;  
//记得要%10 
	 a/=10;
    }
    return 1;
}

int main()
{
freopen("crypt1.in","r",stdin);
freopen("crypt1.out","w",stdout);	
int number,i,j;
	int first,second,sum=0,result;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&number);
		hash[number]=1;
	}	
	for(i=100;i<1000;i++)
	{
		if(!test(i)) continue;
		for(j=10;j<100;j++)
		{
			if(!test(j)) continue;
			first=(j%10)*i;
			second=(j/10)*i;
			if(first<100||first>999||second>999||second<100)   continue;
			if(!test(first)||!test(second)) continue;
			result=i*j;
			if(!test(result)||result>9999||result<1000)  continue;
			sum++;
		}
	}
	printf("%d\n",sum);
}

   总结：

   当题目的条件比较多时，应一一列举出来，细心分析归纳，理清好思路非常重要。题目看起来好像很麻烦的样子，但是仔细分析的话其实也只是多了几个条件而已，数据看起来很庞大，但是当写完出来之后发现也只不过是这样而已。有时候做题往往就是被这种表面的东西吓到了，所以不愿去尝试，必须去习惯做这类枚举的题目，尝试总比什么都不做要好。