求算法！！~~(100分)

智

智者乐水

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #1

有0~9 十个数字,用它们组合成3个数A,B,C.使得A*C=B;输出所有满足条件的组合!
组合规则:每个数字只能用一次,并且0~9全用晚.(如A=123,B=4567,C=890
他的算法怎么解决？

 

W

whitehorse

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #2

想想

 

智

智者乐水

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #3

我这有一点思路，大家参考一下：
共有0-9十个数，也就是说共有十位
要两个数相乘得第三个就只有
1位X4位=5位 或 2位X3位=5位
再分情况考虑，但是还是太多
最后总要一个个试，大家有没更好的方法呢？

 

W

whitehorse

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #4

你没有限制位数,会有无数个结果的
如果限制ac都是不超过3位,算法如下,未及细想,你找这样的算法玩啊?
for i:=0 to 999
for j:=0 to 999
for k:=0 to length(i)
for l:=0 to length(j)
begin
if copy(inttostr(i),k,1)=copy(inttostr(j),l,1) then
continue;
for m:=0 to length(i*j)
begin
if copy(inttostr(i*j),m,1)=copy(inttostr(i),k,1) then
continue;
if copy(inttostr(i*j),m,1)=copy(inttostr(j),l,1) then
continue;
write(i,i*j,j);
end;

end;

 

智

智者乐水

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #5

to whitehorse：
只能A为1位C为4位 或a为2位c为3位（因为只有十位么）
每个数字只能用一次，如果用了0 以后的数字就不能再用0了
我的想法是做一个标志位，记录是否已经用过这个数了
如果没用过就可以再用，如果已经用过就不再用
另： copy函数是怎么用的，功能是什么，很久没用delphi了

 

L

longquestion

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #6

根据楼上所说，我想可以就这样做了，本人delphi语法还不是很精通，你们凑合看吧
定义一个10*10的整形数组后里面存放0~9这10个数的全排列后
for i:=1 to 10do
if a[6]*10000+a[7]*1000+a[8]*100+a[9]*10+a[10]=a[1]*(a[2]*1000+a[3]*100+a[4]*10+a[5])
then
print(a[1],"*",(a[2]*1000+a[3]*100+a[4]*10,"=",a[6]*10000+a[7]*1000+a[8]*100+a[9]*10+a[10]=);
是不是有点乱呀，我刚学帮帮忙

 

W

whitehorse

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #7

copy是取子字符串的函数,copy('123',2,1)取‘2’
如果限制ABC三个数总位数只能是十位,用我前面的循环也行,再加一个判断就可以以
if length(inttostr(i))+length(inttostr(j))+length(inttostr(k))<>10 then
continue

 

H

huasoft

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-07

• #8

　　不难证明B只能是5位数，而A、C只能是2位数和3位数，由于AC的对称性，问题可以简化为：
A（2位数）＊B（3位数）＝C（5位数）ABC由0－9的数字组成。
可枚举A、B的所有可能组合，检查与它们的积C是否由0－9的数字组成。
因是算法讨论，不必贴源程序了。

 

L

lldhz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-08

• #9

>>不难证明B只能是5位数，而A、C只能是2位数和3位数，由于AC的对称性，问题可以简化为：
>>A（2位数）*B（3位数）＝C（5位数）ABC由0－9的数字组成。
有这个作为前提好做多了！因为每个数字只能用一次,并且0~9全用完
现在我们换过来A（3位）*B（2位）=C（5位）->A*B1*10+A*B2=C（B1，B2为B的两位）—>
(a1*100+a2*10+a3)(b1*10+b2)=C1*10000+C2*1000+C3*100+C4*10+C5-->
a1*b1*1000+a2*b1*100+a3*b1*10
+a1*b2*100+a2*b2*10+a3*b2
=c1*10000+c2*1000+c3*100+c4*10+c5
--> c1 =[a1*b1/10]//([]为取整）
c2 =mod(a1*b1,10)+[(a2*b1+a1*b2)/10]
c3 =mod(a2*b1+a1*b2,10)+[(a3*b1+a2*b2)/10]
c4 =mod(a3*b1+a2*b2,10)+[(a3*b2)/10]
c5 =mod(a3*b2,10)
c1<>0
做5个循环，判断就可以了

 

智

智者乐水

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-08

• #10

lldhz 写的和我想的差不多
本来是想把c的位数一个个取出来
看来不用取也可以求出来
嘿嘿
大家还有没更好的方法

 

智

智者乐水

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-10

• #11

多人接受答案了。