Задача 75.75. Обчислити N перших чисел Фібоначчі.

Розв’язання: Нагадаємо, що числами Фібоначчі називаються числа, які утворюються слідуючим чином: Ф0 = 1, Ф1 = 1, Ф2 = Ф0 + Ф1,...,Фn = Фn-2 + Фn-1.

Оскільки кожне число Фібоначчі знаходиться як сума двох попередніх чисел, то програмна реалізація не становить складнощів, потрібно тільки не забувати зберігати два попередніх числа:

program fibon1;

var n, i : integer;

fib, fib1, fib2 : longint;

begin

write(‘Скiльки чисел Фiбоначчi вивести на екран: ’);

readln(n);

fib2 := 1;

fib1 := 1;

for i:= 2 to n do

begin

fib := fib1 + fib2;

fib2 := fib1;

fib1 := fib;

writeln(‘Ф’, i,‘ = ’, fib:10);

if i mod 10 = 0 then

begin

writeln(‘ Нажмiть <Enter> для продовження ’);

readln

end;

end;

readln;

end.

Все здається просто, але спробуйте задати N = 60 і ви побачите, що не все так просто, як здається на перший погляд. До цієї проблеми ми ще з вами повернемось, після того, як вивчимо масиви, а зараз лише відмітимо той факт, що дана версія програми вірно видає результат лише при N Ј 45 і пов’язано це з тим, що числа Фібоначчі швидко зростають і виходять за межі описаного цілочисельного типу.

Задача 76.76. В деякому царстві жив Змій Горинич. У нього було N голів та M хвостів. Іван–царевич вирішив знищити губителя людських душ, для чого йому його кума Баба Яга подарувала чарівний меч, так як тільки ним можна вбити Змія Горинича. Якщо відрубати одну голову, то на її місці виростає нова, якщо відрубати хвіст, то замість нього виросте 2 хвости. Якщо відрубати два хвости, то виросте 1 голова, і тільки коли зрубати 2 голови, то не виросте нічого. Змій Горинич гине тільки в тому випадку, коли йому відрубати всі голови і всі хвости. Напишіть програму, яка вкаже мінімальну кількість ударів мечем К для знищення Змія Горинича і виведе на екран послідовність необхідних ударів мечем.

Розв’язання: Спробуємо знайти закономірність у відрубуванні, розглянувши спочатку конкретні приклади. Припустимо, що у Змія Горинича 3 голови і 3 хвости. До поставленої мети приводить така послідовність дій, як зображено в таблиці, що приводиться на наступній сторінці. Але спробуйте спочатку самостійно знайти розв'язання, його пошук принесе вам задоволення.

З наведеної нижче послідовності вже, в принципі, можна зробити деякі висновки, але перед тим, як ми їх сформулюємо, спробуйте розв’язати чисто «таблично» цю ж задачу для інших значень кількості голів і хвостів, наприклад, 4 і 3, 5 і 3 і т. д.

№ дії Дія (що відрубуємо) Голів Хвостів
   
1 хвіст
1 хвіст
1 хвіст
2 хвости
2 хвости
2 хвости –
2 голови –
2 голови –
2 голови – –

 

Тепер ми можемо, уважно придивившись до приведених таблиць (з урахуванням тих, що ви зробили самостійно), зробити деякі висновки:

1. Якщо кількість хвостів М непарна – ми повинні рубати по 1 хвосту

2. Якщо кількість голів N + половина кількості хвостів непарна – ми також рубаємо по 1 хвосту.

3. Якщо виконались дві попередні умови, то, доки кількість хвостів більша нуля, рубаємо по 2 хвости

4. Якщо відрубали всі хвости, то, доки кількість голів більша нуля, відрубуємо по 2 голови.

Перші два пункти базуються на тому факті, що сума повинна бути парним числом. Тільки у цьому випадку ми, рубаючи по 2 хвости, отримаємо в результаті парну кількість голів. Програмна реалізація описаного алгоритму має вигляд:

program Gorinitch;

var k, n, m : integer;

begin

write(‘Кількість голів: ’); readln(n);

write(‘Кількість хвостів: ’); readln(m);

k := 0;

while n > 0 do { поки не відрубаємо всі голови }

begin

if (m mod 2 = 1) or ((n + m div 2) mod 2 = 1) then

begin { рубаємо 1 хвіст }

m := m + 1;

k := k + 1;

writeln(‘ Відрубали 1xвіст: ’,n,’г ’,m,’x’);

end else

while m > 0 do { поки не відрубаємо всі хвости }

begin { рубаємо 2 хвости }

m := m-2;

n := n+1;

k := k+1;

writeln(‘ Відрубали 2 xвости: ’,n,’г ’,m,’x’);

end;

if m = 0 then

begin { рубаємо дві голови, якщо відрубали всі хвости }

n := n-2;

k := k+1;

writeln(‘ Відрубали 2 голови: ’,n,’г ’,m,’x’);

end;

end;

writeln(‘ Всього ударів мечем ’, k); readln;

end.