分油问题

medie2005

一个桶中有C斤油(这个桶的容积足够大)，要求倒出D斤，可现在另外只有两个桶，分别可装A斤与B斤(A,B,D满足: gcd(A,B)|D). 问题: 1): 请写一个高效的算法求出分油步骤.. 2): 记最少分油次数为P(A,B,C,D), 请分析P(A,B,C,D)这个量.

mathe

1)应该不难，主要在于高效要如何去评估，求解的速度呢？还是求出的解的效率呢？中国剩余定理应该是可以用进去的。 关于2)，这里有个问题,其中A,B,D有多大，如果它们的数值不是太大，那么构建一个图就可以了。显然，图的结点数目并不是很多，它们总是，要么A,B之一空，要么A,B之一满（而A,B之中另外一个的状态任意），所以这个图的顶点数目不超过2(A+B+2).而这个图中每个顶点的出度也很少（总共没几种倒法），所以不复杂。 当然，我估计medie是想讨论问题是否可以推广到A,B,D很大的情况，不过我估计很难。倒是我们可以考虑是否存在一种高效的算法（还是i)中的思路），可以找到一个比较优秀的结果。

medie2005

那就改为: 1): 请写一个高效的算法求出最少分油步骤..

无心人

限制下0 < A < B < D < C <= 1000 如何

无心人

实际上，C可以无限 所以上面的限制可以只针对A, B, D

kon3155

经典的量水(倒水)问题！ 【量水问题】 有两个无刻度的量杯A和B，其容积分别为m升和n升(m>n)，现在允许用量杯从水缸里取水或将水倒回水缸里，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量得k升(k

kon3155

1. program liangshui;
2. const
3. max=600000;
4. type
5. tlist=record {结点类型}
6. father:longint;
7. dep:byte;
8. a:integer;
9. b:integer;
10. end;
11. var
12. list:array[0..max] of tlist; {扩展出的中间结点序列}
13. head,foot,best,i:longint;
14. m,n,k:integer;
15. answer:longint;
16. found:boolean;
17. procedure init; {初始化过程}
18. var
19. i:byte;
20. begin
21. assign(input,'ls.in');
22. reset(input);
23. assign(output,'ls.out');
24. rewrite(output);
25. fillchar(list,sizeof(list),0);
26. found:=false;
27. head:=0; {队列初始化,队首指针head,队尾指针foot}
28. foot:=1;
29. with list[1] do {初始结点作为队列第一个结点}
30. begin
31. a:=0;
32. b:=0;
33. dep:=0;
34. father:=0;
35. end;
36. readln(m,n,k)
37. end;
38. function notappear(newv:tlist):boolean; {判断扩展出的结点是否已在队列中的函数}
39. var
40. i:longint;
41. begin
42. notappear:=false;
43. for i:=1 to foot do
44. if (newv.a=list[i].a) and (newv.b=list[i].b)
45. then exit;
46. notappear:=true;
47. end;
48. procedure add(newv:tlist); {往队列中加入新结点过程}
49. begin
50. if notappear(newv)
51. then begin
52. inc(foot);
53. list[foot]:=newv;
54. end;
55. end;
56. procedure expand(index:longint;var oldv:tlist); {扩展结点过程}
57. var
58. i:integer;
59. newv:tlist;
60. begin
61. for i:=1 to 6 do {分别应用6条规则}
62. begin
63. if i=1 then
64. if oldv.a<>0 {把a量筒倒空}
65. then begin newv.a:=0;newv.b:=oldv.b;end;
66. if i=2 then
67. if oldv.a<>m {把a量筒灌满}
68. then begin newv.a:=m;newv.b:=oldv.b;end;
69. if i=3 then
70. if oldv.b<>0 {把b量筒倒空}
71. then begin newv.b:=0;newv.a:=oldv.a;end;
72. if i=4 then
73. if oldv.a<>n {把b量筒灌满}
74. then begin newv.a:=n;newv.a:=oldv.a;end;
75. if i=5 then
76. if (oldv.a<>0) and (oldv.b<>n) {把a量筒往b量筒倒水}
77. then if oldv.a+oldv.b>=n {判断a往b倒时b能否全部装下}
78. then begin newv.b:=n;newv.a:=oldv.a-(n-oldv.b);end
79. else begin newv.a:=0;newv.b:=oldv.a+oldv.b;end;
80. if i=6 then
81. if (oldv.a<>m) and (oldv.b<>0) {把b量筒往a量筒倒水}
82. then if oldv.a+oldv.b>=m {判断b往a倒时a能否全部装下}
83. then begin newv.a:=m;newv.b:=oldv.b-(m-oldv.a);end
84. else begin newv.b:=0;newv.a:=oldv.a+oldv.b;end;
85. newv.father:=index;
86. newv.dep:=oldv.dep+1;
87. add(newv);
88. end;
89. end;
90. procedure print(index:longint); {递归打印路径}
91. var
92. i,j:byte;
93. begin
94. if index=0 then exit;
95. print(list[index].father);
96. writeln(list[index].a,' ',list[index].b);
97. end;
98. begin{main}
99. init;
100. repeat
101. inc(head);
102. if list[head].a=k {比较是否跟目标相同,相同则找到,否则扩展新结点}
103. then begin
104. found:=true;
105. best:=list[head].dep;
106. answer:=head;
107. break;
108. end;
109. if list[foot].dep>100
110. then begin
111. writeln('OverTime!');
112. break;
113. end;
114. expand(head,list[head]);
115. {writeln(list[head].a,' ',list[head].b);}
116. until (head>=foot) or (foot>max) or found;
117. if found
118. then begin
119. writeln(best);
120. print(answer);
121. end
122. else writeln('No Answer');
123. close(input);
124. close(output);
125. end.

复制代码

mathe

呵呵，你这个复杂度太小了。我上面描述的方法算法复杂度也就O((A+B)log(A+B)). 还有D不应该比A,B大，而是通常小于max(A,B).

litaoye

我觉得这题有个问题,比如A=5,B=6,D=12可能就无解了,因为没有另外一个空桶可供装油! 那个C的容量,可能也会影响最优解 如果只有这2个桶的话,普通搜索方法也挺简单的,可能需到多几个桶才能体现出效率的重要

无心人

精确点 有无限容量桶C 容量A, B桶A, B 现在要凑出容量D的油 如何操作步骤最少？