Czołem!
Poszukuję algorytmu wyznaczającego liczbę możliwości co do rozkładu liczby na sumę elementów ciągu Fibonacciego.
Poniższe rozwiązanie jest prawie idealne, jednak wymaga podania z ilu (K) elementów ma składać się rozkład.
https://bit.ly/2KbuO12
Zastanawiam się w jaki sposób można uogólnić algorytm dla nieokreślonego K.
Czy istnieje inna możliwość niż forsowne ustalenie zakresu dla K, co będzie strasznie niewydajne, biorąc pod uwagę ilość możliwości, a liczby poddawane rozkładowi mogą sięgać 2*10^9.
0
2
Cos ala dynamic programming, albo problem wydawania reszty: suma rozklada sie na ilosc kombinacji z najwieksza liczba, plus bez najwiekszej. Wczesniej trzeba by wygenerowac liczby fibonacciego.
1
Dosłownie bierzesz program który sam zalinkowałeś i usuwasz z niego ograniczenie na K.
Problem polega na tym że masz absurdalną złożoność i raczej nic z nią nie zrobisz.
Przykładowo dla liczby N = 28657 odpowiedź to 175350753369071026461010505478
EDIT: Masz, nawet dla Javy (bo mam ją pod ręką w przeciwieństwie do Pythona i C++) sam ci zmieniłem ten kod:
//to store fibonacci numbers
//42 second number in fibonacci series
//largest possible integer
static int fib[] = new int[43];
//Function to generate fibonacci series
static void fibonacci()
{
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i < 43; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
//Recursive function to return the
//number of ways
static int rec(int x, int last)
{
// base condition
if (x == 0)
return 1;
int sum = 0;
// for recursive function call
for (int i = last; i >= 0; i--) {
if (fib[i] > x)
continue;
sum += rec(x - fib[i], i);
}
return sum;
}
//Driver code
public static void main(String[] args) {
fibonacci();
int n = 10;
System.out.println("Possible ways are: "+ rec(n, 42));
}
0
Noozen napisał(a):
Dosłownie bierzesz program który sam zalinkowałeś i usuwasz z niego ograniczenie na K.
Problem polega na tym że masz absurdalną złożoność i raczej nic z nią nie zrobisz.
Przykładowo dla liczby N = 28657 odpowiedź to 175350753369071026461010505478
EDIT: Masz, nawet dla Javy (bo mam ją pod ręką w przeciwieństwie do Pythona i C++) sam ci zmieniłem ten kod:
//to store fibonacci numbers //42 second number in fibonacci series //largest possible integer static int fib[] = new int[43]; //Function to generate fibonacci series static void fibonacci() { fib[0] = 1; fib[1] = 2; for (int i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } //Recursive function to return the //number of ways static int rec(int x, int last) { // base condition if (x == 0) return 1; int sum = 0; // for recursive function call for (int i = last; i >= 0; i--) { if (fib[i] > x) continue; sum += rec(x - fib[i], i); } return sum; } //Driver code public static void main(String[] args) { fibonacci(); int n = 10; System.out.println("Possible ways are: "+ rec(n, 42)); }
Dziękuję bardzo. Dla C++ po usunięciu y wygląda niemal identycznie. Coś mi się jednak innego nie podoba: od kiedy liczbę 10 można przestawić na 22 różne sposoby jako sumę liczb Fibonacciego...
1
Trywialna modyfikacja programu pozwala na wypisywanie liczb składowych, więc prezentuje, dla 10:
- 8,2,
- 8,1,1,
- 5,5,
- 5,3,2,
- 5,3,1,1,
- 5,2,2,1,
- 5,2,1,1,1,
- 5,1,1,1,1,1,
- 3,3,3,1,
- 3,3,2,2,
- 3,3,2,1,1,
- 3,3,1,1,1,1,
- 3,2,2,2,1,
- 3,2,2,1,1,1,
- 3,2,1,1,1,1,1,
- 3,1,1,1,1,1,1,1,
- 2,2,2,2,2,
- 2,2,2,2,1,1,
- 2,2,2,1,1,1,1,
- 2,2,1,1,1,1,1,1,
- 2,1,1,1,1,1,1,1,1,
- 1,1,1,1,1,1,1,1,1,1,
Dorzucam jeszcze OEIS jak mi nie wierzysz http://oeis.org/A003107 :-)
0
Mała zmiana planów. Znalazłem lepsze rozwiązanie, od tego podlinkowanego u góry: http://algorytmika.wikidot.com/exponential-fibosum
Kompletnie jednak nie wiem jak powinienem taki algorytm wskrzesić do życia czy w C++ czy w Pythonie… jakaś pomocna dłoń by się znalazła?
:
1
Ten algorytm, który Podlinkowaleś, rozkłada liczbę do biliona, ale bez powtórzeń; Zauważ, że jest to zaimplementowanie, pomysłu, który Ci podałem w swoim pierwszym poście w tym wątku. A wygląda tak (wygodniej mi było indeksować od zera):
from functools import reduce
from itertools import accumulate
import sys
def fibo(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
cnt = 0
def fibo_count(n):
F = [fibo(x) for x in range(2, 45)]
sF = [x for x in accumulate(F)]
N = n
a_list = []
def test(N, maxF):
global cnt
for i in range(maxF + 1):
if F[i] > N:
return
if N <= sF[i]:
a_list.append(i)
if N == F[i]:
cnt += 1
else:
test(N - F[i], i - 1)
a_list.pop()
maxF = 42
while F[maxF] >= N:
maxF -= 1
test(N, maxF)
print(cnt)
def main():
fibo_count(int(sys.argv[1]))
if __name__ == '__main__':
main()
0
lion137 napisał(a):
Ten algorytm, który Podlinkowaleś, rozkłada liczbę do biliona, ale bez powtórzeń; Zauważ, że jest to zaimplementowanie, pomysłu, który Ci podałem w swoim pierwszym poście w tym wątku. A wygląda tak (wygodniej mi było indeksować od zera)
Teraz już widzę. ;) Niemniej chciałem sprawdzić działanie kodu, tyle tylko że otrzymuję takowy błąd: IndexError: list index out of range w linijce 40,43...
EDIT: Już coś mam. Jest jeden problem, kiedy wrzucam sobie to pod pętle to dla na przykład 4 liczb: 3,4,5,10 zamiast 1,1,1,2 otrzymuję 1,2,3,5 czyli wynik i sumę poprzedniego. Jak to naprawić?
l = int(input())
for t in range(l):
q = int(input())
fibo_count(q)
0
from functools import reduce
from itertools import accumulate
import sys
def fibo(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
cnt = 0
def fibo_count(n):
F = [fibo(x) for x in range(2, 45)]
sF = [x for x in accumulate(F)]
N = n
a_list = []
def test(N, maxF):
global cnt
for i in range(maxF + 1):
if F[i] > N:
return
if N <= sF[i]:
a_list.append(i)
if N == F[i]:
cnt += 1
else:
test(N - F[i], i - 1)
a_list.pop()
maxF = 42
while F[maxF] >= N:
maxF -= 1
test(N, maxF)
print(cnt)
l = int(input())
for t in range(l):
fibo_count(int(input()))
cnt = 0
Kod działa poprawnie. Dzięki bardzo! Jest jeden problem, dostaję time limit exceeded: za długo trwa wykonanie tego kodu i to mnie martwi...