查看完整版本: “所罗门塔”问题

“所罗门塔”问题

<P>朋友为了工作需要建立了一种数据库存放数字，每次储存数据只能存比库内数字都大的数，每次读取数据也只能读库内数字中最大的数。

问题1：假设现在有3个这样数据库(A)、(B)、(C)，数据库(A)中有100个数字依序排列:1,2,...,100。现在需要将(A)中的数字转移到(B)，请问最少需要多少次转移？
提示：
1）读取并存储算一次转移指令。
2）可以使用(C)作为中转库。
3）准备的3个数据库都可以重复存储和读取。
4）只能在数据库之间转移，不能使用外部纪录方式。

问题2：如果(A)中有N个数据都不相同且都可比大小，最少需要多少次能够全部转移到(B)中？ </P>

<P>问题1：是99！*3</P><P>问题2：是（N-1）！*3</P>

2^N-1

[quote]<B>以下是引用<I>txs132</I>在2004-8-10 3:00:54的发言：</B>
2^N-1[/quote]

假如N=3，怎么移？

<P>1. A-B</P><P>2. A-C</P><P>3. B-C</P><P>4. A-B</P><P>5. C-A</P><P>6. C-B</P><P>7. A-B</P>

我错了

[quote]<B>以下是引用<I>txs132</I>在2004-8-10 3:00:54的发言：</B>
2^N-1[/quote]

同意