Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | N-th Fibonacci |
| Level: | 6 kyu |
| Sprache: | TypeScript |
Beschreibung:
I love Fibonacci numbers in general, but I must admit I love some more than others.
I would like for you to write me a function that, when given a number n (n >= 1 ), returns the nth number in the Fibonacci Sequence.
For example:
nthFibo(4) == 2
nthFibo(4) == 2
nth_fibonacci(4) == 2
fib 4 == 2
nth-fibo 4 == 2
nth_fib(4) == 2
NthFib(4) == 2
nth_fib(4) == 2
nthfibo(4) == 2
nth_fib(4) == 2
mov edi, 4
call nth_fib
cmp rax, 2 ; should be equal
Because 2 is the 4th number in the Fibonacci Sequence.
For reference, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.
Note: Since the 94th term of the sequence would cause an overflow in Lua, n will be between 0 and 93 (inclusive).
#### Encodings
`numEncoding: BinaryScott`
Quelle: codewars.com
Lösung
Pseudo-Code
Wie immer gibt's reichlich Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Als Erstes definieren wir uns unser Fibonacci-Array und legen am besten gleich die 0 und die 1 mit rein.
Schritt 2
Dann loopen wir solange, bis wir die n-te Zahl errechnet haben.
Schritt 3
Bei jeder Iteration hängen wir die Summe der beiden vorhergehenden Zahlen an das Array an.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Meine erste Zeile:
export function nthFibo(n: number): number {
Ich erstelle mein Array:
const fibonacci = [0, 1];
Jetzt der Loop:
for (let i = 2; i < n; i++) {
Da die ersten beiden Zahlen (das 0. und das 1. Element) schon im Fibonacci-Array enthalten sind, starte ich den Loop hier bei 2.
Der Lesbarkeit halber speichere ich jewelis die letzte und die vorletzte Zahl in entsprechenden Variablen ab:
const last = fibonacci[i - 1];
const secondLast = fibonacci[i - 2];
Dann hänge ich die Summe beider Zahlen an das Array dran:
fibonacci.push(last + secondLast);
}
Zum Schluss nur noch die richtige Zahl im Fibonacci zurückgeben:
return fibonacci[n - 1];
}
Wir wollen die n-te Zahl haben, unser Array-Index startet aber bei 0. Um den richtigen Index zu erhalten ziehen wir einfach 1 von n ab.
Voilá! 💪
Komplettlösung
export function nthFibo(n: number): number {
const fibonacci = [0, 1];
for (let i = 2; i < n; i++) {
const last = fibonacci[i - 1];
const secondLast = fibonacci[i - 2];
fibonacci.push(last + secondLast);
}
return fibonacci[n - 1];
}