Trzy operacje
- mol_ksiazkowy
- Użytkownik
- Posty: 11415
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Trzy operacje
Jak wyliczyć \(\displaystyle{ 2^n}\) ty wyraz ciągu Fibonacciego wykonując nie więcej niż \(\displaystyle{ 6n}\) operacji dodawania, odejmowania i mnożenia ?
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Trzy operacje
Znając trójkę \(\displaystyle{ F_{2^k-1} \ , \ F_{2^k} \ i \ F_{2^k+1}}\) można wyznaczyć trójkę \(\displaystyle{ F_{2 \cdot 2^k-1} \ , \ F_{2 \cdot 2^k} \ i \ F_{2 \cdot 2^k+1}}\) w 6 działaniach:
\(\displaystyle{ F_{2 \cdot 2^k}=F_{2^k}(F_{2^k-1} + F_{2^k+1})}\) (dodawanie i mnożenie)
\(\displaystyle{ F_{2 \cdot 2^k-1}=(F_{2^k-1})^2 + (F_{2^k})^2}\) (dwa mnożenia i dodawanie )
\(\displaystyle{ F_{2 \cdot 2^k+1}=F_{2 \cdot 2^k-1} + F_{2 \cdot 2^k}}\) (dodawanie)
\(\displaystyle{ F_{2 \cdot 2^k}=F_{2^k}(F_{2^k-1} + F_{2^k+1})}\) (dodawanie i mnożenie)
\(\displaystyle{ F_{2 \cdot 2^k-1}=(F_{2^k-1})^2 + (F_{2^k})^2}\) (dwa mnożenia i dodawanie )
\(\displaystyle{ F_{2 \cdot 2^k+1}=F_{2 \cdot 2^k-1} + F_{2 \cdot 2^k}}\) (dodawanie)