Project Euler——Problem 32 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 31
Project Euler——Problem 33

Project Euler——Problem 32

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

原题与答案:

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个。我的程序源代码如下所示:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. int list[10],prod[3100],i,j,ans,s,t,u;
  5. bool yet[10],first=true;
  6. void check()
  7. {
  8.         int i;
  9.         for (u=0,i=5;i<9;i++) u=u*10+list[i];
  10.         for (s=i=0;i<1;i++) s=s*10+list[i];
  11.         for (t=0,i=1;i<5;i++) t=t*10+list[i];
  12.         if (s&&t>=1000&&u>=1000&&s*t==u)
  13.                 prod[++prod[0]]=u;
  14.         for (s=i=0;i<2;i++) s=s*10+list[i];
  15.         for (t=0,i=2;i<5;i++) t=t*10+list[i];
  16.         if (s>=10&&t>=100&&u>=1000&&s*t==u)
  17.                 prod[++prod[0]]=u;
  18. }
  19. void calc(int pos)
  20. {
  21.         if (pos==9) check();
  22.         else
  23.                 for (list[pos]=1;list[pos]<=9;list[pos]++)
  24.                         if (!yet[list[pos]])
  25.                         {
  26.                                 yet[list[pos]]=true;
  27.                                 calc(pos+1);
  28.                                 yet[list[pos]]=false;
  29.                         }
  30. }
  31. int main()
  32. {
  33.         prod[0]=0;
  34.         memset(yet,false,sizeof(yet));
  35.         calc(0);
  36.         std::sort(prod+1,prod+prod[0]+1);
  37.         for (ans=0,i=j=1;;i=j)
  38.         {
  39.                 ans+=prod[i];
  40.                 while (j<=prod[0]&&prod[i]==prod[j])
  41.                         j++;
  42.                 if (j>prod[0]) break;
  43.         }
  44.         printf("%d\n",ans);
  45.         return 0;
  46. }

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter