# Fibonacci-talnarunan

### Hvað er Fibonacci-talnaruna?

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](https://www.visindavefur.is/svar.php?id=1592).

![](https://134878523-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LFP9j1mN9hFVwUr9_Cg%2F-LKsNHr6Y2eWpXdSx4e0%2F-LKsNMdleqTMqaHXfQIh%2Ffibonacci_talar.png?alt=media\&token=051c5799-e4a0-4d5a-b07a-81f0eeadbb14)

#### Í þessu verkefni ætlum við að skrifa forrit sem:

* spyr hversu margar *Fibonacci* tölur skuli reikna
* og prentar þær út.

### Markmið verkefnisins:

* 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:

```python
def fibonacci_runa(tala):
```

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.

```python
tala_1 = 0
tala_2 = 1
talnasafn = [tala_1, tala_2]
```

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).

```python
for t in range(tala):
```

Þá 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`).

$$
n = (n - 1) + (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`.

```python
ny_tala = tala_1 + tala_2
```

Einnig skulum við bæta gildi breytunnar `ny_tala` í listann `talnasafn` með `append()` fallinu:

```python
talnasafn.append(ny_tala)
```

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`:

```python
tala_1 = tala_2
tala_2 = ny_tala
```

Þá gæti *for* lykkjan litið svona út:

```python
for t in range(tala):
    ny_tala = tala_1 + tala_2
    talnasafn.append(ny_tala)
    tala_1 = tala_2
    tala_2 = ny_tala
```

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:

```python
def fibonacci_runa(tala):
    tala_1 = 0
    tala_2 = 1
    talnasafn = [tala_1, tala_2]
    for t in range(tala):
        ny_tala = tala_1 + tala_2
        talnasafn.append(ny_tala)
        tala_1 = tala_2
        tala_2 = ny_tala
    return talnasafn
```

### Næsta skref -> að nota fallið

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.

```python
fjoldi = input('Fjöldi talna: ')  # Ath! Gildi verður strengur
fjoldi = int(fjoldi)  # Breytum gildi breytunnar í heiltölu
```

Í 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.

```python
fjoldi = int(input('Fjöldi talna: '))
```

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()`.

```python
fib = fibonacci_runa(fjoldi)
```

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.

```python
for i in fib:
    print(i)
```

Í 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:

```python
def fibonacci_runa(tala):
    tala_1 = 0
    tala_2 = 1
    talnasafn = [tala_1, tala_2]
    for t in range(tala):
        ny_tala = tala_1 + tala_2
        talnasafn.append(ny_tala)
        tala_1 = tala_2
        tala_2 = ny_tala
    return talnasafn

fjoldi = int(input('Fjöldi talna: '))

fib = fibonacci_runa(fjoldi)

for i in fib:
    print(i)
```

Þá er ekkert því til fyrirstöðu að prófa að keyra forritið:

```
sverrir@ubuntu:~$ python3 fibonacci.py 
Fjöldi talna: 10
0
1
1
2
3
5
8
13
21
34
55
89
```

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:

```python
for t in range(tala):
```

Myndi þá líta svona út:

```python
for t in range(tala - 2):
```

### Lokaafurð

Endanlegt forrit gæti þá litið svona út:

```python
def fibonacci_runa(tala):
    tala_1 = 0
    tala_2 = 1
    talnasafn = [tala_1, tala_2]
    for t in range(tala - 2):
        ny_tala = tala_1 + tala_2
        talnasafn.append(ny_tala)
        tala_1 = tala_2
        tala_2 = ny_tala
    return talnasafn

fjoldi = int(input('Fjöldi talna: '))

fib = fibonacci_runa(fjoldi)

for i in fib:
    print(i)
```

Við skulum prófa að keyra forritið til að vera viss:

```bash
sverrir@ubuntu:~$ python3 fibonacci.py 
Fjöldi talna: 10
0
1
1
2
3
5
8
13
21
34
```

;-)
