Ваша задача - преобразовать десятичные дроби обратно в сумму квадратных корней целых чисел. Результат должен иметь точность не менее 6 значащих десятичных цифр.

Вход :

Число, указывающее количество квадратных корней, и десятичное число, указывающее число для аппроксимации.

Пример ввода:

2 3.414213562373095

Вывод : целые числа, разделенные пробелами, которые при квадратном корне и сложении приблизительно соответствуют исходному десятичному знаку с точностью не менее 6 значащих десятичных знаков.

Нули не допускаются в решении.

Если есть несколько решений, вам нужно распечатать только одно.

Пример вывода (в любом порядке):

4 2

Это работает, потому что Math.sqrt(4) + Math.sqrt(2) == 3.414213562373095 .

Это код гольф. Самый короткий код (с дополнительным бонусом) выигрывает!

Всегда будет решение, но -10, если ваша программа выводит «Нет», когда нет решения с целыми числами. Кроме того, -10, если ваша программа печатает все решения (разделенные символом новой строки или точкой с запятой или что-то еще) вместо одного.

Тестовые случаи:

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

И да, ваша программа должна завершиться за конечное время, используя ограниченную память на любой разумной машине. Это не может просто работать «в теории», вы должны быть в состоянии действительно проверить это.

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

(Мега спасибо @xnor за советы, особенно реструктуризацию цикла for)

Простая рекурсивная попытка. Он начинается с целевого числа и непрерывно вычитает квадратные корни, пока не достигнет 0 или ниже. Функция Sможет быть вызвана какS(2,3.414213562373095) (второй аргумент считается положительным).

Программа не просто распечатывает все решения, она печатает все варианты решений (немного посторонний, я знаю). Вот вывод для последнего случая: Pastebin .

Небольшая настройка дает решение 98 - 10 = 88, которое не печатает перестановки, что делает его более эффективным:

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

И просто для удовольствия, этот 99 - 10 = 89 один настолько эффективен, насколько это возможно (в отличие от других, он не бьет стек 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

Обратите внимание, что, хотя у нас есть изменяемый аргумент по умолчанию, это никогда не вызывает проблем, если мы перезапустим функцию, поскольку создаем n+[i]новый список.

Доказательство правильности

Чтобы попасть в бесконечный цикл, мы должны достичь некоторой точки, где x <0 и 0.1 + x ² > 1 . Это удовлетворяет й <-0,948 ... .

Но обратите внимание, что мы начинаем с положительного значения x, а x всегда уменьшается, поэтому для достижения x <-0,948 ... у нас должно быть x '- i ^0,5 <-0,948 ... для некоторых x'> -0,948 .. . Перед х и положительного целого числа я . Для запуска цикла while у нас также должно быть 0.1 + x ' ² > i .

Переставляя, мы получаем x ' ² + 1.897x' + 0,948 <i <0,1 + x ' ² , внешние части подразумевают, что x' <-0,447 . Но если -0,948 <x '<-0,447 , то ни одно положительное целое число i не сможет заполнить пробел в вышеприведенном неравенстве.

Следовательно, мы никогда не попадем в бесконечный цикл.

Эклипс Пролог - 118 (138-20)

Я использовал следующую реализацию Пролога: 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).

Это очень наивный, экспоненциальный подход. Перечисление всех возможных решений требует времени, чтобы охватить все комбинации ( правка : диапазон посещаемых целых чисел теперь уменьшается на каждом шаге, что устраняет множество бесполезных комбинаций).

Здесь следует стенограмма тестовой сессии. По умолчанию среда пытается найти все возможные решения (-10) и выводит «Нет», если это не удается (-10).

Как правильно отметил Sp3000 в комментарии, он также печатает «Да», когда это удается. Это, безусловно, означает, что я могу снять еще 10 очков ;-)

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

(Изменить) Что касается производительности, то она довольно хорошая, по крайней мере, по сравнению с другими (см., Например, этот комментарий от FryAmTheEggman ). Сначала, если вы хотите распечатать все результаты, добавьте следующий предикат:

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

См http://pastebin.com/ugjfEHpw для (5,13.0) случая, который завершает в 0,24 секунде и найти решение (495 , но , возможно , я пропускаю какое - то решение, я не знаю).

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

Эта функция возвращает строку «Нет» или строку со значениями, разделенными пробелами. Он (неэффективно) обрабатывает все возможные значения, кодируя их в большое целое число и начиная с более высоких значений. 0 не разрешены в решении, и закодированный 0 представляет все единицы. Ошибка в квадрате.

Пример:

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 "

Пожалуйста, будьте терпеливы, так f(5,13.0)как пространство поиска функции составляет 13 ^ 10. Это может быть сделано быстрее с 2 дополнительными байтами.

Python 3 2: 173 159 - 10 = 149

Объяснение: Каждое решение имеет вид x_1 x_2 ... x_n с 1 <= x_1 <= x ^ 2, где x - целевая сумма. Поэтому мы можем закодировать каждое решение как целое число в базе x ^ 2. Цикл while перебирает все (x ^ 2) ^ n возможностей. Затем я конвертирую целое число обратно и проверяю сумму. Довольно прямо вперед.

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

Он находит все решения, но последний контрольный пример занимает слишком много времени.

JavaScript (ES6) 162 (172 - 10) 173

Редактировать Немного короче, чуть медленнее.

Как функция с 2 параметрами, вывод на консоль javascript. При этом печатаются все решения без повторений (сгенерированные кортежи решений уже отсортированы).
Я больше заботился о времени, чем о количестве символов, так что его легко протестировать в консоли браузера в течение стандартного ограничения времени javascript.

(Обновление за февраль 2016 года) Текущее время последнего тестового случая: около 1 150 секунд . Требования к памяти: незначительные.

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

Версия ES 5 Любой браузер

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

Тестовый Фрагмент, который он должен запустить на любом недавнем браузере

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>

( Изменить ) Ниже приведены результаты на моем ПК, когда я разместил этот ответ 15 месяцев назад. Я попробовал сегодня, и это в 100 раз быстрее на том же ПК, только с 64-битной альфа-версией Firefox (а Chrome сильно отстает)! - текущее время с Firefox 40 Alpha 64 bit: ~ 2 с, Chrome 48: ~ 29 с

Вывод (на моем ПК - последний номер - время выполнения в миллисекундах)

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

Примеры

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

Это рекурсивный алгоритм, похожий на программу Python 3 @ Sp3000. Он состоит из инфиксной функции, #которая возвращает список всех перестановок всех решений.

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

Со счетом 102 99 92 - 10 = 82 мы можем напечатать каждое решение только один раз, отсортировав:

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

Попробуйте онлайн.

Бесстыдно заимствует из комментария xnor ;)

Это исчерпает память на любом нормальном компьютере даже для значения как 5,5.0 . Определяет функцию, gкоторую можно вызвать как g 3 7.923668178593959.

Эта программа на Python 3 использует, по сути, тот же алгоритм (просто не выполняет печать «Нет» в конце, что можно сделать, назначив переменную всем результатам, затем записав print(K if K else "No") ), но использует генератор, поэтому он не Ошибка памяти (это все равно займет очень много времени, но я распечатал ее, когда нашел значения):

Это дало те же самые результаты, которые получил @ Sp3000. Кроме того, это заняло несколько дней, чтобы закончить (я не рассчитывал, но около 72 часов).

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)

Питон 3 - 157 174 169 - 10 = 159

Edit1: изменен формат вывода на разделенные пробелами целые числа вместо запятых. Спасибо за отзыв о снятии скобок (n, x).

Edit2: Спасибо за советы по игре в гольф! Я могу обрезать еще 9 символов, если я просто использую тест == вместо теста на приблизительное равенство с точностью до 1e-6, но это лишит законной силы приблизительные решения, если таковые существуют.

Использует itertools для генерации всех возможных целочисленных комбинаций, надеюсь, эффективно :)

Я не нашел способа эффективно добавить печать «Нет», всегда кажется, что требуется больше 10 дополнительных символов.

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

Скала (397 байт - 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}}

Если перестановок нет, то эта программа ничего не печатает.