https://pl.wikipedia.org/wiki/Ciąg_Fibonacciego
Algorytm ten jednak trwa bardzo długo dla większych wyrazów ciągu. Twoim zadaniem jest poprawić
szybkość wyliczani wartości ciągu Fibonacciego zgodnie z poniższym algorytmem.
Jeżeli chcemy wyliczyć N-tą liczbę Fibonacciego, musimy zrobić tak:
Dla N parzystego:
- Bierzemy liczbę Fibonacciego na pozycji N/2, zapamiętujemy ją pod literką A.
- Bierzemy liczbę Fibonacciego na pozycji (N/2)+1, mnożymy ją przez dwa. Wynik
zapamiętujemy pod literką B.
- Odejmujemy A od B, wynik odejmowania mnożymy przez A.
- Otrzymany wynik jest N-tą liczbą Fibonacciego.
Dla N nieparzystego:
- Bierzemy liczbę Fibonacciego na pozycji N/2 zaokrąglonej w dół do całości i podnosimy ją do
kwadratu. Zapamiętujemy wynik jako A.
- Bierzemy liczbę Fibonacciego na pozycji N/2 zaokrąglonej w górę do całości, podnosimy ją do
kwadratu. Zapamiętujemy wynik jako B.
- Dodajemy A do B. Wynik dodawania jest N-tą liczbą Fibonacciego.
Wejście: n=10,n=20,n=50,n=100
Wyjście:55,6765,12586269025,354224848179261915075
kod źródłowy programu zapisz w języku C#.