Алгоритм — Найти наименьшее целое число, которое соответствует уравнению в переполнении стека
Возможный дубликат:
В поисках номеров Харди Рамануджана
Мне нужно найти наименьшее натуральное число x где
x = k^3 + l^3 = i^3 + j^3
а также (k, l, i, j) Все должно быть по-другому.
Я попробовал следующие четыре цикла for, но я не смог найти правильное решение из-за бесконечно увеличивающихся переменных …
for (int i=0;;i++)
for (int j=i+1;;j++)
for (int k=j+1;;k++)
for (int l=k+1;;i++)
compare(i,j,k,l);
Решение
Вы должны пересмотреть, как вы думаете о проблеме.
Это действительно говорит так: что наименьшее натуральное число, выражаемое суммой двух кубов двумя разными способами?
Постановка задачи называет это число x, а пары кубов — это (i, j) и (k, l).
Перефразировано таким образом, это не так уж плохо. Вот подсказка в псевдокоде:
function count_num_cubic_pairs(n):
cubic_pairs = []
for i..n:
first_cube = i * i * i
remainder = n - first_cube
if remainder is a cube and (first_cube, remainder) not in cubic_pairs:
cubic_pairs.add((first_cube, remainder))
return length(cubic_pairs)
Трудная часть будет проверять, remainder is a cube — ошибки с плавающей запятой сильно это усложнят. В этом суть проблемы — развлекайся.
Другие решения
Один простой способ заставить ваш код работать, это ограничить область ваших переменных, а затем постепенно расширять ее.
Как упоминал мазай, вы сохраняете каждую переменную строго больше, чем предыдущие, поэтому у вас никогда не будет изменений, которые могли бы быть правильными.
Нечто подобное может работать (псевдокод), но это ужасно неэффективно:
for max in [100, 200, 300, ...]
for i in [0..max]
for j in [0..max]
for k in [0..max]
for l in [0..max]
if (i equals k or l, or j equals k or l) continue
if (i^3 + j^3 equals k^3 + l^3)
return answer
int i = 1
int j = 3
int k = 2
int l = 4
do {
do {
do {
do {
compare(i, j ,k l);
i++;
} while (i < k);
k++;
} while (k < j);
j++;
} while(j < l);
l++;
} while(l < 100);
Примерно так пробует каждую комбинацию чисел без дублирования (до значений 100), с < К < J < л.
Ваши петли предполагают i<j<k<l, что не обязательно верно. (Это может быть j>k. Как только вы получите правильные предположения, вы можете изменить порядок петель, чтобы первый элемент был самым большим, а остальные петли были ограничены.
Вот пример с i>j, i>k>l,
for (int i=1;;i++)
for (int j=1;j<i;j++)
for (int k=1;k<i;k++)
for (int l=1;l<k;i++)
compare(i,j,k,l);
Как только вы это заработаете, попробуйте исключить четвертый цикл, проверив, является ли корень куба i*i*i+j*j*j-k*k*k это натуральное число. Затем попробуйте найти более разумное начальное значение для k,