Числа Фібоначчі
Зазначимо, що існує багато способів вирішення цієї задачі, навіть більш простих, ніж розглянуті нижче. Однак нам важливий саме підхід. Тому не варто звинувачувати авторів у явній неефективності, тим більше, що подібні способи виявляться трохи чи не єдино ефективними через кілька завдань.

Самий очевидний спосіб вирішення завдання полягає в написанні рекурсивної функції приблизно наступного вигляду:

Function F(X:integer):longint;
Begin
if (X = 1) or (X = 2) then F := 1 else F := F(X — 1) + F(X — 2)
end;

При цьому десь в середині четвертого десятка програма підвішує найшвидший комп’ютер (нагадаємо, що за правилами олімпіад час на проходження тесту обмежується, найчастіше це 1015 секунд). Спробуємо розібратися, чому так відбувається? Для обчислення F(40) ми спочатку обчислюємо F(39) і F(38). Причому F(38) ми вважаємо за новою, забуваючи, що вже вирахували його, коли вважали F(39). Тобто наша основна помилка в тому, що значення функції при одному і тому ж значенні аргументу вважається багато (дуже багато!) раз. Якщо виключити повторний рахунок, то функція стане помітно ефективніше. Для цього доводиться завести масив, в якому зберігаються значення нашої функції:

Var D: Array [1..50] of LongInt;

Спрацьовує золотий закон програмування виграючи в швидкості, програємо в пам’яті. Спершу масив заповнюється значеннями, які свідомо не можуть бути значеннями нашої функції (найчастіше, це мінус одиниця, але в нашій задачці цілком годиться для цих цілей нуль). При спробі обчислити якесь значення, програма дивиться, не вираховувалось воно раніше, і якщо так, то бере готовий результат. Функція приймає наступний вигляд (не вірте, будь ласка, книг, стверджують, що шукати числа Фібоначчі рекурсивно не можна в принципі можна, якщо відсікання робити з розумом):

Function F(X: integer): LongInt;
Begin
if D[X] = 0
then
if (X = 1) or (X = 2)
then D[X] := 1
else D[X] := F(x — 1) + F(x — 2);
F := D[X]
End;

На цьому можна зупинитися, але можна ще більше спростити рішення, прибравши рекурсію взагалі. Для цього необхідно змінити спадну логіку міркування (від того, що треба знайти до тривіального) на висхідну (відповідно навпаки). У цій задачі такий перехід очевидний і описується простим циклом:

D[1] := 1; D[2] := 1;
For i := 3 to X do D[i] := D[i-1] + D[i-2];

Найчастіше такий спосіб рази в три швидше. Але дуже часто для його написання доводиться використовувати як проміжний результат спадну форму, а іноді безрекурсивная (итеративная) форма виявляється надзвичайно складною і малозрозумілою. Не варто забувати і про те, що час на олімпіаді обмежена. Ще про один недолік другої форми буде сказано через кілька завдань. Підсумовуючи, можна дати пораду учаснику (поставтеся до нього критично): Пишіть і тестуйте рекурсивні форму, а переробленням займайтеся, якщо ваша програма перевищує відведений їй час на великих тестах.