Числа Фибоначчи – это значения числовой последовательности, в которой, первые два числа равны единице, а каждый последующий элемент равен сумме предыдущих двух чисел.
Последовательность Фибоначчи имеет вид:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610…
Функционально последовательность можно записать как:
- fib0 = 1
- fib1 = 1
- fibn = fibn-1 + fibn-2
Программа рекурсивного вычисления и вывода N первых членов последовательности Фибоначчи
{$CODEPAGE UTF8}
program FibonacciNumbers;
var
N, i, f : integer;
function FibonacciNumber(number : integer) : integer;
begin
if (number = 0) or (number = 1) then
FibonacciNumber := 1
else
FibonacciNumber := FibonacciNumber(number - 1) + FibonacciNumber(number - 2);
end;
begin
write('N = ');
readln(N);
writeln(N, ' первых числа Фибоначчи');
for i := 0 to N - 1 do
begin
f := FibonacciNumber(i);
write(f);
if i < N - 1 then
write(', ');
end;
readln;
end.
Поиск чисел Фибоначчи с помощью рекурсивных вызовов очень не эффективно. Дело в том, что для вычисления каждого элемента необходимо сначала вычислить значения двух предыдущих, а для каждого из них – двух предыдущих, и так далее. Получаем дерево рекурсивных вызовов. Для оптимизации алгоритма, достаточно запоминать два предыдущих элемента ряда Фибоначчи.
Оптимизированная программа поиска чисел Фибоначчи
{$CODEPAGE UTF8}
program FibonacciNumbers;
var
N, i, f : integer;
function FibNum(num : integer) : integer;
var
nm1 : integer; {fib(n-1)}
nm2 : integer; {fib(n-2)}
begin
nm1 := 1;
nm2 := 1;
if (num = 0) or (num = 1) then
FibNum := 1
else
for i := 2 to num do
begin
FibNum := nm1 + nm2;
nm2 := nm1;
nm1 := FibNum;
end;
end;
begin
write('N = ');
readln(N);
writeln(N, ' первых членов последовательности Фибоначчи');
for i := 0 to N - 1 do
begin
f := FibNum(i);
writeln('fib(', i:2,') = ', f:8);
end;
readln;
end.
Смотрите также:
Перейти к содержанию
Ряд Фибоначчи
Просмотров 5.5к. Обновлено 29 октября 2021
Ряд Фибоначчи — это последовательность натуральных чисел, где каждое последующее число является суммой двух предыдущих:
1 1 2 3 5 8 13 21 34 55 89 …
В программах ниже первые два элемента ряда равны не по 1 каждый, а 1 и 2.
Поскольку начальные значения должны быть заданы и выведены на экран, то первые два элемента ряда Фибоначчи выводятся перед циклом. Поэтому цикл начинается с третьего элемента ряда. В самом цикле выполняются следующие действия:
- Вывести сумму текущих значений последних двух элементов.
- Присвоить предпоследнему элементу значение последнего, а последнему сумму последнего и предпоследнего (это делается через буферную переменную).
Цикл выполняется до тех пор, пока переменная-счетчик, изначально равная 3, не достигнет числа, введенного пользователем.
Pascal
числа фибоначчи паскаль
var f1,f2,b,i,n: word;
begin
readln(n);
f1 := 1;
f2 := 2;
write(f1,' ',f2,' ');
for i:=3 to n do begin
write(f1+f2, ' ');
b := f1;
f1 := f2;
f2 := b + f1;
end;
writeln;
end.
9
1 2 3 5 8 13 21 34 55
Язык Си
#includemain() {
unsigned int n,i,f1,f2,b;
scanf("%d",&n);
f1 = 1;
f2 = 2;
printf("%d %d ",f1,f2);
for (i=3; i<=n; i++) {
printf("%d ", f1+f2);
b = f1;
f1 = f2;
f2 = b + f1;
}
printf("n");
}
16
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597
Python
числа фибоначчи python (питон)
n = int(input())
f1 = 1
f2 = 2
print(f1, f2, end=" ")
for i in range(3,n+1):
print(f1+f2, end=" ")
b = f1
f1 = f2
f2 = b+f1
print()
12
1 2 3 5 8 13 21 34 55 89 144 233
КуМир
алг ряд Фибоначчи
нач
цел f1,f2,b,i,n
ввод n
f1 := 1
f2 := 2
если n >= 2 то вывод f1," ",f2," " все
нц для i от 3 до n
вывод f1+f2, " "
b := f1
f1 := f2
f2 := f2+b
кц
кон
10
1 2 3 5 8 13 21 34 55 89
Basic-256
input n
f1 = 1
f2 = 2
print f1 + " ";
print f2 + " ";
for i=3 to n
print (f1+f2) + " ";
b = f1
f1 = f2
f2 = f2+b
next i
6
1 2 3 5 8 13
│
Deutsch (de) │
English (en) │
suomi (fi) │
français (fr) │
русский (ru) │
The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, …
The idea is to add the two last numbers in order to produce the next value.
generation
The following implementations show the principle of how to calculate Fibonacci numbers.
They lack of input checks.
Depending on your preferences you might either want to generate a run-time error (e. g. by {$rangeChecks on} or utilizing system.runError), raise an exception, or simply return a bogus value indicating something went wrong.
recursive implementation
3type 4 /// domain for Fibonacci function 5 /// where result is within nativeUInt 6 // You can not name it fibonacciDomain, 7 // since the Fibonacci function itself 8 // is defined for all whole numbers 9 // but the result beyond F(n) exceeds high(nativeUInt). 10 fibonacciLeftInverseRange = 11 {$ifdef CPU64} 0..93 {$else} 0..47 {$endif}; 12 13{** 14 implements Fibonacci sequence recursively 15 16 param n the index of the Fibonacci number to retrieve 17 returns the Fibonacci value at n 18} 19function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt; 20begin 21 // optimization: then part gets executed most of the time 22 if n > 1 then 23 begin 24 fibonacci := fibonacci(n - 2) + fibonacci(n - 1); 25 end 26 else 27 begin 28 // since the domain is restricted to non-negative integers 29 // we can bluntly assign the result to n 30 fibonacci := n; 31 end; 32end;
iterative implementation
This one is preferable for its run-time behavior.
13{** 14 implements Fibonacci sequence iteratively 15 16 param n the index of the Fibonacci number to calculate 17 returns the Fibonacci value at n 18} 19function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt; 20type 21 /// more meaningful identifiers than simple integers 22 relativePosition = (previous, current, next); 23var 24 /// temporary iterator variable 25 i: longword; 26 /// holds preceding fibonacci values 27 f: array[relativePosition] of nativeUInt; 28begin 29 f[previous] := 0; 30 f[current] := 1; 31 32 // note, in Pascal for-loop-limits are inclusive 33 for i := 1 to n do 34 begin 35 f[next] := f[previous] + f[current]; 36 f[previous] := f[current]; 37 f[current] := f[next]; 38 end; 39 40 // assign to previous, bc f[current] = f[next] for next iteration 41 fibonacci := f[previous]; 42end;
lookup
While calculating the Fibonacci number every time it is needed requires almost no space, it takes a split second of time.
Applications heavily relying on Fibonacci numbers definitely want to use a lookup table instead.
And yet in general, do not calculate what is already a known fact.
Since the Fibonacci sequence doesn’t change, actually calculating it is a textbook demonstration but not intended for production use.
Nevertheless an actual implementation is omitted here, since everyone wants to have it differently, a different flavor.
see also
- Fibonacci numbers in the on-line encyclopedia of integer sequences
- Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number
- Fibonacci sequence § “Pascal” on RosettaCode.org
- GNU multiple precision arithmetic library’s functions
mpz_fib_uiandmpz_fib2_ui - Lucas number, a similar series with different initial values
- Tao Yue Solution to Fibonacci Sequence Problem
В Pascal используется три вида циклов.
В ситуации, когда необходимо повторение каких-то операторов определенное количество раз, без учета каких-либо условий, то используется цикл FOR. В этом цикле используется целочисленный индекс, который увеличивается на 1 до тех пор, пока цикл не достигнет конечного значения (его еще называют цикл со счетчиком).
Например, цикл For i := 3 to 7 do write (‘A’); выведет на экран “AAAAA”.
Отсчет в цикле также возможен и в сторону уменьшения индекса.
Цикл For i := 10 downto 5 do write (‘3’); выведет на экран ‘333333’.
Если есть необходимость повторять определенные команды до тех пор, пока условие, указанное в описании цикла “верно”, то используется цикл WHILE <условие> DO (цикл с предусловием).
Например,
i := 1; While i < 7 do i := i + 3;
Пока переменная i меньше 7 цикл будет работать. Если условие изначально принимает значение “ложь”, то тело цикла (команды внутри цикла) не повторится ни одного раза. В нашем примере цикл повторится 2 раза, т.к. после второго раза переменная i станет равна 7 и условие примет значение “ложь” и произойдет выход из цикла. Не забываем в цикле изменять переменную (или переменные), которые участвуют в условии цикла, чтобы не произошло “зацикливания”.
Иногда есть необходимость выполнения каких-то команд хотя бы один раз и только потом проверяется условие, которое может отправить программу на повтор тех же операторов до тех пор, пока проверяемое условие не станет “верным”.
В этом случае используется цикл REPEAT ……. UNTIL <условие>; (цикл с постусловием).
Например, i:=1; Repeat i := i+3; Until i > 10;
Эти команды означают: повторять тело цикла до тех пор пока условие не станет “верным”, т.е. до тех пор пока i не станет больше 10, тогда программа выйдет из цикла и продолжит выполнять программу дальше. Здесь также не забываем изменять в теле цикла переменную(ые), которые участвуют в условии выхода из цикла.
Стоит обратить внимание, что циклы WHILE и REPEAT отличаются не только тем, что в первом случае у нас идет сначала условие, а потом цикл, а во втором случае – наоборот. Но и в том, что в цикле WHILE происходит выполнение тела цикла, если условие “верно”, а во втором случае тело цикла повторяется до тех пор пока постусловие не станет “верным”.
Рассмотрим использование всех трех видов цикла в программе, по выдаче на экран n-ого количества чисел Фибоначчи.
var a,b,s,n,i : integer;
begin
write (‘Введите кол-во чисел Фибоначчи, которое надо вывести на экран: ‘);
read(n);
a:=0; b:=1; // задаем два начальных числа
if n > 0 then write (a:3);
// пошаговый цикл
For i := 2 to n do
begin
write (b:5);
s:=a+b;
a:=b;
b:=s;
end;
writeln;
// цикл с предусловием
a:=0; b:=1; // задаем два начальных числа
if n > 0 then write (a:3);
i:=2;
while i <= n do
begin
write (b:5);
s:=a+b;
a:=b;
b:=s;
i := i+1; // не забываем изменять переменную
end;
writeln;
// цикл с постусловием
a:=0; b:=1; // задаем два начальных числа
i := 2;
if n > 0 then write (a:3);
repeat
write (b:5);
s:=a+b;
a:=b;
b:=s;
i := i+1; // не забываем изменять переменную
until i > n;
end.
Посмотрим результаты работы этой программы и убедимся в том, что они одинаковые.
Числа Фибоначчи – последовательность
0, 1, 1, 2, 3 ,5 ,8, 13, 21, 34, 55, 89,144,233, 377, 610, 987, 1597, 2584, 4181,..
в которой каждое последующее число равно сумме двух предыдущих чисел. Названы так в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи). Иногда число 0 не рассматривается как член последовательности. Последовательность чисел Фибоначчи можно задать выражением:
F0=0, F1=1, Fn=Fn-1+Fn-2, n≥2, n∈Z.
Программа для вывода первых 20 чисел Фибоначчи написанная на Паскале:
Program fibonacthi;
Uses Crt;
const n= 20;
Var mas: array [0..n] of integer;
i: integer;
Begin
mas[0]:=0;
mas[1]:=1;
writeln ('1');
For i:= 2 to n do
Begin
mas[i]:=mas[i-1]+ mas[i-2];
Writeln (mas[i]);
end;
Readln;
End.
Количество выводимых чисел меняется значение постоянной n.
