Su trabajo es convertir los decimales nuevamente en la suma de las raíces cuadradas de los enteros. El resultado debe tener una precisión de al menos 6 dígitos decimales significativos.

Entrada :

Un número que indica el número de raíces cuadradas y un decimal que indica el número a aproximar.

Entrada de ejemplo:

2 3.414213562373095

Salida : enteros separados por espacios que, cuando se enraizan y se suman, tienen aproximadamente el decimal original con una precisión de al menos 6 dígitos decimales significativos.

Los ceros no están permitidos en la solución.

Si hay varias soluciones, solo tiene que imprimir una.

Ejemplo de salida (en cualquier orden):

4 2

Esto funciona porque Math.sqrt(4) + Math.sqrt(2) == 3.414213562373095.

Este es el código de golf. ¡El código más corto (con bonificación opcional) gana!

Siempre habrá una solución, pero -10 si su programa imprime "No" cuando no hay una solución con enteros. Además, -10 si su programa imprime todas las soluciones (separadas por nuevas líneas o punto y coma o lo que sea) en lugar de solo una.

Casos de prueba:

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

Y sí, su programa tiene que terminar en tiempo finito usando memoria finita en cualquier máquina razonable. No solo puede funcionar "en teoría", tienes que ser capaz de probarlo.

Pitón 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

(Mega gracias a @xnor por los consejos, especialmente la reestructuración del ciclo for en un tiempo)

Un simple intento recursivo. Comienza con el número objetivo y resta continuamente raíces cuadradas hasta que llega a 0 o menos. La función Sse puede llamar como S(2,3.414213562373095)(se supone que el segundo argumento es positivo).

El programa no solo imprime todas las soluciones, imprime todas las permutaciones de soluciones (un poco extraño, lo sé). Aquí está la salida para el último caso: Pastebin .

Un ligero ajuste proporciona una solución 98-10 = 88 que no imprime permutaciones, lo que la hace más eficiente:

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

Y solo por diversión, este 99 - 10 = 89 es lo más eficiente posible (a diferencia de los otros, no vuela la pila 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

Tenga en cuenta que, aunque tenemos un argumento predeterminado mutable, esto nunca causa un problema si volvemos a ejecutar la función, ya que n+[i]crea una nueva lista.

Prueba de corrección

Para terminar en un bucle infinito, debemos alcanzar algún punto donde x <0 y 0.1 + x ² > 1 . Esto se logra haciendo x <-0.948 ... .

Pero tenga en cuenta que comenzamos desde x positivo y x siempre está disminuyendo, por lo que para golpear x <-0.948 ... debemos haber tenido x '- i ^0.5 <-0.948 ... para algunos x'> -0.948 .. . antes de xy entero positivo i . Para que se ejecute el ciclo while, también debemos haber tenido 0.1 + x ' ² > i .

Reordenando obtenemos x ' ² + 1.897x' + 0.948 <i <0.1 + x ' ² , las partes externas implican que x' <-0.447 . Pero si -0,948 <x'<-0,447 , entonces número entero no positivo i puede caber la brecha en la desigualdad anterior.

Por lo tanto, nunca terminaremos en un bucle infinito.

Prólogo ECLiPSe - 118 (138-20)

Usé la siguiente implementación 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).

Este es un enfoque exponencial muy ingenuo. Enumerar todas las soluciones posibles lleva tiempo para cubrir todas las combinaciones ( editar : el rango de enteros visitados ahora disminuye en cada paso, lo que elimina muchas combinaciones inútiles).

Aquí sigue una transcripción de una sesión de prueba. Por defecto, el entorno intentará encontrar todas las soluciones posibles (-10) e imprimirá "No" cuando no lo haga (-10).

Como Sp3000 señaló correctamente en el comentario, también imprime "Sí" cuando tiene éxito. Eso seguramente significa que puedo eliminar 10 puntos más ;-)

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

(Editar) En cuanto al rendimiento, es bastante bueno, al menos en comparación con otros (ver, por ejemplo, este comentario de FryAmTheEggman ). Primero, si desea imprimir todos los resultados, agregue el siguiente predicado:

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

Ver http://pastebin.com/ugjfEHpw para el caso (5,13.0), que se completa en 0.24 segundos y encontrar 495 soluciones (pero tal vez me faltan algunas soluciones, no lo sé).

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

Esta función devuelve la cadena "No" o una cadena con valores separados por espacios. (Ineficientemente) procesa todos los valores posibles que los codifican en un número entero grande y comienzan con valores más altos. 0 no están permitidos en la solución, y 0 codificado representa todos. El error es al cuadrado.

Ejemplo:

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 "

Tenga paciencia f(5,13.0)ya que el espacio de búsqueda de funciones es 13 ^ 10. Se puede hacer más rápido con 2 bytes adicionales.

Pitón 3 2: 173159-10 = 149

Explicación: Cada solución tiene la forma x_1 x_2 ... x_n con 1 <= x_1 <= x ^ 2 donde x es la suma objetivo. Por lo tanto, podemos codificar cada solución como un entero en la base x ^ 2. El ciclo while itera sobre todas las posibilidades (x ^ 2) ^ n. Luego convierto el entero de nuevo y pruebo la suma. Muy claro.

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

Encuentra todas las soluciones, pero el último caso de prueba lleva demasiado tiempo.

JavaScript (ES6) 162 (172-10) 173

Editar Un poco más corto, un poco más lento.

Como una función con 2 parámetros, salida a la consola javascript. Esto imprime todas las soluciones sin repeticiones (las tuplas de soluciones se generan ya ordenadas).
Me preocupaba más el tiempo que el recuento de caracteres, por lo que se prueba fácilmente en una consola del navegador dentro del límite de tiempo estándar de JavaScript.

(Actualización de febrero de 2016) Hora actual para el último caso de prueba: aproximadamente 1 150 segundos . Requisitos de memoria: insignificante.

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

Versión ES 5 Cualquier navegador

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

Test Snippet debería ejecutarse en cualquier navegador reciente

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>

( Editar ) A continuación se muestran los resultados en mi PC cuando publiqué esta respuesta hace 15 meses. Lo intenté hoy y es 100 veces más rápido en la misma PC, ¡solo con una versión alfa de 64 bits de Firefox (y Chrome se queda muy atrás)! - hora actual con Firefox 40 Alpha 64 bit: ~ 2 segundos, Chrome 48: ~ 29 segundos

Salida (en mi PC: el último número es el tiempo de ejecución en milisegundos)

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

Ejemplos

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

Este es un algoritmo recursivo similar al programa Python 3 de @ Sp3000. Consiste en una función infija #que devuelve una lista de todas las permutaciones de todas las soluciones.

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

Con un puntaje de 102 99 92 - 10 = 82 podemos imprimir cada solución solo una vez, ordenadas:

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

Pruébalo en línea.

Descaradamente toma prestado del comentario de xnor ;)

Esto se quedará sin memoria en cualquier computadora en su sano juicio, incluso por un valor como 5,5.0. Define una función, gque se puede llamar como g 3 7.923668178593959.

Este programa de Python 3 usa esencialmente el mismo algoritmo (simplemente no hace la impresión "No" al final, lo que podría hacerse asignando una variable a todos los resultados, luego escribiendo print(K if K else "No") ), pero usa un generador, por lo que no No se produce un error de memoria (aún llevará mucho tiempo, pero lo hice imprimir cuando encuentra los valores):

Esto dio exactamente los mismos resultados que obtuvo @ Sp3000. Además, esto tardó varios días en terminar (no lo cronometré, pero alrededor de 72 horas).

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)

Pitón 3 - 157 174 169 - 10 = 159

Edit1: cambió el formato de salida a enteros separados por espacios en lugar de separados por comas. Gracias por la sugerencia de quitar las llaves alrededor (n, x).

Edit2: ¡Gracias por los consejos de golf! Puedo recortar otros 9 caracteres si solo uso una prueba == en lugar de probar la igualdad aproximada dentro de 1e-6, pero eso invalidaría las soluciones aproximadas, si existe alguna.

Utiliza itertools para generar todas las combinaciones de enteros posibles, con suerte eficientemente :)

No he encontrado una manera de agregar la impresión "No" de manera eficiente, siempre parece tener más de 10 caracteres adicionales.

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

Si no hay permutaciones, este programa no imprime nada.