Wyzwanie
W tym zadaniu otrzymasz liczbę całkowitą N (mniejszą niż 10 6 ), znajdź minimalny sposób, w jaki możesz sumować do N, używając tylko liczb Fibonacciego - ta partycja nazywa się reprezentacją Zeckendorfa .
Możesz użyć dowolnej liczby Fibonacciego więcej niż jeden raz i jeśli istnieje więcej niż jeden wynik reprezentacji.
Na przykład, jeśli dane wejściowe to 67, wówczas jednym z możliwych wyników może być użycie liczb Fibonacciego 1,3,8,55, co jest również minimalną liczbą liczb Fibonacciego, które można wykorzystać do uzyskania sumy 67 .
Wejście N jest podawane w jednym wierszu, wejścia są zakończone przez EOF.
Przykłady
Podany w formacie input: output
0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2
Ograniczenia
- Liczba wejść nie przekroczy 10 10 wartości.
- Twój program nie powinien działać dłużej niż 5 sekund dla wszystkich danych wejściowych.
- Możesz użyć dowolnego wybranego języka.
- Najkrótsze rozwiązanie wygrywa!
code-golf
fibonacci
integer-partitions
Donkiszotowski
źródło
źródło
Odpowiedzi:
Motorola 68000 - 34 bajty
(Składnia asemblera GNU)
36 → 34: Sprawiono, że generator Fibonacciego zatrzymał się przy przepełnieniu zamiast zliczania, i naprawił
0
obudowę, aby wyświetlała[0]
zamiast[]
. Jednak przekazanie negatywnejN
awarii powoduje teraz.Komentarz u góry to prototyp C tej funkcji, wykorzystujący rozszerzenie języka do identyfikacji, które parametry idą gdzie (domyślnie idą na stos).
Mój TI-89 z procesorem 10 MHz zajmuje 5 minut na uruchomienie tej funkcji na 1 - 1 000 000.
Chociaż kod maszynowy ma (obecnie) mniej bajtów niż rozwiązanie GolfScript, prawdopodobnie niesprawiedliwe byłoby zaakceptowanie tego jako najkrótszego rozwiązania, ponieważ:
Jeśli masz TI-89/92 / V200, możesz pobrać cały projekt tutaj (nieaktualny):
https://rapidshare.com/files/154945328/minfib.zip
Powodzenia namawianie RapidShare do uzyskania rzeczywistego pliku. Czy ktoś zna dobrego hosta dla tak dużych plików? 8940 to strasznie dużo bajtów.
źródło
JavaScript (142)
Obsługuje tylko pojedyncze wejście na raz. Ponieważ wprowadzanie wielu wierszy jest bezużyteczne w JavaScript.
http://jsfiddle.net/EqMXQ/
źródło
C, 244 znaki
Z białymi znakami:
Ten program odczytuje liczby ze standardowego wejścia i zapisuje na standardowe wyjście.
źródło
Golfscript, 43 znaki
Myślę, że można to z większym wysiłkiem zmniejszyć o 3 do 5 znaków. Np. Rozwinięcie, a następnie wyrzucenie tablicy, jest marnotrawstwem.
źródło
F # -
282 252241 znakówźródło
Python - 183 znaków
Większość kodu obsługuje wiele danych wejściowych :(
źródło
n=input()
na końcu poprzedniej linii?print
Mathematica 88
Przykład wyniku
źródło
EXCEL: 89 znaków w unikalnym kodzie:
źródło
Scala - 353 znaków (100 znaków do obsługi wielu danych wejściowych)
źródło
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))
można skrócić, abyio.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l)))
zapisać 40-znakowe postacie.Python 3 (170 znaków)
Wejście wielowierszowe, zatrzymaj się na pustej linii
źródło
C, 151 znaków
czytelna wersja:
źródło
R 170
Obsługuje wiele wejść i wyniki kota do STDOUT
źródło
R (460 znaków)
Inna wersja używająca R.
Czytanie z pliku „wejście”, wyjście do pliku „wyjście”
przykład „wprowadzania”
przykład „wynikowy”
Bardziej czytelna wersja:
źródło
D (196 znaków)
Uruchom z
rdmd --eval=…
. To wygodnie ukrywa płytę kotłaimport x, y, z;
ivoid main() {…}
:źródło
Korzystanie z Java
źródło