Fibonacci-talnarunan
Last updated
Last updated
Fibonacci talnaruna virkar þannig að við byrjum með tvær tölur, 0 og 1, sem eru lagðar saman til að reikna næstu tölu. Til að reikna töluna nr. n þurfum við því að þekkja síðustu tvær tölur (n - 1 og n - 2). Þannig getur runan haldið áfram út í hið óendanlega. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... Meira um Fibonacci talnarununa á Vísindavefnum.
spyr hversu margar Fibonacci tölur skuli reikna
og prentar þær út.
að átta sig á virkni Fibonacci-talnarununnar
að þjálfast í að búa til föll
að þjálfast í að vinna með lista
að þjálfast í að nota for lykkjur
Það eru til þó nokkrar leiðir til að leysa þetta verkefni og við ætlum að fara í gegn um eina þar sem við skrifum fall sem bætir hverri tölu í lista og skilar að lokum listanum. Við munum síðan færa skilagildi fallsins okkar undir breytu og prenta innihald hennar.
Við byrjum þá á að skilgreina fallið okkar og látum það taka inn heiltölu:
Við gefum okkur svo fyrstu tvær tölurnar og skilgreinum þær sem breyturnar tala_1 og tala_2. Því næst skilgreinum við lista og færum fyrstu tvær tölurnar beint í hann.
Næst skulum við skrifa setningu með for lykkju. Breytan tala er stiki (e. parameter), í þessu tilfelli heiltala, sem kemur inn sem inntaksgildi frá notanda og tilgreinir hversu langri talnarunu skuli skilað. Við ætlum að nota breytuna tala sem inntaksgildi með fallinu range() til að skilgreina hversu oft lykkjan skuli endurtekin (meira um fallið range() í kafla um innbyggð föll).
Þá er komið að því að skrifa bálk lykkjunnar eða kóðann sem verður inntur (e. executed). Hér þurfum við að huga að því hvernig næsta tala er reiknuð. Næsta tala, köllum hana n, er summa síðustu tölu (n-1) og þar síðustu tölu (n-2).
Athugið þó að hér er átt við að n standi fyrir vísi eða hvar í röðinni talan er en ekki gildi hennar.
Við skulum skilgreina nýja breytu sem verður í hlutverki tölunnar n en við skulum kalla hana ny_tala í þessu dæmi. Breyturnar tala_1 og tala_2 verða í hlutverki n-2 og n-1.
Einnig skulum við bæta gildi breytunnar ny_tala í listann talnasafn með append() fallinu:
Nú þegar við höfum bætt nýju tölunni í safnið getum við uppfært breyturnar tala_1 og tala_2. Þá fær tala_1 sem er lægri talan gildi tala_2 og tala_2 fær gildi breytunnar ny_tala:
Þá gæti for lykkjan litið svona út:
Til ljúka við fallið þurfum við að enda á setningu þar sem fallið skilar af sér gildi sem við köllum skilagildi (e. return value). Í þessu tilfelli ætlum við að skila listanum talnasafn. Við þurfum að gæta að því að return setningin sé ekki inndregin eins og bálkur for lykkjunnar heldur sé hluti af megin bálki fallsins.
Fallið okkar gæti þá litið svona út:
Nú þegar við höfum sett saman fallið skulum við huga að því hvernig við ætlum að nota það í forritinu.
Við gætum harðkóðað lengd talnarununnar í forritið og það myndi þýða að við yrðum að gera breytingar á forritinu í hvert skipti sem við vildum fá Fibonacci-talnarunu af annar lengd en síðast.
Við skulum hins vegar að gera forritið okkar notendavænna en svo og þess vegna ætlum við að nota fallið input() til að biðja notandann um tölu (meira um input() í kafla um innbyggð föll). Við þurfum að hafa í huga að skilagildi fallsins input() er strengur og því skiptir máli að við breytum því í heiltölu áður en við reynum að nota það sem inntaksgildi með fallinu fibonacci_runa().
Skilgreinum næst breytuna fjoldi með skilagildi fallsins input(). Við skulum einnig láta fylgja kvaðningu sem leiðbeinir notandanum.
Í dæminu hér á undan byrjuðum við á að taka inn tölu frá notandanum og breytum henni síðan í heiltölu. Við gerum þetta í tveimur línum en við getum einnig framkvæmt sömu aðgerðir í einni línu.
Næst skulum við skilgreina aðra breytu (köllum hana fib) og gildi hennar verður skilagildi fallsins fibonacci_runa(). Við notum jafnframt breytuna fjoldi sem inntaksgildi fyrir fibonacci_runa().
Nú heldur breytan fib utan um lista sem inniheldur Fibonacci runu.
Markmið þessa verkefnis var að skrifa forrit sem prentar tölur Fibonacci-talnarununnar og því skulum við næst skrifa for lykkju sem fer í gegnum listann og prentar hvert stak (hverja tölu) fyrir okkur.
Í dæminu hér á undan fer for lykkjan í gegnum listann fib og prentar hvert stak (meira um for lykkjur í kafla um Lykkjur og skilyrðingar).
Forritið gæti þá litið svona út:
Þá er ekkert því til fyrirstöðu að prófa að keyra forritið:
Forritið virkar vissulega en glöggir hafa líklega tekið eftir því að í dæminu er beðið um 10 tölur en forritið prentar 12.
Vandamálið liggur í fallinu fibonacci_runa og er til komið vegna þess að þegar við skilgreindum breytuna talnasafn, listann sem heldur utan um tölurnar í rununni, þá bættum við strax inn í listann fyrstu tveimur tölunum (0 og 1). Síðar látum við for lykkjuna (það er að segja bálk hennar) bæta jafn mörgum tölum inn í listann og beðið var um. Niðurstaðan verður því að fallið skilar alltaf tveimur tölum umfram það sem notandinn óskar eftir.
Einföld lausn væri því að láta for lykkjuna innan sjaldnar eða sem nemur tveimur skiptum. Það getum við gert með því að bæta -2 við inntaksgildi range() fallsins.
Setningin sem leit svona út:
Myndi þá líta svona út:
Endanlegt forrit gæti þá litið svona út:
Við skulum prófa að keyra forritið til að vera viss:
;-)
