Jest taki sposób na szybkie obliczanie n-tej liczby ciągu Fibonacciego poprzez mnożenie macierzy .
Czy w zadaniu http://pl.spoj.com/problems/AL_20_05/11 - "Gra w klasy" - można też zastosować sposób z mnożeniem macierzy ?
Feb '17
Feb '17
Oto dlaczego :
Moje rozwiązanie ma czas 0.09 sek - a najlepsze mają czas 0.01 sek .
Zastanawiam się czy to wina złego algorytmu ( nieoptymalnego ) czy to tak zwane Fast I/O zadziałało w innych rozwiązaniach.
Zupełnie nie rozumiem na jakiej zasadzie działa mnożenie macierzy że daje n-ty wyraz ciągu Fibonacciego . Może teraz gdybym wiedział jakich macierzy użyć ( o jakiej ilości wierszy i kolumn ) to zrozumiał bym zasadę działania tej "sztuczki".
Dokładniej poprzez szybkie potęgowanie macierzy.
Jeżeli można, to też ciekawy jestem jak to zrobić...., bo może zasugerowałeś się pkt 1, a tutaj przecież to nie jest ciąg fibonacciego.
A dokładniej 0.00 sek
Dokładnie tak + szybszy język [c, c++] i poprawny algorytm.
AD 3
Jeżeli nie rozumiesz, jak mnożeniem [dokładniej szybkim potęgowaniem] można uzyskać n-ty wyraz ciągu Fibonacciego, to nie byłoby Ci raczej łatwiej zrozumieć zasadę działania tego algorytmu na tym przypadku [gdyby było można?]. Bo jeżeli możnaby użyć tu tej metody, macierz kwadratowa. wydaje mi się, że musiałaby mieć rozmiar co najmnie 3x3, ale nie umiem jej zbudować-wymyślić [więc może jeszcze większy rozmiar?]. Lub może nie jest to możliwe?
Macierz to
1 1 1
1 0 0
0 1 0i należy pomnożyć ją przez wektor początkowych wartości tj. [2, 1, 1].
Może Cię zaciekawić http://students.mimuw.edu.pl/~szreder/skrypt.pdf11 około strony 15.
Wydaje mi się, że trochę lepszym wektorem początkowym będzie: [1,1,0], ale oczywiście wygląda, że działa, i tak, i tak.
Ja doszedłem do macierzy:
1 1 0
1 0 1
1 0 0czyli takiej transponowanej ale coś mi tam nie zadziałało i sobie odpuściłem.
Poza tym, o ile przy macierzy dla ciągu fibonacciego, rozumiem w miarę dokładnie jak to zostało wyprowadzone, to tu na czuja.
Skrypt oczywiście znam i gdzieś tam mam na kąpie, ale trzeba do niego znowu zajrzeć i sobie odświerzyć co nieco.
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| TFRACAL - Kalkulator ułamków | Zbiór zadań | 2 | 191 | Feb 1 |
| FR_20_02 - Poszukiwacze skarbów - Błąd w testach? | Zbiór zadań | 1 | 154 | Apr 2 |
| SPOJ.com - Problem ZABAWA pl.spoj.com | Zbiór zadań | 6 | 130 | Jun 23 |