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ć.

Python 3, 90-10 = 80

def S(N,x,n=[],i=1):
 if x*x<1e-12>N==0:print(*n)
 while.1+x*x>i:S(N-1,x-i**.5,n+[i]);i+=1

(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ę Smożna wywołać podobnie S(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:

def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x<1e-12>N==0:print(*n)
 while.1+x*x>i:S(N-1,x-i**.5,n+[i]);i+=1

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):

def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x<1e-12>N:print(*n)
 while(.1+x*x>i)*N:S(N-1,x-i**.5,n+[i]);i+=1

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 ² > 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 ' ² > i .

Zmiana układu otrzymujemy x ' ² + 1,897x' + 0,948 <i <0,1 + x ' ² , 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.

ECLiPSe Prolog - 118 (138-20)

Użyłem następującej implementacji Prologa: http://eclipseclp.org/

:-lib(util).
t(0,S,[]):-!,S<0.00001,S> -0.00001.
t(N,S,[X|Y]):-A is integer(ceiling(S*S)),between(1,A,X),M is N-1,T is S-sqrt(X),t(M,T,Y).

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 ;-)

[eclipse 19]: t(1,0.5,R).

No (0.00s cpu)
[eclipse 20]: t(2,3.414213562373095,R).

R = [2, 4]
Yes (0.00s cpu, solution 1, maybe more) ? ;

R = [4, 2]
Yes (0.00s cpu, solution 2, maybe more) ? ;

No (0.01s cpu)
[eclipse 21]: t(3,7.923668178593959,R).

R = [6, 7, 8]
Yes (0.02s cpu, solution 1, maybe more) ? ;

R = [6, 8, 7]
Yes (0.02s cpu, solution 2, maybe more) ? ;

R = [7, 6, 8]
Yes (0.02s cpu, solution 3, maybe more) ? 
[eclipse 22]: t(5,5.0,R).

R = [1, 1, 1, 1, 1]
Yes (0.00s cpu, solution 1, maybe more) ? ;
^C

interruption: type a, b, c, e, or h for help : ? abort
Aborting execution ...
Abort
[eclipse 23]: t(5,13.0,R).

R = [1, 1, 1, 1, 81]
Yes (0.00s cpu, solution 1, maybe more) ? ;

R = [1, 1, 1, 4, 64]
Yes (0.00s cpu, solution 2, maybe more) ? ;

R = [1, 1, 1, 9, 49]
Yes (0.00s cpu, solution 3, maybe more) ?
[eclipse 24]:

(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:

    p(N,S):-t(N,S,L),write(L),fail.
    p(_,_).

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).

Erlang, 305–10 302–10

f(M,D)->E=round(D*D),t(p(E,M,1),{M,E,D}).
p(_,0,A)->A;p(E,N,A)->p(E,N-1,A*E).
t(-1,_)->"No";t(I,{N,E,D}=T)->L=q(I,N,E,[]),V=lists:sum([math:sqrt(M)||M<-L])-D,if V*V<0.1e-9->lists:flatten([integer_to_list(J)++" "||J<-L]);true->t(I-1,T)end.
q(I,1,_,A)->[I+1|A];q(I,N,E,A)->q(I div E,N-1,E,[I rem E+1|A]).

Ta 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:

f(1,0.5).               % returns "No"
f(2,3.414213562373095). % returns "4 2 "
f(3,7.923668178593959). % returns "8 7 6 "
f(5,5.0).               % returns "1 1 1 1 1 "
f(5,13.0).              % returns "81 1 1 1 1 "

Prosimy o cierpliwość, f(5,13.0)ponieważ przestrzeń wyszukiwania funkcji wynosi 13 ^ 10. Można to zrobić szybciej dzięki 2 dodatkowym bajtom.

Python 3 2: 173 159-10 = 149

Objaś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.

i=input;n=int(i());x=float(i());m=int(x*x);a=m**n
while a:
 s=[a/m**b%m+1for b in range(n)];a-=1
 if abs(x-sum(b**.5for b in s))<1e-5:print' '.join(map(str,s))

Znajduje wszystkie rozwiązania, ale ostatni przypadek testowy trwa o wiele za długo.

JavaScript (ES6) 162 (172–10) 173

Edytuj 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.

F=(k,t,z=t- --k,r=[])=>{
  for(r[k]=z=z*z|0;r[k];)
  { 
    for(;k;)r[--k]=z;
    for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
    w*w<1e-12&&console.log(r.join(' '));
    for(--r[k];r[k]<1;)z=--r[++k];
  }
}

Wersja ES 5 Dowolna przeglądarka

function F(k,t)
{
  var z=t- --k,r=[];  
  for(r[k]=z=z*z|0;r[k];)
  {
    for(;k;)r[--k]=z;
    for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
    w*w<1e-12&&console.log(r.join(' '));
    for(--r[k];r[k]<1;)z=--r[++k];
  }
}

Snippet testowy powinien działać w dowolnej najnowszej przeglądarce

F=(k,t)=>
{
   z=t- --k,r=[];
   for(r[k]=z=z*z|0;r[k];)
   { 
      for(;k;)r[--k]=z;
      for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
      w*w<1e-12&&console.log(r.join(' '));
      for(--r[k];r[k]<1;)z=--r[++k];
   }
}

console.log=x=>O.textContent+=x+'\n'

t=~new Date
console.log('\n2, 3.414213562373095')
F(2, 3.414213562373095)
console.log('\n5, 5')
F(5, 5)
console.log('\n3, 7.923668178593959')
F(3, 7.923668178593959)
console.log('\n5, 13')
F(5, 13)

t-=~new Date
O.textContent = 'Total time (ms) '+t+ '\n'+O.textContent

<pre id=O></pre>

( 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)

2 4
1 1 1 1 1
6 7 8
1 1 1 1 81
1 1 1 4 64
1 1 1 9 49
1 1 4 4 49
1 1 1 16 36
1 1 4 9 36
1 4 4 4 36
1 1 1 25 25
1 1 4 16 25
1 1 9 9 25
1 4 4 9 25
4 4 4 4 25
1 1 9 16 16
1 4 4 16 16
1 4 9 9 16
4 4 4 9 16
1 9 9 9 9
4 4 9 9 9
281889

Mathematica - 76-20 = 56

f[n_,x_]:=Select[Union[Sort/@Range[x^2]~Tuples~{n}],Abs[Plus@@√#-x]<10^-12&]

Przykłady

f[2, 3.414213562373095]
> {{2, 4}}
f[3, 7.923668178593959]
> {{6, 7, 8}}
f[3, 12]
> {{1, 1, 100}, {1, 4, 81}, {1, 9, 64}, {1, 16, 49}, {1, 25, 36}, {4, 4, 64}, {4, 9, 49}, {4, 16, 36}, {4, 25, 25}, {9, 9, 36}, {9, 16, 25}, {16, 16, 16}}

Haskell, 87 80-10 = 70

Jest to algorytm rekurencyjny podobny do programu Python 3 @ Sp3000. Składa się z funkcji infix, #która zwraca listę wszystkich permutacji wszystkich rozwiązań.

0#n=[[]|n^2<0.1^12]
m#n=[k:v|k<-[1..round$n^2],v<-(m-1)#(n-fromInteger k**0.5)]

Z wynikiem 102 99 92 - 10 = 82 możemy wydrukować każde rozwiązanie tylko raz, posortowane:

0#n=[[]|n^2<0.1^12]
m#n=[k:v|k<-[1..round$n^2],v<-(m-1)#(n-fromInteger k**0.5),m<2||[k]<=v]

Pyth 55 54 47-20 = 27

DgGHKf<^-Hsm^d.5T2^10_12^r1hh*HHGR?jbmjdkKK"No

Wypró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ę, gktórą można wywołać podobnie g 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).

from itertools import*
def g(G,H):
    for x in product(range(1,int(H*H+2)),repeat=G):
        if (H-sum(map(lambda n:n**.5,x)))**2<1e-12:print(*x)

Python 3 - 157 174 169 - 10 = 159

Edycja1: 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.

from itertools import*
n,x=eval(input())
for c in combinations_with_replacement(range(1,int(x*x)),n):
 if abs(sum(z**.5for z in c)-x)<1e-6:print(' '.join(map(str,c)))

Scala (397 bajtów - 10)

import java.util.Scanner
object Z extends App{type S=Map[Int,Int]
def a(m:S,i:Int)=m updated(i,1+m.getOrElse(i,0))
def f(n:Int,x:Double):Set[S]={if(n==0){if(x.abs<1e-6)Set(Map())else Set()}
else((1 to(x*x+1).toInt)flatMap{(i:Int)=>f(n-1,x-Math.sqrt(i))map{(m:S)=>a(m,i)}}).toSet}
val s=new Scanner(System.in)
f(s.nextInt,s.nextDouble)foreach{(m:S)=>m foreach{case(k,v)=>print(s"$k "*v)};println}}

Jeśli nie ma permutacji, ten program nic nie drukuje.