简单填数--极限玩法

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了。