简单填数--极限玩法
要把1-9这9个数全部填进去，一个萝卜一个坑，使得等式成立frac{\square}{\square\square}+frac{\square}{\square\square}+frac{\square}{\square\square}=1
我找不到好的算法，结果用Mathematica花了8秒钟，而用1stopt却只需1秒钟，所以想问问大家，有没有好点子，实现快速填数 设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$
。 9/12+5/34+7/68=1
第一个分母的十位数只能是1:
因为如果是二十几,分式和最大只能为 9/21+8/34+7/56=0.789<<1 又: 9/21+8/35+7/46=0.809317<1 另:
a/x+b/y+c/z=1------->
axbycz是123456789的一个排列
ayz+bxz+cxy=xyz
用乘法应该比除法快多了 9/12+5/34+7/68=1
第一个分母的十位数只能是1:
因为如果是二十几,分式和最大只能为 9/21+8/34+7/56=0.789
northwolves 发表于 2010-1-5 15:35 http://bbs.emath.ac.cn/images/common/back.gif
呵呵，这个信息很关键，一下子减少到1/9了
另外，由于三个分数形式相同，我们不妨先人为设定一下关系，三个分数的分子依次递增，这样，又可省到1/6，于是运算量减少到了1/54了。
页:
[1]