Zabawna para ekwiwalentów wynosi 1 + 5 = 2,3 i 1,5 = 2 + 3 . Istnieje wiele takich, inna to 1 + 1 + 8 = 1 · 2 · 5 i 1 · 1 · 8 = 1 + 2 + 5 . Zasadniczo iloczyn n dodatnich liczb całkowitych jest równy sumie n dodatnich liczb całkowitych i odwrotnie.
W tym wyzwaniu musisz wygenerować wszystkie takie kombinacje dodatnich liczb całkowitych dla wejścia n> 1 , z wyłączeniem permutacji. Możesz je wydrukować w dowolnym rozsądnym formacie. Na przykład wszystkie możliwe rozwiązania dla n = 3 to:
(2, 2, 2) (1, 1, 6)
(1, 2, 3) (1, 2, 3)
(1, 3, 3) (1, 1, 7)
(1, 2, 5) (1, 1, 8)
Program, który może wygenerować najwięcej kombinacji dla najwyższej n w ciągu jednej minuty na moim 2 GB pamięci RAM , wygrywa 64-bitowy laptop Intel Ubuntu. Jeśli twoja odpowiedź zużywa więcej niż 2 GB pamięci RAM lub jest napisana w języku, którego nie mogę przetestować za pomocą bezpłatnego oprogramowania, nie uzyskam odpowiedzi. Przetestuję odpowiedzi za dwa tygodnie i wybiorę zwycięzcę. Oczywiście później można opublikować niekonkurencyjne odpowiedzi.
Ponieważ nie wiadomo, jakie są pełne zestawy rozwiązań dla wszystkich n , możesz publikować odpowiedzi, które generują niekompletne rozwiązania. Jeśli jednak inna odpowiedź wygeneruje (bardziej) kompletne rozwiązanie, nawet jeśli ich maksymalna liczba n jest mniejsza , odpowiedź wygrywa.
Aby to wyjaśnić, oto proces punktacji w celu ustalenia zwycięzcy:
Przetestuję twój program przy n = 2, n = 3 itd. Przechowuję wszystkie twoje wyjścia i zatrzymuję się, gdy twój program zajmie więcej niż minutę lub więcej niż 2 GB pamięci RAM. Za każdym razem, gdy program jest uruchamiany dla danego wejścia n, zostanie zakończony, jeśli zajmie to więcej niż 1 minutę.
Patrzę na wszystkie wyniki dla wszystkich programów dla n = 2. Jeśli program wytworzył mniej poprawne rozwiązania niż inne, program ten jest eliminowany.
Powtórz krok 2 dla n = 3, n = 4 itd. ... Ostatni stojący program wygrywa.
źródło
Odpowiedzi:
C (gcc) , n = 50000000 przy 6499 wynikach w 59 s
Aby uniknąć wytwarzania ponad terabajta wyjściowego składającego się prawie w całości z 1s, sekwencja (powiedzmy) 49999995 1s jest skracana jako
1x49999995
.Wypróbuj online!
źródło
Mathematica, n = 293 z 12 rozwiązaniami
OP zmieniło wyzwanie i prosi o dane wejściowe
Oto nowy kod, który przyjmuje dowolne n jako dane wejściowe
Dla n = 293 otrzymujesz 12 rozwiązań
wkład
Możesz przetestować ten algorytm na Wolfram Sandbox, który jest darmowym oprogramowaniem online.
Wystarczy kliknąć link, wkleić kod (ctrl + v), wkleić dane wejściowe na końcu kodu i nacisnąć shift + enter, aby uruchomić.
Wszystkie moje rozwiązania otrzymasz w kilka sekund
Oto także Wypróbuj online!w C ++ (gcc)
(wielkie dzięki @ThePirateBay za wsparcie i tłumaczenie mojego kodu na wolny język)
ten program generuje tylko rozwiązania o postaci {a, b, c} {a, b, c}
co oznacza a + b + c = a * b * c
Obliczenie zajmuje 1 sekundę
dwanaście rozwiązań to:
źródło
Python 2 , n = 175, 28 wyników w 59s
Spowolniłem go, stosując współczynnik redukcji 2, ale dostaje więcej rozwiązań, zaczynając od n = 83
Otrzymuję wyniki dla n do 92 na TIO w jednym przebiegu.
Wypróbuj online!
źródło
Rubin , n = 12 otrzymuje 6 rozwiązań
Przynajmniej w TIO, zwykłe wyniki dla 1 do 11
Wypróbuj online!
Pobiera 10 wyników poniżej minuty dla n = 13 na moim laptopie.
źródło
Mathematica, n = 19 z 11 rozwiązaniami
to moja nowa odpowiedź zgodnie z nowymi kryteriami PO
jeśli wpiszesz [n] na końcu, program wyświetli rozwiązania
oto moje wyniki (na moim starym laptopie 64-bitowym 2,4 GHz)
źródło
Haskell, wiele rozwiązań szybko
f
oblicza rozwiązania,main
funkcja dodaje pobieranie danych z wiersza poleceń oraz pewne formatowanie i liczenie.źródło
ghc -O3 -o prodsum prodsum.hs
i uruchom z argumentem wiersza poleceń:./prodsum 6
Haskell , n = 10 z 2 roztworami
Działa to jak bzdury, ale przynajmniej to naprawiłem, więc teraz podejmuję wyzwanie!
Wypróbuj online!
źródło
Aksjomat, n = 83 w 59 sekund tutaj
wyniki:
Sposób uruchamiania nad tekstem w Axiomie polega na skopiowaniu całego tekstu do pliku, zapisaniu pliku o nazwie: Name.input, w oknie Axiom użyj „) read absolutepath / Name”.
wyniki: (# f (i) znajduje długość tablicy f (i), czyli liczbę rozwiązań)
źródło