Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Практическая работа №11. Вычисление последовательности Фибоначчи
1. Цель работы:
Получение навыков в программировании циклов.
В математике часто встречаются последовательности чисел, в которых каждый следующий член выражается через предыдущие.
В арифметической прогрессии, например, каждый следующий член равен предыдущему, увеличенному на разность прогрессии: ai=ai-1 + d
В последовательности чисел 1, 1, 2, 3, 5, 8, 13,... каждый член последовательности равен сумме двух предыдущих. Эта последовательность называется последовательностью Фибоначчи. Для этой последовательности: ai = ai-1 + ai-2 a1 = a2 = 1
Формулы, выражающие очередной член последовательности через один или несколько предыдущих членов, называются рекуррентными соотношениями.
Иногда для n-ного члена есть простая формула. Например, для арифметической прогрессии an = a1 + d * (n – 1). Чаще, однако, такой простой формулы нет или она неизвестна. В этом случае члены последовательности вычисляют по рекуррентному соотношению один за другим от i = 1 до i = n.
Для рекуррентного соотношения, задающего последовательность Фибоначчи, очередной элемент выражается через два предыдущих элемента. Поэтому в процессе вычисления надо хранить значения двух элементов. Будем делать это с помощью двух целочисленных переменных - a и b.
Сопоставим значения первых трех чисел последовательности Фибоначчи, математическую запись последовательности и переменные в программе.
|
этап |
Числа Фибоначчи |
||||||
|
1 |
1 |
2 |
3 |
5 |
8 |
13 |
|
|
ai-2 |
ai-1 |
ai |
|||||
|
1 |
a |
b |
x=a+b |
||||
|
значение |
1 |
1 |
2 |
||||
|
запомнить |
a=b 1 |
b=x 2 |
|||||
|
2 |
x=a+b |
||||||
|
значение |
1 |
2 |
3 |
||||
|
запомнить |
a=b 2 |
b=x 3 |
|||||
|
3 |
x=a+b |
||||||
|
значение |
2 |
3 |
5 |
||||
|
запомнить |
a=b 3 |
b=x 5 |
|||||
|
4 |
x=a+b |
||||||
|
значение |
3 |
5 |
8 |
||||
|
запомнить |
a=b 5 |
b=x 8 |
|||||
|
5 |
x=a+b |
||||||
|
значение |
5 |
8 |
13 |
||||
|
запомнить |
a=b 8 |
b=x 13 |
В переменной a будем хранить значение ai-2, в переменной b - значение ai-1. Очередное значение обозначим x. Присвоим значения: a = 1; b = 1; Соответственно закону образования последовательности Фибоначчи x =a + b. Получено третье число, равное 2. Запомним значение переменной b в a, x в b (1 и 2). На этапе 2 получаем очередное число: x=a+b, равное 3. Запоминаем значение переменной b в a, x в b (2 и 3). На этапе 3 получаем очередное число: x=a+b, равное 5 и так далее.
Блок-схема решения задачи
4. Пример
//последовательность Фибоначчи
#include <iostream.h>
#include <conio.h>
int main(){long int a=1, b=1,x; int i,n; clrscr(); n=10;
for(i=3;i<=n;i++){ x=a+b; a=b; b=x; cout<<x<<" "; }
getch(); return 0; }
/* n= 10
1 1 2 3 5 8 13 21 34 55 */
5. Задание
Задание на «удовлетворительно»
Ввести текст программы, получить последовательность 20 чисел Фибоначчи.
Задание на «хорошо»
Изменить программу так, чтобы пользователь мог получить последовательность чисел любой длины. Рассмотреть возможность переполнения типа long int.
Задание на «отлично»
Изменить программу так, чтобы пользователь мог по запросу получить число Фибоначчи по номеру в последовательности.
PAGE 2