INFOMAN брой 7
Адитивна редица Преслав Наков
--------------- -------------
Дефиниция: Под адитивна редица ще разбираме редица от естествени числа за
която е в сила:
- първият член на редицата е 1.
- всеки следващ член е сума от два предходни не непременно различни.
Задачата, която ще разгледаме, е давана на конкурса по програмиране на
вестник "ComputerWorld" от 1995 г., както и като задача 3 от първия ден на
Първата Балканиада по информатика през 1993 г., със следното условие:
Една редица положителни цели числа a1,a2,...,an се нарича адитивна верига
с дължина n, ако за всяко k, 1<k*n, съществуват индекси i и j, 1*i*j*n, така
че ak=ai+aj. Напишете програма, която за a1=1 и въведен последен елемент an,
намира адитивна редица с минимална дължина. Подобна задача е давана и като
задача 4/1995 г. в Задочния конкурс по информатика на сп. "Computer", където
условието е леко изменено:
Дадени са целите числа a и n (0<n<100). Да си представим един въображаем
език за програмиране, който има оператор за присвояване и оператор за умноже-
ние. Напишете програма, която генерира текст на този въображаем език за прес-
мятане на b=a^n (а на степен n) с минимален брой умножения. По-долу е даден
пример на генериран текст при n=13, при който всяка двойка от скоби {} загра-
жда коментар:
x1:=a;
x2:=x1*x1; { = a^2 }
x3:=x2*x2; { = a^4 }
x4:=x3*x1; { = a^5 }
x5:=x3*x3; { = a^8 }
x6:=x5*x4; { = a^13}
b:=x6;
Ако се абстрахираме от подробностите, лесно се забелязва, че горната задача
всъщност се свежда до намирaнето на най-къса адитивна редица, чийто последен
член е някакво предварително зададено естествено число n.Следва да отбележим,
че задачата спада към класа на трудно разрешимите, т.е. за нея не съществува
алгоритъм с полиномиална сложност. Ясно е, че най-бързо растящата, а оттам и
най-къса адитивна редица е тази от степените на двойката,което е и решението
на задачата в случая n - степен на двойката.Как да подходим в останалите слу-
чаи? Най-елементарният метод е търсенето с връщане назад с пълно изчерпване.
Тъй като подобен подход има експоненциална алгоритмична сложност (най-лошата
възможна) и следователно е крайно неефективен за големи стойности на n,е доб-
ре да приложим някои оптимизации. Кнут в [3] например отбелязва, че:
1. При получаването на поредния член на редицата може да се счита, че ед-
ното от събираемите е винаги предпоследният член. Така се получават решения
със минимална дължина до n=2500;
2. Ако n е четно число, тогава първо решаваме задачата за n div 2, след
което прилагаме повдигане в квадрат. Първата стойност на n,при която по този
начин се получава по-дълго решение е 382.
Разбира се, съществуват и други оптимизации, които ще използваме в прило-
жената по-долу програма. Теоретично минималната дължина на редицата например
не би могла да бъде по-малка от Round(Ln(n)/Ln(2) + 0.5) + 1, защото това е
дължината на редицата, образувана от степените на двойката, която, както ве-
че споменахме, расте най-бързо. Това ни осигурява една мощна оптимизация -
условие за излизане от рекурсията. Можем да изполваме и някои други очевидни
оптимизации:
1. Разглеждаме членовете на редицата в намаляващ ред, което гарантира мак-
симално бързото й нарастване. (Забележете, че това правило невинаги съдържа
в себе си втората оптимизация на Кнут)
2. При намиране на решение с дължина равна на теоретично минималната, пре-
кратяваме по-нататъшното търсене.
3. Прекратяваме разглеждането редиците в момента,в който се окажат по-дъл-
ги от най-късата открита до момента.
4. Прекратяваме по-нататъшното разглеждане на редици, чийто последен член
надвишава n.
Програма:
--------
{$R-,S-,Q-}
CONST MAX = 6000;
TYPE OGR = 1.. MAX;
ArrType = Array[OGR] of OGR;
VAR N, I, Br, Minimal : OGR;
M, BEST : ArrType;
PROCEDURE PRINT;
Var I : OGR;
Begin
WriteLn('N = ', N);
For I := 1 to Br do
Write(BEST[I],' ');
WriteLn;
WriteLn('Теоретичната минимална дължина на редицата е ', Minimal,'.');
WriteLn('Действително намерената дължина на редицата е ', Br,'.')
End;
PROCEDURE Find(Index : OGR);
Var I, Pom : OGR;
Begin
If Index < Br then
If M[Index] = N then
begin
Br := Index; BEST := M;
If Br = Minimal then begin PRINT; Halt end
end
else
For I := Index downto 1 do
begin
Pom := M[I] + M[Index];
If Pom <= N then begin M[Index+1] := Pom; Find(Index+1) end
end
End;
BEGIN
Write('Моля, въведете стойност на N = '); ReadLn(N);
Minimal := Round(Ln(N)/Ln(2) + 0.5) + 1; Br := MAX; M[1] := 1;
Find(1); PRINT
END.
Приведеното решение работи, съгласно забележката на Кнут, коректно до n=2500.
Въпреки оптимизациите, за стойности на n дори по-малки от 2500, горната прог-
рама работи бавно. Ето защо ще предложим друг, значително по-бърз алгоритъм.
За съжаление това ускорение идва за сметка на надеждността - тук ще се греши
по-често.Например за числата до 100 имаме грешка при 59, а до 200 още 4 греш-
ки: за n=117, 118, 135 и 153. Алгоритъм:
Редицата ще строим отзад-напред.
1. Включваме n в редицата.
2. Докато n > 1 повтаряме
Ако n се дели на 3, то {включваме в редицата 2n/3 и n/3; n := n/3;}
Ако n се дели на 2, то {включваме в редицата n/2; n:= n/2;}
В противен случай {включваме в редицата n*1; n := n*1;}
3. Извеждаме редицата.
4. Край.
Лесно се забелязва, че този алгоритъм е по-лош от предходния,но за сметка на
това пък е многократно по-бърз, което го прави особено привлекателен за голе-
ми стойности на n. С цел намаляване на грешките леко ще го видоизменим - в
случаите на n=2k и n=3k ще допускаме, освен деление на 2 и 3 съответно, и из-
важдане на 1. Така получаваме алгоритъм с изчерпване, като на всяка стъпка
имаме средно по-малко от две рекурсивни разклонения.
Програма:
--------
CONST MAX = 10000;
TYPE OGR = 0.. MAX;
ArrType = Array[OGR] of OGR;
VAR N, Br,
Minimal : OGR;
M, BEST : ArrType;
PROCEDURE PRINT;
Var I : OGR;
Begin
WriteLn('N = ', N);
For I := Br downto 1 do
Write(BEST[I],' ');
WriteLn;
WriteLn('Намерената дължина на редицата е ', Br,'.')
End;
PROCEDURE Find(Index : OGR);
Var Pom : OGR;
Begin
If Index < Br then
If M[Index] = 1 then
begin
Br := Index; BEST := M;
If Br = Minimal then begin PRINT; Halt end
end
else
begin { делене на 3 }
If (M[Index] mod 3) = 0 then
begin
M[Index+2] := M[Index] div 3;
M[Index+1] := M[Index+2]*2;
Find(Index+2)
end;
If not Odd(M[Index]) then { делене на 2 }
begin M[Index+1] := M[Index] div 2; Find(Index+1) end;
{ изваждане на 1 }
M[Index+1] := M[Index] - 1; Find(Index+1)
end
End;
BEGIN
Write('Моля, въведете стойност на N = '); ReadLn(N);
Minimal := Round(Ln(N)/Ln(2) + 0.5) + 1; Br := MAX; M[1] := N;
Find(1); PRINT
END.
Забележете, че горните програми понякога дават различни оптимални решения.
Например за n=34 първата програма извежда като резултат:
1 2 4 8 16 32 34,
докато втората намира друго оптимално решение:
1 2 4 8 16 17 34.