INFOMAN брой 3

{
                              ЧИСЛА И ФУНКЦИИ
                              ---------------

     Дадени са две цели положителни числа X и Y (X и Y <= 32767) и функциите
 f1(x)=2*x, f2(x)=[x/2], f3(x)=[x/3], където с [a/b] се означава цялата част
 от a/b. Да се намери минимална последователност от прилагане на функции, ко-
 ято води до получаване на числото Y от числото X. Например ако X=3, Y=8, ед-
 но възможно решение е f3(3)=1, f1(1)=2, f1(2)=4, f1(4)=8. Да се отпечата ре-
 шението като последователност от числа 1, 2 или 3, които показват коя опера-
 ция се прилага всеки ход.

     РЕШЕНИЕ:  Ще използваме добре познатия ни метод с търсене в ширина - ме-
 тод на вълната.Започвайки от началната стойност X ще генерираме трите числа,
 които може да се получат с едно преобразувание чрез съответно трите функции.
 След това ще генерираме всички числа, които могат да се получат от X за два
 хода.Тях генерираме като вземаме всяко от получените при първия ход числа и
 от него получаваме чрез трите функции нови три числа.Така последователно ще
 получаваме всички числа, които могат да се получат за 1,2,3,...,n хода. Ако
 на някой ход получим числото Y, значи сме намерили решението и това решение
 е минимално, защото е получено с минимален брой ходове. Ясно е, че ако полу-
 чим едно число, което е било получавано преди това, няма смисъл да продължа-
 ваме търсенето от това число, защото предния път, когато то е било получено,
 то е било обработено и при това е било получено от по-къса последователност
 от ходове. Ето защо когато получим едно число, което е било получавано вече,
 просто го игнорираме. За целта си правим таблица,в която отбелязваме за вся-
 ко число дали е било получено вече и ако е от кое число е било получено. Ос-
 вен това за всяко новопостъпващо число ще си пазим и чрез коя от операциите
 е било получено, за да може после да възстановим по-лесно минималната после-
 дователност, която от X получава Y. Ограничението за максимално число 32767
 идва единствено от ограниченията за блоковете памет в Turbo Pascal. Търсене-
 то в ширина се извършва по стандартния алгоритъм с опашка от числа. Първона-
 чално записваме в опашката само 1 елемент - числото X. След това добавяме в
 нея всикчи числа, които могат да се получат от X чрез някоя от операциите и
 вече не са били получени. След това взимаме първия елемент от опашката и до-
 бавяме в нея всичките числа които могат да се получат от него,после взимаме
 следващия и т.н. Понеже работим само с числата от 1 до 32767, е ясно, че ал-
 горитъма ще обработи най-много 32767 числа  в най-лошия случай и затова има
 константна сложност.Винаги когато добавяме елемент в края на опашката първо
 проверяваме дали той не е равен на Y, при което отпечатваме решението.Иначе
 ако елементът не е вече получен и е в интервала [1..32767], го добавяме към
 опашката и отбелязваме как е получен той - кой е предходния му елемент и от
 коя функция е получен. Възстановяването се получава в обратния ред на прила-
 гането на операциите като на всеки ход се намира предходния елемент на теку-
 щия и номера на функцията чрез която е получен.
}

CONST Max = 32767;

TYPE t32 = array[1..Max] of word;

VAR X,Y: longint;
    SS: ^t32;
    SP: word;
    Prev,PrevOper: ^t32;

Procedure PutOpashka(What,FromWhat:longint;Oper:word);
  Procedure Print;
  Var Count: integer;
      OperList: ^t32;
  Begin
    New(OperList); Count:=0;
    repeat { find previous number and operation it is obtained from }
      Inc(Count); OperList^[Count]:=Oper;
      What:=FromWhat;
      FromWhat:=Prev^[What];
      Oper:=PrevOper^[What];
    until Oper = Max; { until begin /X/ value reached }
    for Count:= Count downto 1 do
      Write(OperList^[Count],' ');
    WriteLn; Halt;
  End;
Begin
  if What = Y then Print;

  if (What > Max) or (What < 1) or (SP >= Max) or
     (Prev^[What] <> 0) then Exit;

  Inc(SP); SS^[SP]:=What;
  Prev^[What]:=FromWhat; PrevOper^[What]:=Oper;
End;

Procedure SearchInShirina;
Var Cur,Poz: longint;
Begin
  SP:=1; PutOpashka(X,Max,Max);
  Poz:=1;
  repeat
    Cur:=SS^[Poz];
    PutOpashka( Cur div 3, Cur, 3 );
    PutOpashka( Cur div 2, Cur, 2 );
    PutOpashka( Cur * 2  , Cur, 1 );
    Inc(Poz);
  until Poz > SP;
End;


BEGIN
  Write('X = '); ReadLn(X);
  Write('Y = '); ReadLn(Y);

  if X = Y then
    begin WriteLn(' X=Y !'); Halt; end;
  New(SS); New(PrevOper);
  New(Prev); FillChar(Prev^,SizeOf(Prev^),0);
  SearchInShirina;
  WriteLn('No solution');
END.