PE[32]:Find the sum of all numbers that can be written as pandigital products.

chyanog · 发表于 2010-4-22 23:02:40

本帖最后由 chyanog 于 2010-4-27 11:02 编辑

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.

7254有着特殊的性质：
　　　　　　　39*186 = 7254
可以看到，乘数，被乘数与乘积连起来恰好是数字1到9的一个排列(391867254)。
现在求所有数c的和，其中c满足存在a,b使得a*b=c，且a,b,c连起来为123456789的一个排列。
这道题使我想起了小学的一道奥数题：求满足将 1 - 9 九个数填入右边式子成立的数，1----9都用上，只用一次，不重不漏、
〇〇〇〇*〇 = 〇〇〇〇。
只要会做这个，这道题应该就没有问题了。

lin2009 · 发表于 2010-4-23 10:17:06

12 * 483 = 5796
18 * 297 = 5346
27 * 198 = 5346
28 * 157 = 4396
39 * 186 = 7254
4 * 1738 = 6952
4 * 1963 = 7852
42 * 138 = 5796
48 * 159 = 7632

不重复C的累加和为 45228

shamohu · 发表于 2010-4-23 16:02:28

1stOpt求解代码：

IntParameter x(9)=[1,9];
Exclusive = True;
Function (x1*10+x2)*(x3*100+x4*10+x5)=x6*1000+x7*100+x8*10+x9;

复制代码

lin2009 · 发表于 2010-4-23 17:24:44

本帖最后由 lin2009 于 2010-4-23 17:27 编辑

5# shamohu

漏掉了一种可能性：k1*(1000*k2 + 100*k3 + 10*k4 + k5) == 1000*k6 + 100*k7 + 10*k8 + k9，且每次只能得到一个解，多次运行也不能保证没有遗漏正解。
对于穷举类型的问题，似乎用不上劲。

我试了这道题，用C编了最低效的穷举法，用了20s，时间稍长，但是程序简单明了，且不会遗漏。

#include < stdio.h >
void main(void)
{
  FILE *fp;
  fp = fopen("mydat.txt","w");

  for (int k1 = 1; k1 <= 9;k1 ++ )
{
   for (int k2 = 1; k2 <= 9;k2 ++ )
      {
      for (int k3 = 1; k3 <= 9;k3 ++ )
         {
            for (int k4 = 1; k4 <= 9;k4 ++ )
            {
               for (int k5 = 1; k5 <= 9;k5 ++ )
                  {
                  for (int k6 = 1; k6 <= 9;k6 ++ )
                     {
                        for (int k7 = 1; k7 <= 9;k7 ++ )
                        {
                           for (int k8 = 1; k8 <= 9;k8 ++ )
                              {
                              for (int k9 = 1; k9 <= 9;k9 ++ )
                                 {
                                    if ((k1 != k2) && (k1 != k3) && (k1 != k4) && (k1 != k5) && (k1 != k6) && (k1 != k7) && (k1 != k8) && (k1 != k9) && \
                                       (k2 != k3) && (k2 != k4) && (k2 != k5) && (k2 != k6) && (k2 != k7) && (k2 != k8) && (k2 != k9) && \
                                       (k3 != k4) && (k3 != k5) && (k3 != k6) && (k3 != k7) && (k3 != k8) && (k3 != k9) && \
                                       (k4 != k5) && (k4 != k6) && (k4 != k7) && (k4 != k8) && (k4 != k9) && \
                                       (k5 != k6) && (k5 != k7) && (k5 != k8) && (k5 != k9) && \
                                       (k6 != k7) && (k6 != k8) && (k6 != k9) && \
                                       (k7 != k8) && (k7 != k9) && \
                                       (k8 != k9) )
                                    {
                                       if (k1*(1000*k2 + 100*k3 + 10*k4 + k5) == 1000*k6 + 100*k7 + 10*k8 + k9)
                                          {
                                          printf("%d * %d = %d\n",k1, 1000*k2 + 100*k3 + 10*k4 + k5,1000*k6 + 100*k7 + 10*k8 + k9);
                                          fprintf(fp,"%d * %d = %d\n",k1, 1000*k2 + 100*k3 + 10*k4 + k5,1000*k6 + 100*k7 + 10*k8 + k9);
                                          }
                                       if ((10*k1 + k2)*(100*k3 + 10*k4 + k5) == 1000*k6 + 100*k7 + 10*k8 + k9)
                                          {
                                          printf("%d * %d = %d\n",10*k1 + k2,100*k3 + 10*k4 + k5,1000*k6 + 100*k7 + 10*k8 + k9 );
                                          fprintf(fp,"%d * %d = %d\n",10*k1 + k2,100*k3 + 10*k4 + k5,1000*k6 + 100*k7 + 10*k8 + k9 );
                                          }
                                    }
                                 }
                              }
                        }
                     }
                  }
            }
         }
      }
}
  fclose(fp);
}

lin2009 · 发表于 2010-4-23 21:32:27

把0也加进来，大家看看下面的一组数：
27 * 594 = 16038
3 * 5694 = 17082
36 * 495 = 17820
3 * 6819 = 20457
3 * 6918 = 20754
3 * 8169 = 24507
3 * 9168 = 27504
39 * 402 = 15678
4 * 3907 = 15628
45 * 396 = 17820
46 * 715 = 32890
4 * 7039 = 28156
4 * 9127 = 36508
52 * 367 = 19084
54 * 297 = 16038
63 * 927 = 58401
6 * 5817 = 34902
7 * 3094 = 21658
7 * 4093 = 28651
78 * 345 = 26910
7 * 9304 = 65128
7 * 9403 = 65821

lin2009 · 发表于 2010-4-24 08:42:07

本帖最后由 lin2009 于 2010-4-24 08:46 编辑

看来大家对数字问题的兴致蛮高的，索性＋—＊／＝都上阵，问0～9能否组成等式？
如 1＋2 －0＊45678／9 ＝ 3，当然这个式子没有多大的意义。这只是说明问题而已，我们可以进一步规定乘除（甚至加减）的操作数不能等于0，0～9和+-*/=一个都不能少，但只能出现一次。
只要能组成等式即可，因此不限定等号一定要出现在+-*/之后。

应排除重复的解，如：
1＋2 －0＊45678／9 ＝ 3
1－0＊45678／9＋2 ＝ 3
3 ＝ 1－0＊45678／9＋2
等不同的排列的形式。
（发了此帖，仿真币就有1001，1001也是大家很熟悉的传奇数字，希望0~9能再现传奇，呵呵...）

lin2009 · 发表于 2010-4-27 11:23:33

看来大家对数字问题的兴致蛮高的，索性＋—＊／＝都上阵，问0～9能否组成等式？
如 1＋2 －0＊45678／9 ＝ 3，当然这个式子没有多大的意义。这只是说明问题而已，我们可以进一步规定乘除（甚至加减）的操作数不能等 ...
lin2009 发表于 2010-4-24 08:42

非常高兴地发现符合这一条件的解还挺多的（0～9，+-*/=），你能全部找出来吗，并排除重复的解吗？

下面的关系你能看出来吗？
123 48 6 5 7 90
123 4 8 76 5 90
12 3 5 60 98 74
12 3 6 40 95 87
12 3 6 50 97 84
12 3 6 90 78 45
12 3 6 90 87 54
12 3 8 96 74 50
12 3 9 78 64 50
12 4 6 30 95 87
12 4 6 90 85 37
12 4 8 60 57 39
12 4 8 60 93 75
12 4 8 70 59 36
12 5 6 30 97 84
12 5 6 78 93 40
...

ggggwhw · 发表于 2010-4-27 22:49:38

arr1 = {{123, 48, 6, 5, 7, 90}, {123, 4, 8, 76, 5, 90}, {12, 3, 5, 60,
98, 74}, {12, 3, 6, 40, 95, 87}, {12, 3, 6, 50, 97, 84}, {12, 3,
6, 90, 78, 45}, {12, 3, 6, 90, 87, 54}, {12, 3, 8, 96, 74,
50}, {12, 3, 9, 78, 64, 50}, {12, 4, 6, 30, 95, 87}, {12, 4, 6,
90, 85, 37}, {12, 4, 8, 60, 57, 39}, {12, 4, 8, 60, 93, 75}, {12,
4, 8, 70, 59, 36}, {12, 5, 6, 30, 97, 84}, {12, 5, 6, 78, 93, 40}};
lena1 = Length[arr1];
arr2 = Table[ToString[arr1[[j, k]]], {j, 1, lena1}, {k, 1, 6}];
brr1 = {"==", "+", "-", "*", "/"};
lenb1 = Length[arr1] - 1;
brr2 = Permutations[brr1, {5}];
lenb2 = Length[brr2];
crr = Table[
StringJoin@Riffle[arr2[[j]], brr2[[k]]], {j, 1, lena1}, {k, 1,
lenb2}];
For[j = 1, j <= lena1, j++,
For[k = 1, k <= lenb2, k++,
If[ToExpression@crr[[j, k]], Print[crr[[j, k]]]];
];
];
123==48/6*5-7+90
123-48/6*5+7==90
123==4/8*76-5+90
123-4/8*76+5==90
12==3/5*60-98+74
12-3/5*60+98==74
12==3/6*40-95+87
12-3/6*40+95==87
12==3/6*50-97+84
12-3/6*50+97==84
12==3/6*90-78+45
12-3/6*90+78==45
12==3/6*90-87+54
12-3/6*90+87==54
12==3/8*96-74+50
12-3/8*96+74==50
12==3/9*78-64+50
12-3/9*78+64==50
12/3*9+78-64==50
12==4/6*30-95+87
12-4/6*30+95==87
12==4/6*90-85+37
12-4/6*90+85==37
12==4/8*60-57+39
12-4/8*60+57==39
12==4/8*60-93+75
12-4/8*60+93==75
12==4/8*70-59+36
12-4/8*70+59==36
12==5/6*30-97+84
12+5*6/30==97-84
12-5/6*30+97==84
12==5/6*78-93+40
12-5/6*78+93==40

复制代码

lin2009 · 发表于 2010-4-28 10:15:02

7# chyanog
谢谢，
可能文件的读写比较耗时。

已经用递归的方式改进了排列组合的算法，程序运行1s以内（只显示，不记录到文件）。但是小问题还是倾向于用简单的算法（编程复杂度低）。

lin2009 · 发表于 2010-4-28 10:21:39

本帖最后由 lin2009 于 2010-4-28 10:42 编辑

12# ggggwhw

这里有不少是通过简单的移项操作得到。如1、2和3、4，能否去除这样重复的等式，并找出所有符合条件的方程呢？

123==48/6*5-7+90
123-48/6*5+7==90
123==4/8*76-5+90
123-4/8*76+5==90

Simewe · 发表于 2013-10-9 23:20:15

lin2009 发表于 2010-4-28 10:15
7# chyanog
谢谢，
可能文件的读写比较耗时。

您好，如果用递归怎么写啊？

lin2009 · 发表于 2013-10-10 19:52:48

Simewe 发表于 2013-10-9 23:20
您好，如果用递归怎么写啊？

抱歉，时隔太久找不到源程序等相关资料了。有时间的话，我再看看。

账号		自动登录	找回密码
密码			注册

账号		自动登录	找回密码
密码			立即注册

[欧拉习题] PE[32]:Find the sum of all numbers that can be written as pandigital products.

相关帖子