简单填数--极限玩法

wayne

要把1-9这9个数全部填进去，一个萝卜一个坑，使得等式成立
$frac{\square}{\square\square}+frac{\square}{\square\square}+frac{\square}{\square\square}=1$

我找不到好的算法，结果用Mathematica花了8秒钟，而用1stopt却只需1秒钟，所以想问问大家，有没有好点子，实现快速填数

KeyTo9_Fans

设9个数分别是

a、b、c、d、e、f、g、h、i

$a$、$b$、$c$、$d$、$e$、$f$、$g$、$h$、$i$

于是有

a/(10b+c)+d/(10e+f)+g/(10h+i)=1

$a/(10b+c)+d/(10e+f)+g/(10h+i)=1$

通分

a(10e+f)(10h+i)+d(10b+c)(10h+i)+g(10b+c)(10e+f)=(10b+c)(10e+f)(10h+i)

$a(10e+f)(10h+i)+d(10b+c)(10h+i)+g(10b+c)(10e+f)=(10b+c)(10e+f)(10h+i)$

展开

100aeh+10aei+10afh+afi+100bdh+10bdi+10cdh+cdi+100beg+10bfg+10ceg+cfg=1000beh+100bei+100bfh+100ceh+10bfi+10cei+10cfh+cfi

$100aeh+10aei+10afh+afi+100bdh+10bdi+10cdh+cdi+100beg+10bfg+10ceg+cfg=1000beh+100bei+100bfh+100ceh+10bfi+10cei+10cfh+cfi$

竟然没有同类项。

按系数收集

1000beh+100(bei+bfh+ceh-aeh-bdh-beg)+10(bfi+cei+cfh-aei-afh-bdi-cdh-bfg-ceg)+(afi+cdi+cfg-cfi)=0

$1000beh+100(bei+bfh+ceh-aeh-bdh-beg)+10(bfi+cei+cfh-aei-afh-bdi-cdh-bfg-ceg)+(afi+cdi+cfg-cfi)=0$

没有得到任何有用信息。

唯一可利用的是

(afi+cdi+cfg-cfi) mod 10 =0

$(afi+cdi+cfg-cfi) mod 10 =0$

只需枚举

a、c、d、f、g、i

$a$、$c$、$d$、$f$、$g$、$i$

枚举量为原来的

1/6

$1/6$

其中大约有

1/10

$1/10$

符合条件。

然后再考虑

b、e、h

$b$、$e$、$h$

的值，代入原式，看看是否符合条件。

累计枚举量为

9*8*7*6*5*4 + 9*8*7*6*5*4/10*6 = 96768

$9*8*7*6*5*4 + 9*8*7*6*5*4/10*6 = 96768$

是直接枚举量

9! = 362880

$9! = 362880$

的

4/15

$4/15$

。

northwolves

9/12+5/34+7/68=1
第一个分母的十位数只能是1:

因为如果是二十几,分式和最大只能为 9/21+8/34+7/56=0.789<<1

northwolves

又: 9/21+8/35+7/46=0.809317<1

northwolves

另:

a/x+b/y+c/z=1------->
axbycz是123456789的一个排列
ayz+bxz+cxy=xyz
用乘法应该比除法快多了

wayne

9/12+5/34+7/68=1
第一个分母的十位数只能是1:

因为如果是二十几,分式和最大只能为 9/21+8/34+7/56=0.789
northwolves 发表于 2010-1-5 15:35

呵呵，这个信息很关键，一下子减少到1/9了

另外，由于三个分数形式相同，我们不妨先人为设定一下关系，三个分数的分子依次递增，这样，又可省到1/6，于是运算量减少到了1/54了。