|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 07 Mar 2003 21:43:32
To : Vjacheslav Maslov
Subject : Re: задачка: A^3+B^3+C^3=D^3
--------------------------------------------------------------------------------
"Vjacheslav Maslov" <Vjacheslav.Maslov@p60.f231.n5000.z2.fidonet.org> wrote
in message news:1046888490@p60.f231.n5000.z2.ftn...
> /*Доброго времени суток*/, All !
>
> Хочу предложить такую задачку: найти все натуральные числа меньшие 1000,
> которые удовлетворяют уравнению:
>
> A^3+B^3+C^3=D^3.
[skip]
> Работает, но медленно где-то 5-7 минут. Один мой знакомый утверждает, что
> придумал алгоритм решения этой задачи, который отрабатывает за 2 сек на
машине
> класса P III.
#include <math.h>
#include <stdio.h>
int main(){
int const N =1000;
int i3[N+1];
for(int i=1; i<=N; ++i) i3[i] =i*i*i;
int const M =N/pow(3.0,1.0/3.0);
int const L =N/pow(2.0,1.0/3.0);
for(int a =1; a<M; ++a){
int a3 =i3[a];
for(int b=a; b<=L; ++b){
int b3 =i3[b];
int a3_b3 =a3+b3;
int a3_b3_b3 =a3_b3+b3;
int d =b+1; // or d =b*pow(2.0,1.0/3.0)
int d3 =i3[d];
while(d3<a3_b3_b3) d3 =i3[++d]; // or bsearch in i3[b+1:2*b]
if(d>N) break;
if(d3==a3_b3_b3) printf("%i^3 + %i^3 + %i^3 = %i^3\n",a,b,b,d);
for(int c=b+1; c<N; ++c){
int a3_b3_c3 =a3_b3+i3[c];
while(d <=N && d3 < a3_b3_c3) d3 =i3[++d];
if(d>N) break;
if(d3==a3_b3_c3) printf("%i^3 + %i^3 + %i^3 = %i^3\n",a,b,c,d);
}
}
}
}
работает около 1 сек (правда на P4 1.8 :)
комментарии показывают места,
где можно еще чуть ускорить (на 10-20%)
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
