Project Euler——Problem 32

daybreakcx posted @ 2009年8月15日 05:12 in Prject Euler , 1236 阅读

原题与答案：

Problem 32

06 December 2002

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Answer:45228

分析与解答：

这个题目是求所有的满足条件的乘法表达式的积的和，题目中的条件是要求表达式中出现1到9这9个数字，每个有且只有一次。仔细分析一下去掉一些不可能的情况，首先是我们的表达式里面一共有9个数字，这样我们先考虑生成9的全排列，然后再加入乘号和等号，同时考虑到我们加入乘号和等号的情况总数为C(8,2)=28种，我们可以从这里排除掉一大堆不可能的情况。对于一个n位数和一个m位数的乘法，他们的积只可能是n+m或者是n+m-1位数，于是乎我们可以假设当被乘数小等于乘数的时候，我们得到的只可能有两种情况符合题意，即1位数*4位数=4位数或者是2位数*3位数=4位数，这样我们就将情况数从28种缩减到了2种，然后就是枚举计算的事情了，实际上满足条件的表达式非常少，因为积都是4位数，不会超过P(9,4)=3024个，但是实际算出来只有9个。我的程序源代码如下所示：

#include<stdio.h>
#include<string.h>
#include<algorithm>
int list[10],prod[3100],i,j,ans,s,t,u;
bool yet[10],first=true;
void check()
{
int i;
for (u=0,i=5;i<9;i++) u=u*10+list[i];
for (s=i=0;i<1;i++) s=s*10+list[i];
for (t=0,i=1;i<5;i++) t=t*10+list[i];
if (s&&t>=1000&&u>=1000&&s*t==u)
prod[++prod[0]]=u;
for (s=i=0;i<2;i++) s=s*10+list[i];
for (t=0,i=2;i<5;i++) t=t*10+list[i];
if (s>=10&&t>=100&&u>=1000&&s*t==u)
prod[++prod[0]]=u;
}
void calc(int pos)
{
if (pos==9) check();
else
for (list[pos]=1;list[pos]<=9;list[pos]++)
if (!yet[list[pos]])
{
yet[list[pos]]=true;
calc(pos+1);
yet[list[pos]]=false;
}
}
int main()
{
prod[0]=0;
memset(yet,false,sizeof(yet));
calc(0);
std::sort(prod+1,prod+prod[0]+1);
for (ans=0,i=j=1;;i=j)
{
ans+=prod[i];
while (j<=prod[0]&&prod[i]==prod[j])
j++;
if (j>prod[0]) break;
}
printf("%d\n",ans);
return 0;
}