Фибоначијеви бројеви у језику Питхон

Фибоначијеви бројеви су одређени низ у коме је прва вредност унапред декларисана као 0, а друга вредност је унапред декларисана као 1. Остали бројеви се добијају од ова два сабирањем претходна два броја. Сви Фибоначијеви бројеви су позитивни цели бројеви, почевши од 0. Првих дванаест Фибоначијевих бројева и начин на који се добијају су следећи:

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

Без збирних израза, ови Фибоначијеви бројеви се могу ставити у табелу на следећи начин:

Први ред има Фибоначијеве бројеве. Други ред има индексе засноване на нули, под претпоставком да су Фибоначијеви бројеви у низу.

Фибоначијеви бројеви се могу произвести у О(н) времену иу О(1) времену. У овим изразима временске сложености, н значи н главних операција, а 1 значи 1 главну операцију. Са О(н), производи се н Фибоначијевих бројева, почевши од 0. Са О(1), један Фибоначијев број се производи из одговарајућег индекса. Зато је потребна само једна главна операција уместо н главних операција.

Циљ овог чланка је да објасни како произвести Фибоначијеве бројеве, било како, користећи Питхон.

Формула за Фибоначијев број

Формална дефиниција Фибоначијевог броја је:

где је Ф _н је Фибоначијев број на н<суптх индексу заснованом на нули. 0 и 1 су унапред декларисани. Последњи ред показује како се остатак бројева производи из прва два. Показује да се непосредна претходна два броја додају да би се добио тренутни број.

Израда Фибоначијевих бројева у О(н) времену

Ако је н 1, онда би само 0 било одштампано као Фибоначијев број. Ако је н 2, онда би 0 и 1 били одштампани као Фибоначијеви бројеви, тим редоследом. Ако је н 3, онда би 0, 1 и 1 били одштампани као Фибоначијеви бројеви тим редоследом. Ако је н 4, онда би 0, 1, 1 и 2 били одштампани као Фибоначијеви бројеви тим редоследом. Ако је н 5, онда би 0, 1, 1, 2 и 3 били одштампани као Фибоначијеви бројеви, тим редоследом. Ако је н 6, онда би 0, 1, 1, 2, 3 и 5 били одштампани као Фибоначијеви бројеви, тим редоследом – и тако даље.

Питхон функција за производњу првих н Фибоначијевих бројева је:

Почиње стварањем низа од н елемената, сви иницијализовани на нуле. Овај низ ће садржати Фибоначијеве бројеве. Први Фибоначијев број, 0, је већ ту. Други Фибоначијев број, 1, додељује се следећом наредбом (у функцији). Затим постоји фор-петља, која почиње од индекса 2 до непосредно пре н. Има изјаву:

Ово додаје непосредна претходна два броја.

Код за позивање функције и штампање првих дванаест Фибоначијевих бројева може бити:

Н = 12
А = фибоначи(Н)
за и у опсегу (Н):
штампа (А[и], крај=’ ‘)
принт()

Излаз је:

Стварање једног Фибоначијевог броја у сталном времену

Постоји математичка формула која повезује индекс заснован на нули са одговарајућим Фибоначијевим бројем. Формула је:

Имајте на уму да на десној страни једначине није квадратни корен од 5 подигнут на степен н; то је израз у загради који је подигнут на степен н. Постоје два таква израза.

Ако је н 0, Фибн би био 0. Ако је н 1, Фиб _н било би 1. Ако је н 2, Фиб _н било би 1. Ако је н 3, Фиб _н било би 2. Ако је н 4, Фиб _н било би 3 – и тако даље. Читалац може да провери ову формулу математички тако што ће заменити различите вредности за н и проценити. н је индекс заснован на нули у овој формули.

Питхон код за ову формулу је:

импорт матх

Математички модул је увезен. Има функцију квадратног корена. Оператор, ** се користи за напајање. Функција фибНо() директно имплементира формулу. Погодан позив и штампање за функцију фибНо() је:

Н = 11
десно = фибНо(Н)
штампа (поновно)

Излаз је:

Могуће је уклонити непотребне децималне цифре из одговора. Међутим, то је дискусија за неки други пут.

Ако су различити Фибоначијеви бројеви потребни за различите н индекса, функција фибНо() мора бити позвана једном за сваки од н индекса да би вратила различите одговарајуће Фибоначијеве бројеве. Следећи програм то ради за индексе засноване на нули, од 7 до 9 (укључиво):

импорт матх

Излаз је:

Обратите пажњу на начин на који је фор-петља кодирана у Питхон-у. Први индекс је 7. Следећи индекс је 8, а последњи индекс је 9. 10 у аргументу опсега је 9 + 1. Вредност на позицији 10 мора да буде последњи индекс заснован на нули плус 1. Први аргумент, 7, је почетни индекс заснован на нули.

Закључак

Фибоначијеви бројеви су одређени низ целих бројева (позитивних целих бројева). Почиње са 0, након чега следи 1 безусловно. Остали бројеви се развијају одатле додавањем непосредна претходна два броја.

Да бисте добили првих н Фибоначијевих бројева, прихватите 0 и 1 као прва два, а затим за остатак користите фор-петљу са наредбом као што је:

који сабира непосредна претходна два броја.

Да бисте добили само један Фибоначијев број из индекса н заснованог на нули, користите формулу: