Текущ брой на Списание ИнфоМан
 


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

           На последните ученически състезания по информатика се налагаше да се откриват рекурентни зависимости при участието на два аргумента. На Зимния турнир, проведен в Бургас, решението на задачите A3 и B1 изискваше извеждане на следните зависимости (променили сме само означенията, с цел обобщаване):

           за A3 : F(i,1)=1  за  i=1,2, . . ,N;

                        F(i,j)=1  при  j=i;

                        F(i,j)=(i+1-j) * F(i-1,j-1) + j * F(i-1,j); за i=2,3,.. ,N и 1< j<i ;

          за B1 :F(i,0)=0  за i=2,3, . .  ,N;

                        F(i,j)=1 приj=i;

                        F(i,j) = F(i-1,j-1) + (i-1) * F(i-1,j), за i=3, . . ,N  и 0<j<i;

           На областния кръг на миналогодишната олимпиадата по информатика ( 13 март 2004 г.) подобна задача беше A2 и нейното решение изискваше откриването на следната рекурентна формула:

          за A2 : F(i,0)=1 за i=2,3, . . , N;

                        F(i,j)=1 при j=i-1;

                        F(i,j) = (i-j) * F(i-1,j-1) + (j+1) * F(i-1,j) за i=3,4, . . ,N и 0<j<i-1.

I. Икономия на памет.

            При публикуваните решения на A3 и B1, в електронното издание, в което сте в момента, за реализиране на изчисленията се ползват двумерни масиви с размерност съответно 2048 X 2048 и 2000 X 2000. Изчисленията могат да се реализират и с едномерни масиви с по N елемента. Ето нашите разсъждения :

            - изхождайки от разположението на стойностите в двумeрна таблица може да се направи следния извод : елемента F(i,j) се изчислява възоснова на две съседни стойности от предходния ред, който се намира непосредствено над и в ляво от него.

            - крайна цел при решаването на задачите е да се изведе едно число от последния изчислен ред; поради тази причина не е необходимо да се съхраняват предходните редове.

            - достатъчно е да се използва едномерен масив, в който ще се съхранява само текущо изчислявания ред.В него ще се получават новите стойности   и трябва при обхождането  да се актуализират старите стойности, след като са били използвани.

            Отново ще е необходим двоен цикъл и за сега няма да намаляваме броя на пресмятанията, а ще се опитаме да работим само със значително по - малка памет ( от порядъка на N вместо от N2 ).

            Ще използваме същността на процедурата за изчисляване на биномните коефициенти от книгата на П. Наков и П.Добриков- "Програмиране = ++ Алгоритми"(стр.497 ). При приетите от нас означения, рекурентната зависимост между числата от триъгълника на Паскал може да се запише по следния начин :

            F( i,0) = 1 за i=0,1, . . , N;

           F(i,j) = 1, при j=i;

            F(i,j) = F(i-1,j-1) + F(i-1,j) за i=1,2, . . ,N и 0<j<i;

           Посочената зависимост подсказва, че е желателно обхождането на масива във вътрешния цикъл да е с намаляваща стъпка.

T[0]=1;

T[0]:=1;

for (i=1;i<=N;i++)

for i:= 1 to N do

  { T[i]=1;

  begin  T[i]:=1;

     for(j=i-1;j>=1;j--)

      for j:=i-1 downto 1 do

        T[j]=T[j-1]+T[j];

         T[j]:=T[j-1]+T[j]

  }

  end;

            Използвания по - горе подход приложен към решението на задача A3 от тазгодишния зимен турнир води до следното :

T[1] = 1;

T[1]:=1;

for (i=2; i<=N;i++)

for i:=2 to N do

  {T[i] = 1;

  begin T[i] := 1;

    for  (j=i-1;j>=2;j--)

      for j:=i-1 downto 2 do

      T[j]=(i+1-j) * T[j-1] + j * T[j];

        T[j] := (i+1-j) * T[j-1] + j * T[j];

   }

   end;

           Необходимия фрагмент за решението на задача B1 ще изглежда по следния начин :

T[0]=0; T[1] = 1;

T[0]:=0;T[1] := 1;

for(i=2;i<=N;i++)

for i := 2 to N do

  { T[i]=1;

  begin  T[i]:=1;

     for(j=i-1;j>=1;j--)

for j := i-1 downto 1  do

       T[j] = T[j-1] + (i-1) * T[j];

T[j] := T[j-1] + (i-1) * T[j];

   }

  end;

          За решението на задача A2 от областния кръг на олимпиадата през 2004 може да се напише по следния начин:

T[0]=1; T[1] = 1;

T[0] := 1 T[1] := 1

for(i=3;i<=N;i++)

for i := 3 to N do

  { T[i-1]=1;

  begin  T[i-1]:=1;

     for(j=i-2;j>=1;j--)

for j := i-2 downto 1  do

       T[j] = (i-j)*T[j-1] + (j+1) * T[j];

T[j] :=(i-j)*T[j-1] + (j+1) * T[j];

   }

  end;

II. По - голямо бързодействие.

            По - горе представените фрагменти изчисляват всички числа от N- тия ред за задачите A3, B1 и A2. Следващите разсъждения засягат само задача B1, но аналогични могат да се направят и за останалите разглеждани задачи.

            При големи стойности на N, бързодействието може да се подобри, като се изчислява само необходимата част от елементите в масива T. Ако желаем да изчисляваме само числата надясно от търсеното число с индекс P, горните цикли могат да се запазят като вътрешния цикъл отново ще започва от i - 1, но ще приключва до някаква променлива M. В последния ред M трябва да е P, в предпоследния ред - P-1,  а преди това P-2 и т.н. Поради тази причина на M трябва да се присвои стойността i-N+P и тя не трябва да става по - малка от 1. Ето как ще изглежда кода на фрагмента за решаване на B1, при условие че не желаем излишно да изчисляваме числата в долния ляв триъгълник ( равнобедрен правоъгълен триъгълник с големина на бедрото P ).

T[0]=0;T[1]=1;

T[0]:=0;T[1]:=1;

for(i=2;i<=N;i++)

for i:=2 to N do

  {T[i]=1;M=i-N+P;

    if (M<1) M=1;

begin T[i]:=1;M:=i-N+P;

  if M<1 then M:=1;

    for(j=i-1;j>= M;j--)

  for j:=i-1 downto M do

       T[j]=T[j-1]+(i-1)*T[j];

    T[j]:=T[j-1]+(i-1)*T[j];

}

end;

            Удебеленият текст е нов или променен. Сега функцията за сложност ще е O(0.5*(N2 - P2). При необходимост да изчисляваме само в лявата част ( правоъгълен трапец с основи N и N-P и височина P ) ще е необходимо да се използват две помощни променливи A и B. Вътрешният цикъл ще приключва до една нова променлива  M, която ще бъде равна на i, ако i<P или на P в противен случай. В помощните променливи A и B се съхраняват старите стойности на елементите, които участват в изчисляването на текущата стойност. Ето и кода на този фрагмент:

T[0]=0;T[1]=1;

T[0]:=0;T[1]:=1;

for(i=2;i<=N;i++)

for i:=2 to N do

  { T[i]=1;A=T[0];

    if (i<P) M=i; else M=P;

begin T[i]:=1;A:=T[0];

  if i<P then M:=i else M:=P;

   for (j=1;j<=M;j++)

  for j:=1 to M do

      { B=T[j]; T[j]=A+(i-1)*B;A=B;}

  begin B:=T[j];T[j]:=A+(i-1)*B;A:=B;end;

}

end;

            Сложността на алгоритъма сега ще е O(N*P - 0.5*P2). Остава въпроса : кога да се реализират изчисления само в лявата част на масива T или само в дясната. Двете сложности ще са равни, ако P=N/2. Ако P<N/2 изчисленията ще стават по - бързо в лявата част , а в противен случай - в дясната. Поради тази причина се налага съпоставяне стойностите на P и N/2 и в зависимост от това се избира посоката на обхождане на вътрешния цикъл. В най - лошия случай елемента F(N,P) ще бъде намерен след 3/8*N2 изчисления.

III. С използване на триъгълна матрица.

            На стр. 505 от цитираната по - горе книга е представена следната рекурента зависимост :

                        │ 1, при i=1 или j=1;

            F(i,j) = │F(i,j-1) + F(i-j,j), ако i>j;

                        │1+F(i,i-1), ако j=i;

                        F(i,i), когато i < j,

за определяне броя на различните представяния ( разбивания ) на  i  като сума от естествени числа , не непременно различни и ненадминаващи j. Там е публикувана и програма, чрез която се определя търсения брой представяния на числото N - това е F(N,N). Използва се двумерен масив. Ако с i  е означен номера на реда, а с j - номера на стълба, последната зависимост от горната формула ще означава, че числата над главния диагонал ще бъдат еднакви в съответния ред. За да се спести памет може да се работи с триъгълна матрица. Тогава  посочената рекурентна зависимост ще трябва да има вида :

                        │ 1, при i=1 или j=1;

            F(i,j) = 1+F(i,i-1), ако j=i;

                        F(i,j-1) + F(i-j,j),ако j<=i/2;

                        F(i,j-1) + F(i-j,i-j),ако j> i/2.

            Програмният фрагмент може да изглежда по следния начин :

 F[1][1]=1;

F[1,1]:=1;

 for(i=2;i<=N;i++)

for i:=2 to N do

  {F[i][1]=1;

begin F[i,1]:=1;

   For (j=2;j<i;j++)

  for j:=2 to i-1 do

    if (j<=i/2) F[i][j]=F[i][j-1]+F[i-j][j];

    if j<=i div 2 then F[i,j]:=F[i,j-1]+F[i-j,j]

              else F[i][j]=F[i][j-1]+F[i-j][i-j];

                       else F[i,j]:=F[i,j-1]+F[i-j,i-j];

   F[i][i]=1+F[i][i-1]

  F[i,i]:=1+F[i,i-1];

}

end;

            От триъгълна матрица може да се премине към едномерен масив ( аналогично на представянето на пирамида чрез едномерен масив) посредством трансформирането на индексите по следния начин k = (i-1)*i/2 +j.

След тази редакция горния  фрагмент ще изглежда така:

T[1]=1;

T[1]:=1;

for(i=2;i<=N;i++)

for i:=2 to N do

{k=(i-1)*i/2; T[k+1]=1;

begin k:=(i-1)*i div 2;T[k+1]:=1;

  for (j=2;j<i;j++)

  for j:=2 to i-1 do

  { L=(i-j-1)*(i-j)/2;

  begin L:=(i-j-1)*(i-j) div 2;

     if (j<=i/2) T[k+j]=T[k+j-1] + T[L+j];

 if j<=i div 2 then T[k+j]:=T[k+j-1]+T[L+j]

               else T[k+j]=T[k+j-1]+T[L+i-j];

                  else T[k+j]:=T[k+j-1]+T[L+i-j];

    }

end;

   T[k+i]=1+T[k+i-1];

T[k+i]:=1+T[k+i-1];

}

end;

IV. С използване на рекурсия.

            Отново ще разгледаме задачата за определяне броя на разбиванията на числото N, като ще се основаваме на дадената по – горе рекурентна формула, използваща триъгълна матрица. Следва примерен код на рекурсивната функция getF с параметри номер на ред и номер на колона. Глобалната променлива Count се използва за преброяване извикванията на функцията.

l long getF(int i,int j)

function getF(i,j:word):longInt;

{Count++;

begin Count:=Count+1;

  if (j==1) return 1;

  if j=1 then getF:=1;

  else if (j==i) return 1+getF(i,i-1);

  else if j=i then getF:=1+getF(i,i-1)

 else if (j<=i/2)

                       return getF(i,j-1)+getF(i-j,j);

else if j<=i div 2 then

                     getF:=getF(i,j-1)+getF(i-j,j)

             else return getF(i,j-1)+getF(i-j,i-j);

             else getF:=getF(i,j-1)+getF(i-j,i-j);

}

end;

            С цел намаляване броя на изчисленията може да се приложи техниката memoization и изчислените вече сойности да се запазват в едномерен масив T (линеализирана триъгълна матрица ), откъдето да се взима наготово при необходимост от повторни изчисления ( когато T[k]>0, тъй като е инициализирана с нули).

l long memF(int i, int j)

function memF(i,j:word):longInt;

var k:word;

{ long k=(i-1)*i/2+j;

begin k:=(i-1)*i div 2+j;

  if (T[k]>0) return T[k];

  if T[k]>0 then memF:=T[k];

  else {Count++;

  else begin Count:=Count+1;

           if (j==1) T[k]=1;

          if j=1 then T[k]:=1;

           else if (j==i) T[k]=1+memF(i,i-1);

          else if j=i then T[k]:=1+memF(i,i-1)

                  else if (j<=i/2)

                T[k]=memF(i,j-1)+memF(i-j,j);

                 else if j<=i div 2 then

                T[k]:=memF(i,j-1)+memF(i-j,j)

         else T[k]=memF(i,j-1)+memF(i-j,i-j);

         else T[k]:=memF(i,j-1)+memF(i-j,i-j);

         return T[k];

         memF:=T[k];

         }

         end;

}

end;

            Следващата таблица посочва различията в броя на изчисленията при предложените по – горе два фрагмента.

 N=K=

10

20

50

100

120

I I вариант

71

1116

377750

359799166

I II вариант

33

118

673

2598

3718

 

Автор : Богдан Христов