4 1 7 6 2 5 8 2 3 9 4 1 7 6求解次序: 1 11 17 4 7 19 9 2 15 13 5 12 18 6 8 20 10 3 16 14 。Р根据程序运行结果画出图中顶点到各顶点的最短通路,如图7中粗线所示。其中,方框中的数字是到各顶点最短通路的长。Р由图8可见,从顶点到顶点的最短路径为:Р如图8所示,这条最短路径的长是9,即从原始状态出发,按照这条最短通路所表示的次序倒油9次,就可以用最快的速度把油分完。Р图7 到各顶点的最短通路Р图8 顶点到的最短通路Р七、模型推广Р对于这个分油问题,可以推广出当A、B、C所能装的油的重量为a、b、c斤,a﹥b﹥c;现在A中装满a斤油,B,C均为空,如何利用三个瓶子将a油分成二等分?Р当c=1时,自然可将油分出1——b斤,我们对c﹥1的情形进行讨论,通过图2,我们发现分油的步骤是有规律的,即规定:Р(1)?B中若空,则A向B倒油;Р(2)?若B不空,从B向C倒油;Р(3)?若C满了,就把C倒向A。РB中油量x的变化与倒油的操作有关,则设,即()。Р我们将按以上规定对b中油量x作如下具体分析:Р1)由A倒满B后,B中的油量为x=b斤;Р2)由B向C倒次油后(i∈N),B中的油量为斤,当i足够大时,B的油量为斤;Р3)将B中的斤油倒向C,此时C中有油斤油;Р4)重复1)、2),B中的油量,即斤油;重复3),此时C中有油y= f(λ)斤。Р5)如此反复次(,可看作B曾被倒满n次)可知B中有油时,可将a分成二等分;另外,当x=nf(λ)=1,即b-1= kc时,B中油量为x=nf(λ)(n=0,1,2,3…c-1)斤,由b-1= kc => ( b-1) f(λ)=0 =>n(b -1) f(λ)=0 =>nb f(λ)= n即x=n可知在b中能分0,1,2,3…c-1斤油,即c ,c+1…ck=b-1*b斤油。
全文预览
