Liczba rozkladow Fibonacci'ego

Question

Witam, ma ktos jakis sensowny pomysl na podejscie do tego zadania?

Dodam, ze algorytm musi byc z wykorzystaniem rekurencji

Comments

serio aż tak trudno wpisać w google?

---

Próbowałes coś napisać? Szukałeś w sieci?

Answer 1

1. Funkcja licząca ciąg Fibonacci'ego do wartości mniejszej bądź równej n. Wynik do wektora.
2. Funkcja rekurencyjna licząca liczbę rozkładów, kilka warunków wewnątrz niej:

• jeśli suma ostatnich wartości w wektorze jest równa n, return ++result; (gdzie result to liczba na wyjściu);
• jeśli ta suma jest mniejsza od n, zwracamy tę funkcję z naszym wektorem bez ostatniego elementu (albo usuwamy ten element albo tak jakby wskaźnik zmniejszamy o 1;
• w pozostałych przypadkach pętla dodająca do sumy kolejne wartości z wektora i kiedy wychodzi n, ++result;

Powodzenia

Comments

Imo to rozwiązanie nie działa. Z jakiej racji wybierasz ostatni element a nie np. pierwszy przy zamianie?  To jest niedziałająca heurystyka, jeżeli miałeś na myśli sprawdzanie wszystkich możliwości to to też jest słabe bo złożoność wielomianowa.

Do tego problemu trzeba zastosować programowanie dynamiczne.

---

Rekurencja, taka jak tutaj:

https://www.geeksforgeeks.org/find-ways-integer-can-expressed-sum-n-th-power-unique-natural-numbers/

Też powinna dac radę, w końcu tych liczb do miliona jest tylko 30.

---

na moje oko do szybkiego dzialania programu oprocz tablicy liczb fibonacciego (1, 2, 3, 5, 8 ...) trzeba takze utworzyc tablice sum prefiksowych fibonacci'ego (1, 3, 6, 11, 19 ...).

po drugie, program powinien na poczatku znalezc najprostsza sume jakiejs liczby, np.: 80 = 55+21+3+1, a dopiero potem jakos rekurencyjnie rozbijac te czynniki na kolejne i kolejne..., czyli nastepnie 80 = 55+13+8+3+1 = 34+21+13+8+3+1. Wymyslenie warunków w funkcji rekurencyjnej jest najtrudniejsze.

---

https://www.geeksforgeeks.org/number-of-ways-to-represent-a-number-as-sum-of-k-fibonacci-numbers/

Tu macie dokładne rozwiązanie tego problemu

---

2^30 to miliard, więc nie dałoby rady

---

ROZKŁAD ma swój wzór, ten wzór można poddać implementacji, więc ot-co cała filozowia j/w podał Jan.