level 1
songxz123
楼主
分油问题,请教高手指点:
有A,B,C三个油桶,容量分别为8升,5升,3升,A桶里装了8升油,现在要求借助着3个桶将8升油分成2个4升。注意,桶内没有刻度,因此无法认为控制倒入倒出的数量。每次倒油时,只能有两种情况:将原桶倒空(当原桶油量小于等于目标桶剩余容积时)或将目标桶倒满(当源桶油量大于等于目标桶剩余容积时)。
program fenyou;
const
stacksize=64;
type
tstate=array[1..3] of integer;
tstackstruc=record
state:tstate;
branchcode:integer;
end;
var
a,b:tstate;
stack:array[1..stacksize] of tstackstruc;
stacktop:integer;
foundnewstate:boolean;
i:integer;
function equal(state1,state2:tstate):boolean;
begin
if (state1[1]=state2[1]) and
(state1[2]=state2[2]) and
(state1[3]=state2[3])
then
equal:=true
else
equal:=false;
end;
procedure push(astate:tstate;acode:integer);
begin
stacktop:=stacktop+1;
stack[stacktop].state:=astate;
stack[stacktop].branchcode:=acode;
end;
procedure pop(var astate:tstate;var acode:integer);
begin
if stacktop>0
then
begin
astate:=stack[stacktop].state;
acode:=stack[stacktop].branchcode;
stacktop:=stacktop-1;
end;
end;
procedure createnewstate(state:tstate;var newstate:tstate;code:integer);
begin
newstate:=state;
case code of
1 :if state[1]>=(5-state[2])
then
begin
newstate[1]:=state[1]-(5-state[2]);
newstate[2]:=5;
end
else
begin
newstate[2]:=state[2]+state[1];
newstate[1]:=0;
end;
2 : if state[1]>=(3-state[3])
then
begin
newstate[1]:=state[1]-(3-state[3]);
newstate[3]:=3;
end
else
begin
newstate[3]:=state[3]+state[1];
newstate[1]:=0;
end;
3: if state[2]>=state[2]-(8-state[1])
then
begin
newstate[2]:=state[1]+state[2];
newstate[1]:=8;
end
else
begin
newstate[1]:=state[1]+state[2];
newstate[2]:=0;
end;
4: if state[2]>=(3-state[3])
then
begin
newstate[2]:=state[2]-(3-state[3]);
newstate[3]:=3;
end
else
begin
newstate[3]:=state[3]+state[2];
newstate[2]:=0;
end;
5: if state[3]>=(8-state[1])
then
begin
newstate[3]:=state[3]-(8-state[1]);
newstate[1]:=8;
end
else
begin
newstate[1]:=state[3]+state[1];
newstate[3]:=0;
end;
6: if state[3]>=(5-state[2])
then
begin
newstate[3]:=state[3]-(5-state[2]);
newstate[2]:=5;
end
else
begin
newstate[2]:=state[2]+state[3];
newstate[3]:=0;
end;
end;{case}
end;
function InStack(astate:tstate):boolean;
var
i:integer;
begin
instack:=false;
for i:=1 to stacktop do
if equal(stack[i].state,astate)
then
begin
instack:=true;
break;
end;
end;
begin
a[1]:=8;
a[2]:=0;
a[3]:=0;
i:=1;
stacktop:=0;
while not ((a[1]=4) and (a[2]=4) and (a[3]=0)) do
begin
foundnewstate:=false;
while (not foundnewstate) and ( i<=6) do
begin
createnewstate(a,b,i);
if instack(b) or equal(a,b)
then
i:=i+1
else
foundnewstate:=true;
end;
if foundnewstate
then
begin
push(a,i);
a:=b;
i:=1;
end
else
begin
pop(a,i);
i:=i+1;
end;
end;
push(a,i);
writeln('***');
for i:=1 to stacktop do
with stack[i] do
writeln(state[1],',',state[2],',',state[3]);
end.
2014年05月28日 12点05分
1
有A,B,C三个油桶,容量分别为8升,5升,3升,A桶里装了8升油,现在要求借助着3个桶将8升油分成2个4升。注意,桶内没有刻度,因此无法认为控制倒入倒出的数量。每次倒油时,只能有两种情况:将原桶倒空(当原桶油量小于等于目标桶剩余容积时)或将目标桶倒满(当源桶油量大于等于目标桶剩余容积时)。
program fenyou;
const
stacksize=64;
type
tstate=array[1..3] of integer;
tstackstruc=record
state:tstate;
branchcode:integer;
end;
var
a,b:tstate;
stack:array[1..stacksize] of tstackstruc;
stacktop:integer;
foundnewstate:boolean;
i:integer;
function equal(state1,state2:tstate):boolean;
begin
if (state1[1]=state2[1]) and
(state1[2]=state2[2]) and
(state1[3]=state2[3])
then
equal:=true
else
equal:=false;
end;
procedure push(astate:tstate;acode:integer);
begin
stacktop:=stacktop+1;
stack[stacktop].state:=astate;
stack[stacktop].branchcode:=acode;
end;
procedure pop(var astate:tstate;var acode:integer);
begin
if stacktop>0
then
begin
astate:=stack[stacktop].state;
acode:=stack[stacktop].branchcode;
stacktop:=stacktop-1;
end;
end;
procedure createnewstate(state:tstate;var newstate:tstate;code:integer);
begin
newstate:=state;
case code of
1 :if state[1]>=(5-state[2])
then
begin
newstate[1]:=state[1]-(5-state[2]);
newstate[2]:=5;
end
else
begin
newstate[2]:=state[2]+state[1];
newstate[1]:=0;
end;
2 : if state[1]>=(3-state[3])
then
begin
newstate[1]:=state[1]-(3-state[3]);
newstate[3]:=3;
end
else
begin
newstate[3]:=state[3]+state[1];
newstate[1]:=0;
end;
3: if state[2]>=state[2]-(8-state[1])
then
begin
newstate[2]:=state[1]+state[2];
newstate[1]:=8;
end
else
begin
newstate[1]:=state[1]+state[2];
newstate[2]:=0;
end;
4: if state[2]>=(3-state[3])
then
begin
newstate[2]:=state[2]-(3-state[3]);
newstate[3]:=3;
end
else
begin
newstate[3]:=state[3]+state[2];
newstate[2]:=0;
end;
5: if state[3]>=(8-state[1])
then
begin
newstate[3]:=state[3]-(8-state[1]);
newstate[1]:=8;
end
else
begin
newstate[1]:=state[3]+state[1];
newstate[3]:=0;
end;
6: if state[3]>=(5-state[2])
then
begin
newstate[3]:=state[3]-(5-state[2]);
newstate[2]:=5;
end
else
begin
newstate[2]:=state[2]+state[3];
newstate[3]:=0;
end;
end;{case}
end;
function InStack(astate:tstate):boolean;
var
i:integer;
begin
instack:=false;
for i:=1 to stacktop do
if equal(stack[i].state,astate)
then
begin
instack:=true;
break;
end;
end;
begin
a[1]:=8;
a[2]:=0;
a[3]:=0;
i:=1;
stacktop:=0;
while not ((a[1]=4) and (a[2]=4) and (a[3]=0)) do
begin
foundnewstate:=false;
while (not foundnewstate) and ( i<=6) do
begin
createnewstate(a,b,i);
if instack(b) or equal(a,b)
then
i:=i+1
else
foundnewstate:=true;
end;
if foundnewstate
then
begin
push(a,i);
a:=b;
i:=1;
end
else
begin
pop(a,i);
i:=i+1;
end;
end;
push(a,i);
writeln('***');
for i:=1 to stacktop do
with stack[i] do
writeln(state[1],',',state[2],',',state[3]);
end.
