Господа всем привет. Столкнулся с проблемой, которая озвучена в названии темы. Погугля выяснил, что любое натуральное число(меня интересуют только числа до 2*10^9) можно разбить на сумму не более чем 9 кубов. Но здесь речь идет об оптимальном разбиении. Первое что пришло в голову, это реализовать жадный алгоритм. Но конечно он неэффективен. К примеру те же 2*10^9 он представляет в виде суммы 9 кубов, хотя можно представить в виде двух. Может кто нить знает как это делать? Буду благодарен на справочный материл по этой тематике
Здравствуйте, UnderFelixAbove, Вы писали:
UFA>Господа всем привет. Столкнулся с проблемой, которая озвучена в названии темы. Погугля выяснил, что любое натуральное число(меня интересуют только числа до 2*10^9) можно разбить на сумму не более чем 9 кубов. Но здесь речь идет об оптимальном разбиении. Первое что пришло в голову, это реализовать жадный алгоритм. Но конечно он неэффективен. К примеру те же 2*10^9 он представляет в виде суммы 9 кубов, хотя можно представить в виде двух. Может кто нить знает как это делать? Буду благодарен на справочный материл по этой тематике
А что значит "оптимальное" разбиение? Минимальное количество кубов?
Кубический корень 2*10^9 ~ 1250, то есть тебе достаточно создать сортированый массив со всеми кубами от 0 до ~1250 и рекурсивно пройтись по нему. С отсеканием лишних вариантов должно работать очень быстро.
Здравствуйте, Mace, Вы писали:
M> С отсеканием лишних вариантов должно работать очень быстро.
Немного подумал и забираю свои слова назад =) Самый быстрый алгоритм, который приходит в голову — O(N^(1+1/3)), но он требует N байтов памяти. N — максимальное возможное значение числа, которое нужно разложить.
Здравствуйте, Багер, Вы писали:
Б>Здравствуйте, UnderFelixAbove, Вы писали:
UFA>>любое натуральное число можно разбить на сумму не более чем 9 кубов.
Б>Нипанятно... Разложите хоть бы неоптимально 670 000 (шестьсот семьдесят тысяч).
Это достаточно известный факт, именуемый в простонародии теоремой Варинга.
В общем виде это выглядит так: каждое натуральное число есть сумма не более, чем k(n) натуральных чисел в степени n.
Лагранж доказал, что любое натуральное число есть сумма не более чем 4 квадратов, g(2) = 4.
Варинг показал, что g(3) = 9.
Далее, g(4) = 19, g(5) = 37. И т.д.
Хотелось бы еще раз пояснить, что имелось под неоптимальным разбиением исходного натурального числа N. Имеем массивчик, состоящий из кубов натуральных чисел, максимальное значение которого(куба) не превосходило 2*10^9. Далее выбирается максимальный элемент из этого массивчика, который меньше текущего числа N, забиваем его в ответ и уменьшаем N на это значение. Так повторяем пока не от числа N не останется бублик. Для озвученного числа 670000 получается следующее разбиение (N = a1^3 + a2^3 + ... an^3, я представлю список только ai): 87 22 9 43 3 1 1 .
Спасибо за позновательную ссылку на английском языке: спасибо за интересную теорему, хоть буду знать, как она называется и кто из Великих творил в этом направлении, и за то, что напомнили, что английский не сдан с лета((.
Все же остается интересным не то, как доказать, что количество кубов в сумме числа не превосходит 9, а то как получить такое разбиение
Здравствуйте, UnderFelixAbove, Вы писали:
UFA>Хотелось бы еще раз пояснить, что имелось под неоптимальным разбиением исходного натурального числа N. Имеем массивчик, состоящий из кубов натуральных чисел, максимальное значение которого(куба) не превосходило 2*10^9. Далее выбирается максимальный элемент из этого массивчика, который меньше текущего числа N, забиваем его в ответ и уменьшаем N на это значение. Так повторяем пока не от числа N не останется бублик. Для озвученного числа 670000 получается следующее разбиение (N = a1^3 + a2^3 + ... an^3, я представлю список только ai): 87 22 9 43 3 1 1 .
UFA>Спасибо за позновательную ссылку на английском языке: спасибо за интересную теорему, хоть буду знать, как она называется и кто из Великих творил в этом направлении, и за то, что напомнили, что английский не сдан с лета((.
UFA>Все же остается интересным не то, как доказать, что количество кубов в сумме числа не превосходит 9, а то как получить такое разбиение
А такой алгоритм, по идее, не всегда даст <=9 кубов. Или для чисел до 2*10^9 всегда?
Здравствуйте, vadimcher, Вы писали:
V>А такой алгоритм, по идее, не всегда даст <=9 кубов. Или для чисел до 2*10^9 всегда?
Честно говоря не проверял. Меня интересует оптимальное разбиение, при котором количество кубов в разбиении будет минимальным. А приведенный алгоритм не дает оптимального разбиения
Здравствуйте, UnderFelixAbove, Вы писали:
UFA>Хотелось бы еще раз пояснить, что имелось под неоптимальным разбиением исходного натурального числа N. Имеем массивчик, состоящий из кубов натуральных чисел, максимальное значение которого(куба) не превосходило 2*10^9. Далее выбирается максимальный элемент из этого массивчика, который меньше текущего числа N, забиваем его в ответ и уменьшаем N на это значение. Так повторяем пока не от числа N не останется бублик. Для озвученного числа 670000 получается следующее разбиение (N = a1^3 + a2^3 + ... an^3, я представлю список только ai): 87 22 9 43 3 1 1 .
UFA>Спасибо за позновательную ссылку на английском языке: спасибо за интересную теорему, хоть буду знать, как она называется и кто из Великих творил в этом направлении, и за то, что напомнили, что английский не сдан с лета((.
UFA>Все же остается интересным не то, как доказать, что количество кубов в сумме числа не превосходит 9, а то как получить такое разбиение
Разбиение оптимальное, но очень медленное(извиняюсь за не очень красивый код, писал чисто для проверки):
#include <iostream>
#include <vector>
using namespace std;
int cubes[1300];
int best[10];
int bestCount;
int cur[10];
int H;
int bSearch(int x)
{
int h = H, l = 0, m;
while(h - l > 1)
{
m= l + (h - l) / 2;
if(cubes[m] > x)
{
h = m;
}
else
{
l = m;
}
}
return cubes[h] <= x ? h : l;
}
void rec(int n, int summ, int index)
{
if(index == bestCount)
{
return;
}
int i;
int delta = n - summ;
int start = bSearch(delta);
if(cubes[start] == delta) // found
{
cur[index] = delta;
for(i = 0;i <= index; i++)
{
best[i] = cur[i];
}
bestCount = index + 1;
}
else
{
for(i = start; i > 0; i--)
{
cur[index] = cubes[i];
rec( n, summ + cubes[i], index + 1);
}
}
}
int main()
{
int i,n;
bestCount = 10;
for(i = 0; i * i * i <= 2000000000; i++)
{
cubes[i] = i * i * i;
}
H = i - 1;
cin >> n;
rec( n, 0, 0);
for(i = 0; i < bestCount; i++)
{
cout << best[i] << ' ';
}
return 0;
}
