Лекции по TURBO PASCAL

Оптимизация программ

Допустим, что нам дано такое рекуррентное отношение:

a₁ = 2;

a_i = 2a_i_-1 + 3;

Нужно найти 20 член этой последовательности.

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

Сделайте это задание, прежде чем читать дальше!

Если вы добросовестно выполните это задание, то у вас получится такая программа:

program Example1;

var a : array [1..20] of integer;

i : integer;

begin

a[1] := 2;

for i := 1 to 20 do

a [i] := 2*a[i–1] + 3;

writeln (’Двадцатый элемент = ’, a[20]);

end.

Заметьте, что для вычисления 20 элемента программа находит последовательно каждый элемент, хотя для вычисления нового используется только последний элемент, остальные же лежат “мёртвым грузом”, так как далее они нигде не используются. Давайте попробуем избавиться от хранения излишней информаци. Другими словами, надо избавиться от массива. Так как при вычислении нового элемента нам надо знать, чему равен только предыдущий элемент, то будем его хранить в переменной pred, а новый элемент – в переменной novuj. Перед тем, как вычислять новый элемент, учтём, что бывший новый элемент становится предыдущим, поэтому содержание переменной pred надо будет поменять. Вот как изменится эта программа:

program Example2;

var pred, novyj, i : integer;

begin

novyj := 2;

for i := 1 to 20 do

begin

pred := novyj; { новый стал старым }

novyj := 2*pred + 3;

end;

writeln (’Двадцатый элемент = ’, novyj);

end.

Внимательно разберите этот пример! Если вам будет всё ясно, то вы, наверное, заметите, что в этой программе можно ещё избавиться от переменной pred, записав предложение цикла в таком виде:

for i := 1 to 20 do

novyj := 2*novyj + 3;

Содержание