Czy da się obliczyć n-ty element w ciągu tribonacciego w podobny sposób, jak w ciągu fibonacciego? Może istnieje inny sposób, szybszy niż metoda rekurencyjna?
0
0
Pewnie jakiś wzór jest, ale taki ciąg rośnie na tyle szybko, że spokojnie możesz go prostym algorytmem liczyć dopóki wyniki mieszczą się w typie danych (oczywiście nie naiwnym, nie rób algorytmu O(ft(n)), tylko O(n)).
Dla przykładu wystarczy n=1167, żeby wynik nie mieścił się w zakresie zmiennej double. Przy takim n czas wykonania takiego algorytmu jest praktycznie natychmiastowy.
0
Mam do obliczenia ostatnie cztery cyfry, do tego wielu różnych elementów, więc najlepsze, co do tej pory wymyśliłem, to O(nlogn) [sortowanie danych wejściowych + jednokrotny przelot do największego elementu, po drodze zapamiętując dla mniejszych]. Chciałbym to zrobić szybciej, bo w niektórych przypadkach leci prawie 5 sekund. Przy symbolu newtona udało mi się zejść z 0.16s do 0.005 dzięki temu wzorowi z ułamkami i myślałem, że tu też coś w tym stylu istnieje.
0
0
Znalazłem na OEIS coś takiego, ale nie potrafię tego rozszyfrować. Rozumiecie ten zapis?
(PARI) {a(n) = polcoeff( if( n<0, x / ( 1 + x + x^2 - x^3), x^2 / ( 1 - x - x^2 - x^3) ) + x*O(x^abs(n)), abs(n))} /* Michael Somos, Sep 03 2007 */
(Maxima) a(n):=sum(sum(if mod(4*k-i, 3)>0 then 0 else binomial(k, (4*k-i)/3)*(-1)^((i-k)/3)*binomial(n-i+k-1, k-1), i, k, n), k, 1, n); [From Kruchinin Vladimir, Aug 18 2010]
1
W maximie:
binomial to symbol Newtona
sum(sumowane_wyrażenie,zmienna,granica_dolna,granica_górna)
np. sum(k*k,k,2,66) to
int suma=0;
for(int k=2;k<=66;k++)
suma+=k*k;
1
0
Dzięki! Więc jeżeli zrobię potęgowanie macierzy szybkim potęgowaniem, powinienem otrzymać złożoność O(logn), prawda? To znaczne przyspieszenie względem O(n). Wieczorem zabieram się do pisania, zobaczymy, co z tego wyjdzie.
0
Nie napisałeś od razu, że chcesz tylko 4 ostatnie cyfy. W takim wypadku sprawa jest prostsza:
int getFib(long n) {
if (n < 0)
throw new IllegalArgumentException();
if (n >= 124000)
n %= 124000;
if (n == 0)
return 0;
else if (n == 1)
return 1;
else if (n == 2)
return 1;
int a = 1;
int b = 1;
int c = 2;
for (long i = 3; i < n; i++) {
int nc = a + b + c;
a = b;
b = c;
if (nc >= 20000)
c = nc - 20000;
else if (nc >= 10000)
c = nc - 10000;
else
c = nc;
}
return c;
}
0
OK, dziękuję ślicznie za odpowiedzi, potęgowanie macierzy zrobię, jak będę miał trochę wolnego czasu, bo na razie męczę się z medianą multizbioru różnic wszystkich liczb w zbiorze - masakra... :)
0
Zrobiłem kiedyś potęgowanie macierzy + algorytm Karatsuby do mnożenia, ale dla liczb Fibonacciego, a nie Tribonacciego: VS2008 WM fibonacci duże liczby