SB
https://www.geeksforgeeks.org/minimum-number-of-squares-whose-sum-equals-to-given-number-n/ - первый результат в гугле
Плохой алгоритм
Size: a a a
2020 March 05
SB
Даже на 1000 он уже не хочет работать
SB
Не говоря уже на 10 в 5
A
там две реализации, попробуй вторую
A
да, первая экспоненциальная
SB
О да, вторая работает))
SB
Спасибо
SB
Но надо теперь
1)понять как
2)вывести эти самые квадраты
1)понять как
2)вывести эти самые квадраты
SB
Пожалуй этим я и займусь, если не получится, напишу через пару десятков минут
A
как - рекурсивно с запоминанием промежуточных результатов
SB
Мне удалось упростить алгоритм, и он работает, но я так и не понял куда тут вставлять сами сгенерированный квадраты
SB
Вот мой алгоритм
SB
Максимально простой
SB
Я даже убрал лишние присваивания оттуда и заменил на вектор
SB
Оно получается запоминает квадраты вообще для всех чисел
SB
Но как разобрать это на сами квадраты?
A
твой вектор squares это число квадратов. Ты можешь параллельно вести вектор "набор квадратов"
A
и изначально его заполнять как i единиц, а в строке 13 сделать что if squares[i] < 1 + squares[jj], то поменять его на jj плюс squares[jj]
A
кстати, у тебя там ошибка, должно быть не squares[jj], а squares[i-jj]