|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Igor Krassikov 2:463/59.1 06 Mar 2003 11:41:00
To : Vjacheslav Maslov
Subject : Re: задачка: A^3+B^3+C^3=D^3
--------------------------------------------------------------------------------
06 Mar 03, Vjacheslav Maslov ==. All:
VM> 2. Затем тройной цикл:
VM> for a:=1 to N do
VM> for b:=1 to N do
VM> for c:=1 to N do begin
VM> if Search(Cubes[a]+Cubes[b]+Cubes[c]) then //найдено
Как минимум, лучше циклы такие: (для ясности я вычисляю кубы на месте)
for(a = 1; a <= 1000; +=a)
{
int a3 = a*a*a;
for(b = a; b < 1000; ++b)
{
int b3 = b*b*b;
if (a3 +b3 > 1000000000) break;
for(c = b; c < 1000; ++c)
{
int c3 = c*c*c;
if (a3+b3+c3 > 1000000000) break;
... собственно проверки ...
Да и проверять, исходя из a <= b <= c, надо только числа а не более 694...
Код ниже на Intel Pentium III 32/256Kb Cache 733.3MHz находит все решения за
29 секунд. Использован алгоритм поиска целочисленного кубического корня.
#include <stdio.h>
inline int Cube(int x) { return x*x*x; };
inline int icbrt(unsigned x)
{
int s = 30;
unsigned y = 0, b;
while(s >= 0)
{
y *= 2;
b = (3*y*(y+1)+1) << s;
s -= 3;
if (x >= b)
{
x -= b;
++y;
}
}
return y;
}
#define N 694 // ceil(1000/exp(log(1000)/3))
void main()
{
int a,b,c,d;
for(a = 1; a <= N; ++a)
{
int a3 = Cube(a);
for(b = a; b <= 1000; ++b)
{
int b3 = Cube(b);
if (a3 + b3 > 1000000000) break;
for(c = b; c <= 1000; ++c)
{
int sum = a3+b3+Cube(c);
if (sum > 1000000000) break;
d = icbrt(sum);
if (Cube(d) == sum) printf("%d %d %d %d\n",a,b,c,d);
}
}
}
}
Всего при таком раскладе проверяется 118807221 тройка, т.е. меньше 12% от
твоего расклада.
Hо! это не более чем улучшение предложенного тобой метода "в лоб" (впрочем,
на порядок...) - наверное, возможны и другие, более хитрые алгоритмы.
Best regards.
Igor
--- That's all
* Origin: KIV ~&C[++!]o (FidoNet 2:463/59.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
