Завдання № 46. Вивести на екран n-ну кількість Фібоначчі » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 46. Вивести на екран n-ну кількість Фібоначчі

Завдання № 46. Вивести на екран n-ну кількість Фібоначчі
Формулювання. Дано натуральне n (яке також може бути дорівнює 0). Вивести на екран n-ну кількість Фібоначчі.
Примітка: послідовність чисел Фібоначчі задається наступною рекуррентной формулою:

Тобто, нульовий член послідовності - це число 0, 1-й член - число 1, а будь-який інший член, починаючи з 2-го, є сумою двох попередніх. Наприклад, F2 = F1 + F0 = 1 + 0 = 1, F3 = F2 + F1 = 1 + 1 = 2 і т. Д.
Рішення. Знайдемо кілька перших чисел Фібоначчі:

F2 = F1 + F0 = 1 + 0 = 1;
F3 = F2 + F1 = 1 + 1 = 2;
F4 = F3 + F2 = 2 + 1 = 3;
F5 = F4 + F3 = 3 + 2 = 5;

Легко помітити, що при їх послідовному обчисленні нам не потрібно «розписувати» доданки за визначенням, і щоб отримати черговий член послідовності, достатньо на кожному кроці складати два попередніх отриманих результату.
Так як нульовий і перший члени послідовності НЕ обчислюються і даються як частина визначення, будемо вважати їх заздалегідь відомими. Позначимо їх ідентифікаторами fib0 і fib1. За прикладом знаходження перших членів послідовності порахуємо кількість опера-цій, необхідне для обчислення кожного члена (вважаючи, що попередні члени невідомі). Легко побачити, що для обчислення 2-го члена (при відомому 1-му та нульовому членах) необхід-ма одна операція додавання, 3-го - дві операції додавання і т. Д. Видно, що за цими ж правилами для обчислення n- ного члена необхідно виконати (n - 1) операцій.
Тепер можна почати писати програму. Спочатку нам необхідно ввести значення n і ви-конати ініціалізацію значень нульового та першого чисел Фібоначчі, так як ми вважаємо їх заздалегідь відомими:
readln (n);
fib0: = 0;
fib1: = 1;

Далі нам необхідно організувати цикл, в якому на кожному кроці змінні fib0 і fib1 отримуватимуть наступні значення в послідовності чисел Фібоначчі. Тобто, наприклад, якщо в fib0 і fib1 знаходитимуться значення, відповідно, (n - 2) -го і (n - 1) -го членів послідовності Фібоначчі, то після одного кроку циклу вони будуть містити значен-ня (n - 1 ) -го і n-го членів. Для цього можна створити якусь допоміжну змінну fib, в яку помістити результат складання fib0 і fib1, після чого в fib0 у нас буде значення (n - 2) -го члена, в fib1 - (n - 1) -го, а в fib - n-го. Тепер потрібно тільки скопіювати значення fib1 в fib0 і fib в fib1, після чого значення змінної fib на цьому кроці вже не має значення. З урахуванням те-го, що ми вже порахували необхідну кількість повторень для отримання необхідного ре-результату, цикл буде виглядати так:
for i: = 1 to n - 1 do begin
  fib: = fib1 + fib0;
  fib0: = fib1;
  fib1: = fib
end;

Такий метод вирішення загальної задачі, заснований на використанні в ній рішень задач з меншою розмірністю вихідних даних (в даному випадку під розмірністю розуміється вели-чину n), називається динамічним програмуванням.
Якщо говорити конкретніше, то ми застосували метод висхідного динамічного программи-вання, що грунтується на вирішенні завдань спочатку мінімальної розмірності з поступовим отриманням рішень обширніших завдань. Цей метод найбільш оптимальний у плані реалізації, швидкодії і використовуваної пам'яті.
Однак далеко не для всіх завдань, що вирішуються за допомогою динамічного програмування, можна з'ясувати, вирішення яких підзадач потрібні для вирішення даної. Для цього суті-ет метод спадного динамічного програмування, з яким ми познайомимося пізніше.
Інший приклад спадного динамічного програмування - обчислення факторіала (задача 28). Щоб обчислити n !, необхідний обчислений (n - 1)! і т.д.
Отже, повернемося до поточної задачі. Раніше було сказано, що після вичерпання n - 1 кроків циклу в змінній fib1, яка піде на висновок в програмі, буде зберігатися значення Fn. Перевіримо коректність обробки граничних значень (зокрема, коли n = 0, 1, 2):
1) При n = 0 кордону циклу будуть у відрізку [1, 0 - 1]. При цьому значення правої межі залежить від типу змінної i, так як компілятор, щоб уникнути помилок, при обчислити-ванні «розширює» тип виразів, що означають межі циклу.
Якщо i буде оголошено типу byte, то вираз 0 - 1 дасть в результаті 255 (так як всі числові типи в мові Pascal більшість компіляторів вважає кільцевими), що ви-кличе довгий ланцюжок обчислень, а це невірно. Звичайно, можна оголосити i типу in-teger, і тоді кордону циклу будуть у відрізку [1, -1] і входити не буде здійснено, але ми зробимо інакше, намагаючись зберегти пам'ять для змінних.
Так як при обчисленні важливо лише кількість повторень, ми можемо зрушити отре-зок [1, n - 1] на одну позицію правіше на числової прямої, і тоді цикл буде проходити від 2 до n, що допоможе відсіяти вхід в цикл при введенні 0 в Як n, так як неможливий цикл по всіх i від 2 до 0.
Однак тоді ми зіткнемося з іншою проблемою: при введенні 0 буде виведено значення fib1, якій було присвоєно число 1 при ініціалізації. Справитися з проблемою можна, присвоївши fib1 значення 0, якщо n = 0:
if n = 0 then fib1: = 0;
2) При n = 1 (з урахуванням прийнятих в попередньому пункті змін) входу в цикл не буде, і на екран виведеться незмінне значення fib1, рівне 1;
3) При n = 2 відбудеться вхід в цикл, де i буде змінюватися від 2 до 2 (тобто, в цьому випадку буде виконаний єдиний крок), в якому буде обчислено значення fib = fib1 + fib0 = 1 + 0 = 1, яке буде скопійовано в fib1 і виведено на екран. Неважко зрозуміти, що подальша підстановка значень не потрібно, так як коректність циклічної конструкції ми вже довели.
Верхні значення ми не перевіряємо, оскільки не існує найбільшого номера в послідовно-сті чисел Фібоначчі (хоча зрозуміло, що коректність обчислень обмежена «вмести-мостью» типу integer, і при його перевищенні в обчисленнях числа вже будуть неправильними).

 

Код:


  1. program FibonacciNumbers;
  2. var
  3. fib0, fib1, fib: integer;
  4. i, n: byte;
  5. begin
  6. readln(n);
  7. fib0 := 0;
  8. fib1 := 1;
  9. for i := 2 to n do begin
  10. fib := fib1 + fib0;
  11. fib0 := fib1;
  12. fib1 := fib
  13. end;
  14. if n = 0 then fib1 := 0;
  15. writeln(fib1)
  16. end.

0046.-FibonacciNumbers.rar [669 b] (cкачувань: 5)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 47. Вивести на екран суму чи... Попередня сторінка » Завдання № 45. Перевірити, чи є послідо...