【题目描述】 设有大小不等的3个无刻度的油桶，分别能够存满，X，Y，Z公升油。初始时，第一个油桶盛满油，第二、三个油桶为空。编程寻找一种最少步骤的分油方式，在某一个油桶上分出targ升油。若找到解，则将分油方法打印出来，否则输出“No Answer!”。 【输入格式】 一行4个整数，依次表示X，Y，Z，targ，每个数之间用一个空格隔开 【输出格式】 表示解的情况，如果无解输出“No Answer!”，如果有解，则输出分油方法（每一步三个油桶的状态），如果解不唯一也只有输出任一个解 【样例输入】 80 50 30 40 【样例输出】 80 0 0 30 50 0 30 20 30 60 20 0 60 0 20 10 50 20 10 40 30 【分析】 广搜，每次搜索6种倒油方案： A–>B A–>C B–>A B–>C C–>A C–>B
var q:array[0..10001,1..4]of longint; tar:array[1..3]of longint; targ,head,tail,flag:longint; procedure move(a,b,c:longint); var i:longint; begin inc(tail); if q[head,a]+q[head,b]>tar[b] then begin q[tail,a]:=q[head,a]+q[head,b]-tar[b]; q[tail,b]:=tar[b]; end else begin q[tail,a]:=0; q[tail,b]:=q[head,a]+q[head,b]; end; q[tail,c]:=q[head,c]; q[tail,4]:=head; for i:=1 to tail-1 do if (q[tail,1]=q[i,1])and(q[tail,2]=q[i,2]) then begin dec(tail);exit; end; if (q[tail,a]=targ)or(q[tail,b]=targ) then flag:=1; end; procedure print(step:longint); begin if q[step,4]<>0 then print(q[step,4]); writeln(q[step,1],' ',q[step,2],' ',q[step,3]); end; begin read(tar[1],tar[2],tar[3],targ); q[1,1]:=tar[1]; q[1,2]:=0; q[1,3]:=0; q[1,4]:=0; flag:=0; head:=1;tail:=1; while (head<=tail)and(flag=0) do begin if (q[head,1]>0)and(flag=0) then move(1,2,3); if (q[head,1]>0)and(flag=0) then move(1,3,2); if (q[head,2]>0)and(flag=0) then move(2,1,3); if (q[head,2]>0)and(flag=0) then move(2,3,1); if (q[head,3]>0)and(flag=0) then move(3,1,2); if (q[head,3]>0)and(flag=0) then move(3,2,1); inc(head); end; if head>tail then begin write('No Answer!');exit; end; print(tail); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533547.html
相关资源：小孩分油问题(广度优先搜索算法)实验报告及c 程序