SB
тут вроде алгоритм без этого
Size: a a a
2020 March 05
K
из этих двух ссылок следует более простой алгоритм, если что
SB
если я буду еще эти формулы щас искать, то я точно не успею сделать, лол
SB
из этих двух ссылок следует более простой алгоритм, если что
т.е более простой?
SB
так это, у меня осталось 20 минут, я не успею написать другой, надо доработать этот
SB
он работает, но не до конца
SB
твой вектор squares это число квадратов. Ты можешь параллельно вести вектор "набор квадратов"
я сделал этот вектор, я хз как его заполнять
SB
вообще не понимаю, неужели придется цикл назад идти?
SB
а по этим формулам можно найти сами квадраты
SB
имея число и зная кол-во квардатов?
A
изначальное заполнение - засунуть туда i единиц
A
в смысле у тебя должен быть вектор векторов и i-й вектор изначально содержит в себе i единиц
A
а дальше когда ты нашел, что для некоторого x, решение для i-x*x короче, чем текущее для i, ты полностью заменяешь i-й вектор на копию j-го+x*x
A
но опять же, тот алгоритм, который реализован там, он сразу генерит полностью ответы вообще для всех чисел от 1 до n
DK
Число разбить на сумму квадратов, да так чтобы кол-во квадратом было наименьшим
Теорема Лагранжа
A
а если ты хочешь только для n, то можно просто рекурсивно опуститься и будет проще
DK
Любое число представимо в виде суммы четырех квадратов целых чисел
DK
Может поможет
DK
Следовательно, ответ не больше четырех
DK
Кек, уже не поможет, время вышло))