Программа из задачника на перестановки

evg

Задание:

У нас есть 3 чашки с максимальными объемами A,B,C. Объемы находящейся в чашках жидкости X,Y,Z.

Мы можем выливать воду из чашки и наливать ее в другие. Вода в чашку наливается до заполнения (т.е. до максимального объема), остаток остается в чашке. Воду нельзя никуда больше выливать.

Нужно определить все объемы которые мы можем получить в результате переливаний.
Вывести в виде 0:1 1:2 2:3.
Первая цифра объем, вторая минимальное количество переливаний.

Язык: pascal

Решение задачи состоит в переборе всех возможных состояний чашек. Т.е. необходимо использовать алгоритм поиска в ширину.

Алгоритм

  • Заносим в список начальное состояние
  • пока в списке что-то есть
  • берем первый попавшийся элемент списка
  • добавляем в список все возможные состояния чашек получаемые из текущего, кроме тех что уже были добавлены ранее
  • удаляем текущий элемент из списка

Максимальный объем
Начальный объем

program pereliv;
var a,b,c,x,y,z:integer;
  olist:array[0..10] of integer;
  i:integer;


type    
     pL = ^tL;
     tL = record
      x,y,z:integer;
      id:longint;
      step:integer;
      next:pL;
     end;
     
var
  list,dlist:pL;
  
function inList(list:pL;id:longint):boolean;
var ls:pL;
begin
  ls:=list;
  inList:=false;
  if ls = nil then exit;
  while ls^.next
nil do begin
    if ls^.id = id then begin inList:=true; exit;end;
    ls:=ls^.next;
  end;
end;   

procedure addp(l:pL);
var t:pL;
begin
  l^.next:=nil;
  if dlist = nil then begin dlist:=l; exit;end;
  t:=dlist;
  while t^.next 
 nil do t:=t^.next;
  t^.next:=l;
  
end;

procedure del(var lst:pL);
var l:pL;
begin
  l:=lst^.next;
  addp(lst);
  lst:=l;
  
end;
procedure delm(var l:pL);
var n:pL;
begin
  while l 
 nil do begin 
    n:=l^.next;
    dispose(l);
    l:=n;
  end;
end;

procedure addv(v,c:integer);
begin
 if olist[v] > c then olist[v]:=c;
end;


procedure add(var l:pL;x,y,z,s:integer);
var cc,ll:pL;
id:longint;
begin
  if (x < 0) or (y < 0) or (z < 0) or (x > a) or (y > b) or (z > c) then exit;
  id:= longint(x) + (longint(y) shl 8) + (longint(z) shl 16);
  ll:=l;
  if ll <> nil then begin
  if inList(list, id) or inList(dlist,id) then
  exit;
  while ll^.next <> nil do ll:=ll^.next;
  new(ll^.next);cc:=ll^.next;
  end else begin new(list);ll:=list;cc:=ll;end;
  cc^.x:=x;
  cc^.y:=y;
  cc^.z:=z;
  addv(x,s);
  addv(y,s);
  addv(z,s);
  cc^.step:=s;
  cc^.id:=id;
  cc^.next:=nil;
end;

procedure add_moves(l:pL);
var x,y,z:integer;
begin
  if l <> nil then begin
    if  a-l^.x < l^.y then begin x:=a; y:=l^.y - (a-l^.x);z:=l^.z;end else begin x:= l^.x+l^.y; y:=0; z:=l^.z;end;
    add(list,x,y,z,l^.step+1);
    if  a-l^.x < l^.z then begin x:=a; z:=l^.z - (a-l^.x);y:=l^.y;end else begin x:= l^.x+l^.z; z:=0; y:=l^.y;end;
    add(list,x,y,z,l^.step+1);
    if  b-l^.y < l^.x then begin y:=b; x:=l^.x - (b-l^.y);z:=l^.z;end else begin y:= l^.y+l^.x; x:=0; z:=l^.z;end;
    add(list,x,y,z,l^.step+1);  
    if  b-l^.y < l^.z then begin y:=b; z:=l^.z - (b-l^.y);x:=l^.x;end else begin y:= l^.y+l^.z; z:=0; x:=l^.x;end;
    add(list,x,y,z,l^.step+1); 
    if  c-l^.z < l^.x then begin z:=c; x:=l^.x - (c-l^.z);y:=l^.y;end else begin z:= l^.z+l^.x; x:=0; y:=l^.y;end;
    add(list,x,y,z,l^.step+1);
    if  c-l^.z < l^.y then begin z:=c; y:=l^.y - (c-l^.z);x:=l^.x;end else begin z:= l^.z+l^.y; y:=0; x:=l^.x;end;
    add(list,x,y,z,l^.step+1); 
  end;
end;



begin
  for i:=0 to 10 do olist[i]:=11;
  list:=nil;
  dlist:=nil;
  readln(a,b,c,x,y,z); //4 1 1  1 1 1
  //a:=4;b:=1;c:=1;
  //x:=1;y:=1;z:=1;
 add(list,x,y,z,0);
 while list <> nil do begin
  add_moves(list);
  del(list);
 end;

  for i:=0 to 10 do begin
    if olist[i] <> 11 then write(i,':',olist[i],' ')
  end;
  delm(dlist);
end.

Реализация на JavaScript:


var olist=[],
    list=[],
    dlist=[],
    xx,yy,zz,a,b,c,tid;
  var did=document.getElementById('out');

  function inList(el, idx, arr) {
	if(tid == el.id) return true;
    return false;
  }
  function add(x,y,z,s){    
    if ((x < 0)||(y < 0)||(z < 0) || (x > a) || (y > b) || (z > c)) return;
    tid=x+(y<<8)+(z<<16);     
    if(list.some(inList) || dlist.some(inList)) return;
    if (olist[x] > s) olist[x]=s;
    if (olist[y] > s) olist[y]=s;
    if (olist[z] > s) olist[z]=s;
      
    list.push({x:x,y:y,z:z,s:s,id:tid});
  }
  function pereliv(){
  for(var i=0;i<11;i++) olist[i]=11;
  a=4;b=1;c=1;
  xx=1;yy=1;zz=1;
  
  add(xx,yy,zz,0);
  while(list.length >0){
      	p=list.shift();
       // did.innerHTML+= p.x+','+p.y+','+p.z+','+p.id+'
';
        if  (a-p.x < p.y) {tx=a; ty=p.y - (a-p.x);tz=p.z;} else {tx= p.x+p.y; ty=0; tz=p.z;}
  		add(tx,ty,tz,p.s+1);
    
        if  (a-p.x < p.z) {tx=a; tz=p.z - (a-p.x);ty=p.y;} else {tx= p.x+p.z; tz=0; ty=p.y;}
        add(tx,ty,tz,p.s+1);

        if  (b-p.y < p.x) {ty=b; tx=p.x - (b-p.y);tz=p.z;} else {ty= p.y+p.x; tx=0; tz=p.z;}
        add(tx,ty,tz,p.s+1);

        if  (b-p.y < p.z) {ty=b; tz=p.z - (b-p.y);tx=p.x;} else {ty= p.y+p.z; tz=0; tx=p.x;}
        add(tx,ty,tz,p.s+1);

        if  (c-p.z < p.x) {tz=c; tx=p.x - (c-p.z);ty=p.y;} else {tz= p.z+p.x; tx=0; ty=p.y;}
        add(tx,ty,tz,p.s+1);

        if  (c-p.z < p.y) {tz=c; ty=p.y - (c-p.z);tx=p.x;} else {tz= p.z+p.y; ty=0; tx=p.x;}
        add(tx,ty,tz,p.s+1);
        
         dlist.push(p);
        }
did.innerHTML='';
for(i=0;i<11;i++)if(olist[i]!=11) did.innerHTML+=i+':'+olist[i]+'
';
  }

Коментарии