Votre travail consiste à reconvertir les décimales en la somme des racines carrées d'entiers. Le résultat doit avoir une précision d'au moins 6 chiffres décimaux significatifs.

Contribution :

Un nombre indiquant le nombre de racines carrées et une décimale indiquant le nombre à approximer.

Exemple d'entrée:

2 3.414213562373095

Sortie : Entiers séparés par des espaces qui, lorsqu'ils sont enracinés au carré et ajoutés, ont approximativement la décimale d'origine précise à au moins 6 chiffres décimaux significatifs.

Les zéros ne sont pas autorisés dans la solution.

S'il existe plusieurs solutions, il vous suffit d'en imprimer une.

Exemple de sortie (dans n'importe quel ordre):

4 2

Cela fonctionne parce que Math.sqrt(4) + Math.sqrt(2) == 3.414213562373095.

C'est le golf de code. Le code le plus court (avec bonus en option) gagne!

Il y aura toujours une solution mais -10 si votre programme affiche "Non" quand il n'y a pas de solution avec des entiers. De plus, -10 si votre programme imprime toutes les solutions (séparées par des retours à la ligne ou des points-virgules ou autre) au lieu d'une seule.

Cas de test:

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"]

Et oui, votre programme doit se terminer en temps fini en utilisant la mémoire finie sur n'importe quelle machine raisonnable. Cela ne peut pas simplement fonctionner "en théorie", vous devez pouvoir le tester.

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

(Méga merci à @xnor pour des conseils, en particulier la restructuration de la boucle for en un moment)

Une tentative récursive simple. Il commence par le nombre cible et soustrait continuellement les racines carrées jusqu'à ce qu'il atteigne 0 ou moins. La fonction Speut être appelée comme S(2,3.414213562373095)(le deuxième argument est supposé positif).

Le programme n'imprime pas seulement toutes les solutions, il imprime toutes les permutations de solutions (un peu étrangères, je sais). Voici la sortie pour le dernier cas: Pastebin .

Un léger ajustement donne une solution 98 - 10 = 88 qui n'imprime pas les permutations, ce qui la rend plus efficace:

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

Et juste pour le plaisir, ce 99-10 = 89 est à peu près aussi efficace que possible (contrairement aux autres, il ne fait pas exploser la pile 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

Notez que, bien que nous ayons un argument par défaut modifiable, cela ne pose jamais de problème si nous réexécutons la fonction car n+[i]crée une nouvelle liste.

Preuve d'exactitude

Afin de se retrouver dans une boucle infinie, nous devons atteindre un point où x <0 et 0,1 + x ² > 1 . Ceci est satisfait par x <-0,948 ... .

Mais notons que nous partons de x positifs et que x diminue toujours, donc pour atteindre x <-0,948 ... nous devons avoir eu x '- i ^0,5 <-0,948 ... pour certains x'> -0,948 .. . devant x et nombre entier positif i . Pour que la boucle while s'exécute, nous devons également avoir eu 0,1 + x ' ² > i .

En réarrangeant, nous obtenons x ' ² + 1,897x' + 0,948 <i <0,1 + x ' ² , les parties extérieures impliquant que x' <-0,447 . Mais si -0,948 <x '<-0,447 , alors aucun entier positif i ne peut combler l'écart dans l'inégalité ci-dessus.

Par conséquent, nous ne nous retrouverons jamais dans une boucle infinie.

ECLiPSe Prolog - 118 (138-20)

J'ai utilisé l'implémentation suivante de Prolog: 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).

Il s'agit d'une approche exponentielle très naïve. La liste de toutes les solutions possibles prend du temps pour couvrir toutes les combinaisons ( édition : la plage des nombres entiers visités diminue désormais à chaque étape, ce qui supprime beaucoup de combinaisons inutiles).

Voici une transcription d'une session de test. Par défaut, l'environnement essaiera de trouver toutes les solutions possibles (-10) et affichera "Non" s'il échoue (-10).

Comme Sp3000 l'a correctement noté dans le commentaire, il affiche également "Oui" lorsqu'il réussit. Cela signifie sûrement que je peux supprimer 10 points supplémentaires ;-)

[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]:

(Edit) Concernant les performances, elles sont assez bonnes, du moins par rapport aux autres (voir par exemple ce commentaire de FryAmTheEggman ). Tout d'abord, si vous souhaitez imprimer tous les résultats, ajoutez le prédicat suivant:

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

Voir http://pastebin.com/ugjfEHpw pour le cas (5,13.0), qui se termine en 0,24 seconde et trouve 495 solutions (mais peut-être que je manque des solutions, je ne sais pas).

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

Cette fonction renvoie la chaîne "Non" ou une chaîne avec des valeurs séparées par des espaces. Il (inefficacement) traite toutes les valeurs possibles en les encodant en un grand entier, et en commençant par des valeurs plus élevées. 0 n'est pas autorisé dans la solution, et 0 codé représente tous les uns. L'erreur est quadrillée.

Exemple:

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 "

Veuillez être patient avec f(5,13.0)comme espace de recherche de fonction est 13 ^ 10. Il peut être rendu plus rapide avec 2 octets supplémentaires.

Python 3 2: 173 159 - 10 = 149

Explication: Chaque solution est de la forme x_1 x_2 ... x_n avec 1 <= x_1 <= x ^ 2 où x est la somme cible. Par conséquent, nous pouvons coder chaque solution sous forme d'entier dans la base x ^ 2. La boucle while itère sur toutes les (x ^ 2) ^ n possibilités. Ensuite, je reconvertis l'entier et teste la somme. Assez simple.

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

Il trouve toutes les solutions, mais le dernier cas de test prend beaucoup trop de temps.

JavaScript (ES6) 162 (172-10) 173

Edit Un peu plus court, un peu plus lent.

En tant que fonction avec 2 paramètres, sortie vers la console javascript. Cela imprime toutes les solutions sans répétitions (les tuples de solutions sont générés déjà triés).
Je me souciais plus du timing que du nombre de caractères, afin qu'il soit facilement testé dans une console de navigateur dans le délai standard javascript.

(Mise à jour de février 2016) Heure actuelle du dernier scénario de test: environ 1 150 secondes . Besoins en mémoire: négligeable.

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];
  }
}

Version ES 5 N'importe quel navigateur

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];
  }
}

Extrait de test, il doit s'exécuter sur n'importe quel navigateur récent

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>

( Modifier ) Vous trouverez ci-dessous le résultat sur mon PC lorsque j'ai posté cette réponse il y a 15 mois. J'ai essayé aujourd'hui et c'est 100 fois plus rapide sur le même PC, juste avec une version alpha 64 bits de Firefox (et Chrome est loin derrière)! - heure actuelle avec Firefox 40 Alpha 64 bits: ~ 2 sec, Chrome 48: ~ 29 sec

Sortie (sur mon PC - dernier numéro est temps d' exécution en millisecondes)

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&]

Exemples

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

Il s'agit d'un algorithme récursif similaire au programme Python 3 de @ Sp3000. Il se compose d'une fonction infixe #qui renvoie une liste de toutes les permutations de toutes les solutions.

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

Avec un score de 102 99 92 - 10 = 82 nous pouvons imprimer chaque solution une seule fois, triées:

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

Essayez-le en ligne.

Effrontément emprunte de commentaire de xnor ;)

Cela manquera de mémoire sur n'importe quel ordinateur sain, même pour une valeur comme 5,5.0. Définit une fonction,, gqui peut être appelée comme g 3 7.923668178593959.

Ce programme python 3 utilise essentiellement le même algorithme (ne fait tout simplement pas l'impression "Non" à la fin, ce qui pourrait être fait en affectant une variable à tous les résultats, puis en écrivant print(K if K else "No") ), mais utilise un générateur, donc il ne fonctionne pas " t obtenir une erreur de mémoire (cela prendra encore très longtemps, mais je l'ai fait imprimer car il trouve les valeurs):

Cela a donné exactement les mêmes résultats que @ Sp3000. De plus, cela a pris plusieurs jours pour terminer (je ne l'ai pas chronométré, mais environ 72 heures).

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 169 - 10 = 159

Edit1: modification du format de sortie en entiers séparés par des espaces au lieu de séparés par des virgules. Merci pour le conseil de retirer les accolades autour (n, x).

Edit2: Merci pour les conseils de golf! Je peux couper 9 autres caractères si j'utilise simplement un test == au lieu de tester l'égalité approximative à 1e-6, mais cela invaliderait les solutions approximatives, le cas échéant.

Utilise itertools pour générer toutes les combinaisons entières possibles, espérons-le efficacement :)

Je n'ai pas trouvé un moyen d'ajouter efficacement "Non" à l'impression, il semble toujours prendre plus de 10 caractères supplémentaires.

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 octets - 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}}

S'il n'y a pas de permutations, ce programme n'imprime rien.