Re: задачка: A^3+B^3+C^3=D^3

From

Sergiy Kanilo ()

To

Vjacheslav Maslov ()

Date

2003-03-07T20:43:32Z

Area

RU.ALGORITHMS

From: "Sergiy Kanilo" <skanilo@artannlabs.com>

"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)