Twoim zadaniem jest przekształcenie ułamków dziesiętnych z powrotem w sumę pierwiastków kwadratowych liczb całkowitych. Wynik musi mieć dokładność co najmniej 6 cyfr dziesiętnych.
Wejście :
Liczba wskazująca liczbę pierwiastków kwadratowych i liczba dziesiętna wskazująca liczbę do przybliżenia.
Przykładowe dane wejściowe:
2 3.414213562373095
Dane wyjściowe : liczby całkowite oddzielone spacjami, które po zrootowaniu i dodaniu do kwadratu są w przybliżeniu pierwotne po przecinku z dokładnością do co najmniej 6 cyfr po przecinku.
Zero nie jest dozwolone w roztworze.
Jeśli istnieje wiele rozwiązań, wystarczy wydrukować tylko jedno.
Przykładowe dane wyjściowe (w dowolnej kolejności):
4 2
Działa to, ponieważ Math.sqrt(4) + Math.sqrt(2) == 3.414213562373095
.
To jest kod golfowy. Najkrótszy kod (z opcjonalnym bonusem) wygrywa!
Zawsze znajdzie się rozwiązanie, ale -10, jeśli twój program wypisze „Nie”, gdy nie ma rozwiązania z liczbami całkowitymi. Ponadto -10, jeśli program wypisze wszystkie rozwiązania (oddzielone znakiem nowej linii lub średnikiem lub czymkolwiek) zamiast tylko jednego.
Przypadki testowe:
3 7.923668178593959 --> 6 7 8
2 2.8284271247461903 --> 2 2
5 5.0 --> 1 1 1 1 1
5 13.0 --> 4 4 9 9 9 --> 81 1 1 1 1 --> 36 9 4 1 1 etc. [print any, but print all for the "all solutions bonus"]
I tak, twój program musi zakończyć się w skończonym czasie przy użyciu skończonej pamięci na dowolnej rozsądnej maszynie. Nie może po prostu działać „teoretycznie”, musisz być w stanie to przetestować.
źródło
6 7 8
drugiej premii?Odpowiedzi:
Python 3, 90-10 = 80
(Ogromne podziękowania dla @xnor za wskazówki, zwłaszcza restrukturyzację pętli for na chwilę)
Prosta próba rekurencyjna. Zaczyna się od liczby docelowej i ciągle odejmuje pierwiastki kwadratowe, aż osiągnie 0 lub mniej. Funkcję
S
można wywołać podobnieS(2,3.414213562373095)
(zakłada się, że drugi argument jest dodatni).Program nie tylko drukuje wszystkie rozwiązania, ale drukuje wszystkie permutacje rozwiązań (trochę obce, wiem). Oto wynik ostatniego przypadku: Pastebin .
Niewielkie ulepszenie daje rozwiązanie 98-10 = 88 , które nie drukuje permutacji, dzięki czemu jest bardziej wydajne:
I dla zabawy, ten 99 - 10 = 89 jest mniej więcej tak wydajny, jak to tylko możliwe (w przeciwieństwie do innych, nie wysadza stosu
S(1,1000)
:Zauważ, że chociaż mamy domyślny argument, który można zmienić, nigdy nie powoduje to problemów, jeśli uruchomimy ponownie funkcję, ponieważ
n+[i]
tworzy ona nową listę.Dowód poprawności
Aby skończyć w nieskończonej pętli, musimy trafić w punkt, w którym x <0 i 0,1 + x 2 > 1 . Jest to realizowane przez x <-0,948 ... .
Ale uwaga, że zaczynamy od dodatniej x i x jest zawsze maleje, tak aby trafić x <-0,948 ... musimy mieli x „- i 0,5 <-0.948 ... dla niektórych x”> -0,948 .. , przed x i dodatnią liczbą całkowitą i . Aby pętla while mogła działać, musieliśmy także mieć 0,1 + x ' 2 > i .
Zmiana układu otrzymujemy x ' 2 + 1,897x' + 0,948 <i <0,1 + x ' 2 , zewnętrzne części sugerują, że x' <-0,477 . Ale jeśli -0,948 <x '<-0,477 , to żadna dodatnia liczba całkowita i nie może zmieścić się w powyższej nierówności.
Dlatego nigdy nie skończymy w nieskończonej pętli.
źródło
abs
zx*x<1e-12
.while
pętla działa w celu zastąpieniafor
:while.1+x*x>i:S(x-i**.5,n+[i]);i+=1
po zainicjowaniui=1
parametrów funkcji. Chodzi o to, aby uniknąć konieczności konwersji naint
s..1
To obsłużyć nieścisłości pływaka; Myślę, że jest bezpieczny przed nieskończonymi pętlami.N
teraz, gdy jest teraz argument funkcji, krótsze jest powtarzanie sięN-1
i sprawdzanie, kiedyN==0
zamiastlen(n)==N
..1
jest bezpieczny; Mogę porozmawiać z tobą o kłótni, jeśli chcesz.ECLiPSe Prolog - 118 (138-20)
Użyłem następującej implementacji Prologa: http://eclipseclp.org/
To bardzo naiwne, wykładnicze podejście. Wymienienie wszystkich możliwych rozwiązań zajmuje czas, aby objąć wszystkie kombinacje ( edycja : zakres odwiedzanych liczb całkowitych zmniejsza się teraz z każdym krokiem, co usuwa wiele niepotrzebnych kombinacji).
Poniżej znajduje się transkrypcja sesji testowej. Domyślnie środowisko spróbuje znaleźć wszystkie możliwe rozwiązania (-10) i wyświetli „Nie”, gdy tego nie zrobi (-10).
Jak prawidłowo zauważył Sp3000 w komentarzu, drukuje również „Tak”, gdy się powiedzie. To z pewnością oznacza, że mogę usunąć jeszcze 10 punktów ;-)
(Edytuj) Jeśli chodzi o wydajność, jest całkiem dobra, przynajmniej w porównaniu do innych (patrz na przykład ten komentarz FryAmTheEggman ). Po pierwsze, jeśli chcesz wydrukować wszystkie wyniki, dodaj następujący predykat:
Zobacz http://pastebin.com/ugjfEHpw w sprawie (5,13.0), która kończy się w 0,24 sekundy i znajduje 495 rozwiązań (ale być może brakuje mi niektórych rozwiązań, nie wiem).
źródło
Erlang,
305–10302–10Ta funkcja zwraca ciąg „Nie” lub ciąg z wartościami oddzielonymi spacjami. (Nieefektywnie) przetwarza wszystkie możliwe wartości, kodując je w dużą liczbę całkowitą i rozpoczynając od wyższych wartości. 0 nie jest dozwolone w rozwiązaniu, a zakodowane 0 reprezentuje wszystkie. Błąd jest podniesiony do kwadratu.
Przykład:
Prosimy o cierpliwość,
f(5,13.0)
ponieważ przestrzeń wyszukiwania funkcji wynosi 13 ^ 10. Można to zrobić szybciej dzięki 2 dodatkowym bajtom.źródło
Python
32:173159-10 = 149Objaśnienie: Każde rozwiązanie ma postać x_1 x_2 ... x_n z 1 <= x_1 <= x ^ 2, gdzie x jest sumą docelową. Dlatego możemy zakodować każde rozwiązanie jako liczbę całkowitą w podstawie x ^ 2. Pętla while iteruje wszystkie (x ^ 2) ^ n możliwości. Następnie przeliczam liczbę całkowitą z powrotem i testuję sumę. Całkiem prosto.
Znajduje wszystkie rozwiązania, ale ostatni przypadek testowy trwa o wiele za długo.
źródło
JavaScript (ES6) 162 (172–10)
173Edytuj Trochę krócej, trochę wolniej.
Jako funkcja z 2 parametrami, wyjście do konsoli javascript. Spowoduje to wydrukowanie wszystkich rozwiązań bez powtórzeń (krotki rozwiązań są generowane już posortowane).
Bardziej zależało mi na czasie niż na liczbie znaków, dzięki czemu można go łatwo przetestować w konsoli przeglądarki w standardowym limicie czasu javascript.
(Aktualizacja z lutego 2016 r.) Aktualny czas dla ostatniego przypadku testowego: około 1
150 sekund. Wymagania dotyczące pamięci: nieistotne.Wersja ES 5 Dowolna przeglądarka
Snippet testowy powinien działać w dowolnej najnowszej przeglądarce
( Edytuj ) Poniżej znajdują się wyniki na moim komputerze, gdy opublikowałem tę odpowiedź 15 miesięcy temu. Próbowałem dzisiaj i jest 100 razy szybszy na tym samym komputerze, tylko z 64-bitową wersją alfa Firefoksa (a Chrome jest daleko w tyle)! - aktualny czas w Firefox 40 Alpha 64 bit: ~ 2 s, Chrome 48: ~ 29 s
Dane wyjściowe (na moim komputerze - ostatni numer to czas działania w milisekundach)
źródło
Mathematica - 76-20 = 56
Przykłady
źródło
No
? Ponadto dane wyjściowe nie są rozdzielane spacjami. Nie możesz też użyćTr@
zamiastPlus@@
? Być może będziesz w stanie zapisać niektóre znaki, zmieniającSelect
naCases
, funkcję na końcu na wzorzec i wykonującf
nienazwaną czystą funkcję.Haskell,
8780-10 = 70Jest to algorytm rekurencyjny podobny do programu Python 3 @ Sp3000. Składa się z funkcji infix,
#
która zwraca listę wszystkich permutacji wszystkich rozwiązań.Z wynikiem
102 9992 - 10 = 82 możemy wydrukować każde rozwiązanie tylko raz, posortowane:źródło
Pyth
55 5447-20 = 27Wypróbuj online.
Bezwstydnie pożycza od komentarza Xnora ;)
To zabraknie pamięci na każdym rozsądnym komputerze, nawet dla wartości takiej jak
5,5.0
. Definiuje funkcję,g
którą można wywołać podobnieg 3 7.923668178593959
.Ten program w Pythonie 3 używa zasadniczo tego samego algorytmu (po prostu nie wykonuje drukowania „Nie” na końcu, co można zrobić przez przypisanie zmiennej do wszystkich wyników, a następnie zapisywanie
print(K if K else "No")
), ale używa generatora, więc nie robi t pojawia się błąd pamięci (nadal potrwa to bardzo długo, ale kazałem mu drukować, gdy znajdzie wartości):To dało dokładnie takie same wyniki, jak @ Sp3000. Ponadto zajęło mi to kilka dni (nie zdążyłem tego zrobić, ale około 72 godzin).
źródło
Python 3 -
157174169 - 10 = 159Edycja1: Zmieniono format wyjściowy na liczby całkowite rozdzielone spacjami zamiast rozdzielane przecinkami. Dziękujemy za wskazówkę dotyczącą usuwania nawiasów klamrowych wokół (n, x).
Edycja2: Dzięki za wskazówki dotyczące gry w golfa! Mogę przyciąć kolejne 9 znaków, jeśli po prostu użyję testu == zamiast testować przybliżoną równość w granicach 1e-6, ale to unieważniłoby przybliżone rozwiązania, jeśli takie istnieją.
Używa itertools do generowania wszystkich możliwych kombinacji liczb całkowitych, mam nadzieję, że skutecznie :)
Nie znalazłem sposobu na skuteczne dodanie drukowania „Nie”, zawsze wydaje się, że zajmuje on więcej niż 10 dodatkowych znaków.
źródło
n,x
.SyntaxError
s, kiedy próbujęeval
linii ...from itertools import*
oszczędza 1, usuwając przestrzeńz**.5for
oszczędza 1 i usuwanie[]
insum(z**.5for z in c)
oszczędza 2 i wyjmowanie()
inif(...)
oszczędza 1.n,x=input()
byłaby bardziej kompaktowa?Scala (397 bajtów - 10)
Jeśli nie ma permutacji, ten program nic nie drukuje.
źródło