分油问题
一个桶中有C斤油(这个桶的容积足够大)，要求倒出D斤，可现在另外只有两个桶，分别可装A斤与B斤(A,B,D满足: gcd(A,B)|D).问题:
1):请写一个高效的算法求出分油步骤..
2):记最少分油次数为P(A,B,C,D), 请分析P(A,B,C,D)这个量. 1)应该不难，主要在于高效要如何去评估，求解的速度呢？还是求出的解的效率呢？中国剩余定理应该是可以用进去的。
关于2)，这里有个问题,其中A,B,D有多大，如果它们的数值不是太大，那么构建一个图就可以了。显然，图的结点数目并不是很多，它们总是，要么A,B之一空，要么A,B之一满（而A,B之中另外一个的状态任意），所以这个图的顶点数目不超过2(A+B+2).而这个图中每个顶点的出度也很少（总共没几种倒法），所以不复杂。
当然，我估计medie是想讨论问题是否可以推广到A,B,D很大的情况，不过我估计很难。倒是我们可以考虑是否存在一种高效的算法（还是i)中的思路），可以找到一个比较优秀的结果。 那就改为:
1):请写一个高效的算法求出最少分油步骤.. 限制下0 < A < B < D < C <= 1000
如何 实际上，C可以无限
所以上面的限制可以只针对A, B, D 经典的量水(倒水)问题！
【量水问题】
有两个无刻度的量杯A和B，其容积分别为m升和n升(m>n)，现在允许用量杯从水缸里取水或将水倒回水缸里，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量得k升(k<n<m)所需的最少操作步数。 (每一个取水或倒水都算一个操作步数)
【输入文件】ls.in
仅一行，三个数，分别为m,n,k。
【输出文件】ls.out
仅一行，为最少步数。
【样例数据】
【输入】
4 3 2
【输出】
6
【提示:可以利用宽度搜索求解】
【参考程序】见楼下 program liangshui;
const
max=600000;
type
tlist=record {结点类型}
father:longint;
dep:byte;
a:integer;
b:integer;
end;
var
list:array of tlist; {扩展出的中间结点序列}
head,foot,best,i:longint;
m,n,k:integer;
answer:longint;
found:boolean;
procedure init; {初始化过程}
var
i:byte;
begin
assign(input,'ls.in');
reset(input);
assign(output,'ls.out');
rewrite(output);
fillchar(list,sizeof(list),0);
found:=false;
head:=0; {队列初始化,队首指针head,队尾指针foot}
foot:=1;
with list do {初始结点作为队列第一个结点}
begin
a:=0;
b:=0;
dep:=0;
father:=0;
end;
readln(m,n,k)
end;
function notappear(newv:tlist):boolean;{判断扩展出的结点是否已在队列中的函数}
var
i:longint;
begin
notappear:=false;
for i:=1 to foot do
if (newv.a=list.a) and (newv.b=list.b)
then exit;
notappear:=true;
end;
procedure add(newv:tlist); {往队列中加入新结点过程}
begin
if notappear(newv)
then begin
inc(foot);
list:=newv;
end;
end;
procedure expand(index:longint;var oldv:tlist);{扩展结点过程}
var
i:integer;
newv:tlist;
begin
for i:=1 to 6 do {分别应用6条规则}
begin
if i=1 then
if oldv.a<>0 {把a量筒倒空}
then begin newv.a:=0;newv.b:=oldv.b;end;
if i=2 then
if oldv.a<>m {把a量筒灌满}
then begin newv.a:=m;newv.b:=oldv.b;end;
if i=3 then
if oldv.b<>0 {把b量筒倒空}
then begin newv.b:=0;newv.a:=oldv.a;end;
if i=4 then
if oldv.a<>n {把b量筒灌满}
then begin newv.a:=n;newv.a:=oldv.a;end;
if i=5 then
if (oldv.a<>0) and (oldv.b<>n) {把a量筒往b量筒倒水}
then if oldv.a+oldv.b>=n {判断a往b倒时b能否全部装下}
then begin newv.b:=n;newv.a:=oldv.a-(n-oldv.b);end
else begin newv.a:=0;newv.b:=oldv.a+oldv.b;end;
if i=6 then
if (oldv.a<>m) and (oldv.b<>0) {把b量筒往a量筒倒水}
then if oldv.a+oldv.b>=m {判断b往a倒时a能否全部装下}
then begin newv.a:=m;newv.b:=oldv.b-(m-oldv.a);end
else begin newv.b:=0;newv.a:=oldv.a+oldv.b;end;
newv.father:=index;
newv.dep:=oldv.dep+1;
add(newv);
end;
end;
procedure print(index:longint); {递归打印路径}
var
i,j:byte;
begin
if index=0then exit;
print(list.father);
writeln(list.a,' ',list.b);
end;
begin{main}
init;
repeat
inc(head);
if list.a=k {比较是否跟目标相同,相同则找到,否则扩展新结点}
then begin
found:=true;
best:=list.dep;
answer:=head;
break;
end;
if list.dep>100
then begin
writeln('OverTime!');
break;
end;
expand(head,list);
{writeln(list.a,' ',list.b);}
until (head>=foot) or (foot>max) or found;
if found
then begin
writeln(best);
print(answer);
end
else writeln('No Answer');
close(input);
close(output);
end.
呵呵，你这个复杂度太小了。我上面描述的方法算法复杂度也就O((A+B)log(A+B)).
还有D不应该比A,B大，而是通常小于max(A,B). 我觉得这题有个问题,比如A=5,B=6,D=12可能就无解了,因为没有另外一个空桶可供装油!
那个C的容量,可能也会影响最优解
如果只有这2个桶的话,普通搜索方法也挺简单的,可能需到多几个桶才能体现出效率的重要 精确点
有无限容量桶C
容量A, B桶A, B
现在要凑出容量D的油
如何操作步骤最少？
页:
[1]
2