女王的数字问题

[Caravel]

算了多久？

可能5秒？

[CalCat]

有很多解 1279个，而且似乎有些数字，排列组合之后还是成立

9 * 85347261 = 768125349
9 * 85372461 = 768352149
9 * 85436127 = 768925143
9 * 85461372 = 769152348
9 * 85473126 = 769258134
9861 * 23475 = 231486975
9864 * 13752 = 135649728
9864 * 17532 = 172935648
9864 * 25137 = 247951368
9864 * 52137 = 514279368
9 * 87146325 = 784316925
9 * 87325146 = 785926314
9873 * 54612 = 539184276

我的很笨的code

import itertools

a = "123456789"

def test_num(x):
if x > 987654321 or x < 1234567:
return False
x = str(x)
if "0" in x:
return False
b = set([c for c in x])
return len(b) == 9

sol = []
for s in itertools.permutations(a):
s1 = "".join(s)
for i in range(1, 4):
c = int(s1[0:i])
d = int(s1[i:])
if (c > d):
continue
e = c * d
if (test_num(e)):
print ("{} * {} = {}".format(c, d, e))
sol.append((c, d, e))

这程序漂亮， 但是我运行通不过，看如下个问题：
File "<ipython-input-14-57c78a3f0187>", line 6
if x > 987654321 or x < 1234567:
^
IndentationError: expected an indented block
你能不能把程序再格式化一下？我再试试。非常感谢

[meiyoumajia]

为啥要“除123456789等共362880个数”， 乘完检查一下数字不就行了。

p=a*b

两个原因：
1。那样做判断会更直接，减少次数。那就是找一个整数的整数因子的基本算法。
2。在最底下，乘除应该是没有根本区别的。都是对一个数（除时p或（乘时a和b中一个））的2进制的byte做shift的操作。

其实还可以优化。

p = a * b

Since the sum of all of p's digits are 45, so p is a multiple of 9.
1. Both a and b are multiples of 3.
OR
2. Either a or b is a multiple of 9, so the sum of all of the other's digits is a multiple of 9, so the other is also a multiple of 9.
So, 1 holds for all a and b.

因为p/b在之前本来没有什么规律性，利用次性质，可以把运算次数减少到原来的1/3*1/3=1/9左右。
可能在2.2亿次。

还可以按下面继续优化：
A。用multi-thread做。现在普通的pc都有4-core或更多，最多会支持4或5-6个threads（？），用两个threads就可以减少差不多一半。把其它的applications尽量关掉。

B。如果懒得去那样做，直接run 两个子问题也行。

可能还有进一步优化的算法。

这个题目的结果太多，因此本身没有实际意义。但是作为介绍几种（数字或算法的）基本性质还是很不错的。昨天我就决定用以上的思路，在有时间时把它演示给小孩看。我家有4台mac （3个pro，其中一个是老婆要上交的老pro，还有1个book）。因此可以大概看出上面的A和B的差别是多少，但不一定会去做这个。应该会去试方法A。

[meiyoumajia]

可能5秒？

wow！真快。
你利用了小的乘数位数不超过4。

在机器和操作系统上的已经做到的优化真是太厉害了。20年前我试过自己优化几种基本的sort，怎么做都比系统上有的sort差了很多。

[Caravel]

整数分解肯定要难多了，我是把两个乘数的组合，一一验证一下，就9！x 4 个

p=a*b

两个原因：
1。那样做判断会更直接，减少次数。那就是找一个整数的整数因子的基本算法。
2。在最底下，乘除应该是没有根本区别的。都是对一个数（除时p或（乘时a和b中一个））的2进制的byte做shift的操作。

其实还可以优化。

p = a * b

Since the sum of all of p's digits are 45, so p is a multiple of 9.
1. Both a and b are multiples of 3.
OR
2. Either a or b is a multiple of 9, so the sum of all of the other's digits is a multiple of 9, so the other is also a multiple of 9.
So, 1 holds for all a and b.

因为p/b在之前本来没有什么规律性，利用次性质，可以把运算次数减少到原来的1/3*1/3=1/9左右。
可能在2.2亿次。

还可以按下面继续优化：
A。用multi-thread做。现在普通的pc都有4-core或更多，最多会支持4或5-6个threads（？），用两个threads就可以减少差不多一半。把其它的applications尽量关掉。

B。如果懒得去那样做，直接run 两个子问题也行。

可能还有进一步优化的算法。

这个题目的结果太多，因此本身没有实际意义。但是作为介绍几种（数字或算法的）基本性质还是很不错的。昨天我就决定用以上的思路，在有时间时把它演示给小孩看。我家有4台mac （3个pro，其中一个是老婆要上交的老pro，还有1个book）。因此可以大概看出上面的A和B的差别是多少，但不一定会去做这个。应该会去试方法A。

[meiyoumajia]

整数分解肯定要难多了，我是把两个乘数的组合，一一验证一下，就9！x 4 个

那其实与乘除本身没有关系。
你用的是
a>b
b的位数最多是4。
这个相当不错。我竟然没有想到（还是被老办法套住了）。我把我之前的思路，也用这个性质可以去改善。
如果到某个更高进制，可能就要优化了。

[CalCat]

Hi, Caravel, 你能把这个程序格式化下， 让我试试？
初学者

[Caravel]

Hi, Caravel, 你能把这个程序格式化下， 让我试试？
初学者

FT，几个indentation你自己弄一下不就行了，就当是homework了。

[CalCat]

我不知道再哪里indentation， 你搞一下，非常感谢

[meiyoumajia]

“if x > 987654321 or x < 1234567:”
结尾的7后应该有89？

“
if (c > d):
continue
”

现在做的是10进制，这个没有用处。但是对11进制或更高的奇数进制就有用了

你的次数是：9！*4=1451520
1.45百万
如果是几秒的话，那每秒做了几千次。我已经很多年不作大计算，没有去查操作有多快了。计算能力真是进步太快了。

[Caravel]

“if x > 987654321 or x < 1234567:”
结尾的7后应该有89？

“
if (c > d):
continue
”

现在做的是10进制，这个没有用处。但是对11进制或更高的奇数进制就有用了

你的次数是：9！*4=1451520
1.45百万
如果是几秒的话，那每秒做了几千次。我已经很多年不作大计算，没有去查操作有多快了。计算能力真是进步太快了。

哦，写错了，不过那个就是稍微加快点，去掉后面那个check也可以兜底。 百万次对现在的计算机很容易吧，现在的CPU的GHZ的处理器，百万个loop，1个loop可以跑1000个cycle的operation。

[CalCat]

别作这些无意义的题目。我有许多现实社会里面的有使用价值的题目，非常有趣。你先帮我把python搞定，我给你们贴出来。

[verdelite]

FT，几个indentation你自己弄一下不就行了，就当是homework了。

你们不熟悉这个BBS，我上次贴程序发现需要选择一个保持format 的按钮，按钮会加[ pre][ /pre]，就可以搞定了。我已经帮edit搞定了。

[CalCat]

你们不熟悉这个BBS，我上次贴程序发现需要选择一个保持format 的按钮，按钮会加[ pre][ /pre]，就可以搞定了。我已经帮edit搞定了。

Very good! Thank you, a million times!

[meiyoumajia]

如果楼主之前用“传统”的找因子办法，其它地方与Caravel的相同，那就大概需要

25.5亿/1.45百万*（5至6秒）
= 10551秒
=2.9小时

几个小时左右

但如果楼主用的那些置换等操作没有用系统提供的工具，效率就差了很多。
因此，通常，如果系统提供了可用工具，那就尽量用。 比自己写的要优化（即使自己或通过系统外的工具优化了自己的程序）。这就是我之前说的那种（多年前我测试出的）情况。