Задача на пребор.

[Ангелика А]

Не могу решить задачу...кто может помочь помогите...
Дано натуральное число N<=2000000000.Представить его в виде суммы квадратов натуральных чисел,содержащей наименьшее число слагаемых.


Я пыталась решать находя в начале Sqrt(n) и потом в цикле от 1 до Sqrt(n)
находила самое близкое число к N...
Дальше вроде как можно через repeat и untill или через while и тут у меня загвоздка.....я не знаю как поделить действия до этих операторов и после...не знаю куда это нужно вписать....и как сохранить все слагаемые...

[LeBron]

? Нда... Если Вы даже писать не умеете... Ну ладно, может я просто неправильно Вас понял. Ладно, вот вам первый алгоритм решения, который приходит в голову: Сначала смотрим, является ли полным квадратом. Если да - ответом будет 1 число, которое мы нашли. Если нет - далее классическим "оптимизированным полным" перебором проверяем для 2 чисел - если нашли пару, то она ответ, иначе - ответа в виде суммы 2 нету. Далее чуть сложнее уже, надо подумать. Само количество слагаемых находится с помощью теоремы Лагранжа, а вот как сами числа найти - вопрос не ясный. Подумаю сейчас немного, может что-то и придумаю.
З.Ы. Все, вспомнил, как такое делать. Ищите Rabin-Shallit algo, сам алго точно есть, а реализация... На С++ когда-то видел, а на Паскале - даже не знаю, хватит ли кому-нибудь глупости выложить в сеть такое на Паскале.

[Anatole]

Здесь напрашивается использование процедуры с перебором чисел от sqrt(n) до 1,в которой от заданного числа отнимаем квадрат счётчика, а дальше рекурсивный вызов этой же процедуры с меншим значением параметра.

[LeBron]

Вполне логично для всех "рекурсивщиков". Только вот красиво упадет Правда, не знаю, из-за чего - ведь можно оформить так, что раньше закончиться время, а можно так, что раньше закончиться стек рекурсии.

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

[Ангелика А]

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

[LeBron]

Как вариант - тупой перебор. Если Вы не учили способ решения этой задачи с математических дисциплин, то я слабо себе представляю, на что ожидает от Вас препод. Или лично Вы столь отстаете от своей гениальной группы, или препод очень уж высокого мнения о Вас лично и о группе вообще. Изучая язык, обычно делают задачи "для криворуких дебилов", а эту я б к таким не отнес. А такую задачу можно давать для поиска "небезнадежных", что никто делать в процессе изучения кодинга не будет. У Вас есть связь с кем-нибудь другим из группы? Может попытайтесь узнать, что делают они? задание ведь не персональное, как я понял.

[Anatole]

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

[LeBron]

Anatole, нет. Стек нам не спасти. Во-первых, нету смысла искать "лучше", так как за тысячные доли секунды можно точно определить, сколько именно будет слагаемых. Во-вторых, Вы слабо представляете себе количество вызовов, которые получатся. Допустим, мы перебираем всего 2 слагаемых (доказали, что ответ 3, а не 4, и третье определяем с помощью суммы первых 2). Корень из миллиарда - это будет где-то 31620 (влом калькулить), значит, число 31620 сгенерит 31620 запросов, 31619 - 31619 запросов, и так далее. В результате получим почти полмиллиарда вызовов. Даже после оптимизации проверкой на "половинную перекрываемость" число уменьшиться не достаточно сильно, чтоб наша программа работала в пределах секунды или 2 секунд. (на моем компъютере получилось число чуть более 100 млн, это даже для 5 секунд наверно многовато при вложеных циклах и алгебраических операциях) А это еще даже не 4 числа, а только 3. Перебор же, работая аналогично, упадет точно так же, только без обвала стека.
Я уже проверил, алгоритм, который я указал, в сети отгугливаеться

[Ангелика А]

Я не отстала от группы...Нам преподователь на практику задает лабораторные работы и всем разные.Совпадения незначительные...а конкретно такое же задание только еще сложней представить в виде суммы факториалов ...и успехов в нем тоже нет...Распределение этих работ происходит методом тыка.Просто нам с девчонкой еще "повезло" всем препод выдал аналогичные задачи только с разными цифрами и даже показал метод решения...типовую программу...а мы "решайте сами"...
Можете выложить фрагмент программы готового перебора...я попробую перенести на свой лад..?
Заранее спасибо

[LeBron]

Сообщение от Ангелика А

Можете выложить фрагмент программы готового перебора...я попробую перенести на свой лад..?
Заранее спасибо

Да что уж готовый передирать, вот Вам наводящие куски кода конкретно в эту тему:

n:=trunc(sqrt(nmb));
for i:=1 to n do for j:=1 to n do for t:=1 to n do if i*i+j*j+t*t=nmb then writeln(i,' ',j,' ',t);

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

n:=trunc(sqrt(nmb));
for i:=1 to n do begin q:=trunc(sqrt(i));
for j:=1 to q do begin t:=nmb-i*i-j*j;
if trunc(sqrt(t))=sqrt(t) then writeln(i,' ',j,' ',t);end;end;

здесь мы уже не перебираем третье число из всех вариантов, а выбираем значение, которое получается с учетом первого и второго. Так же мы не можем взять слишком большое второе - тогда сумма квадратов точно будет больше, следовательно, перебирать такие варианты нету смысла.
Эти коды можно еще оптимизировать, к примеру, если Вы воспользуетесь первым вариантом, то вам каждую возможную тройку выдасть 6 раз (в виде 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1)). Для устранения этой проблемы и ускорения работы, отбрасываються варианты, которые рассматриваються несколько раз из-за перестановки слагаемых. Самый простой способ - перебирать так, чтобы числа шли в порядке неубывания. На примере первого перебора:

n:=trunc(sqrt(nmb));
for i:=1 to n do for j:=i to n do for t:=j to n do if i*i+j*j+t*t=nmb then writeln(i,' ',j,' ',t);

В этом варианте не может получиться триплет из чисел, которые идут не в порядке неубывания. Да и перебор уменьшен в 3!=6 раз.
Думаю, дальше сможете написать сами хоть что-то. Попытайтесь, выложите наработки сюда, с исправлением - помогут.