По - ефективно програмиране на двуаргументови рекурентни зависимости
На последните ученически
състезания по информатика се налагаше да се откриват рекурентни зависимости при
участието на два аргумента. На Зимния турнир, проведен в Бургас, решението на задачите
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
|
Автор
: Богдан Христов
|