一道算法题，求最优解法？

cugb_cat

原帖由 ypxing 于 2008-4-17 16:23 发表
大家应该探讨有没有低于O(n)的算法

这就是我前面提到的，去找勾股数的公式和定理。

ypxing

其实很想证明：
(a1, b1, c1)
(a2, b2, c2)
(a3, b3, c3)

c3/c2 > c2/c1 > 5

没证出来

wxycyel

命题成立的话也应该是O(N)的算法.

ypxing

命题成立的话，最坏情况是O(n),
但是，会快很多

比如，最好情况下，第一次检查1，第二次检查5，...25, ....125

zicfy

#include <iostream.h> #include <math.h> int main(int argc, char* argv[]) { const int n = 200; float r = 0; for ( int i = 3; i < n; i += 2) { &nbsp;&nbsp;&nbsp;r = sqrt(2 * i * i - 1); &nbsp;&nbsp;&nbsp;if ( r == int(r) ) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout << -(1 - r ) / 2 << " " << -(1 - r) / 2 + 1 << " " << i << endl; } &nbsp;&nbsp;&nbsp;getchar(); &nbsp;&nbsp;&nbsp;&nbsp;return 0; }

hot_ice

import java.io.*;
import java.sql.*;
import java.math.BigDecimal;

/**
* oracle数据库thin协议下操作测试.
*/
public class jie
{
    public static void main(String[] args)
    {
   int i,j,k;
   int N=2000;
   int c;
   long t=System.currentTimeMillis();c=0;
   for(i=2;i<N;i++)
       for(j=2;j<N;j++)
           for(k=2;k<N;k++){c++;
             if((i*i+j*j==k*k)&&(j==i+1))
                 System.out.println(i+" "+j+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");

   t=System.currentTimeMillis();c=0;
   for(i=2;i<N;i++)
       for(k=i+1;k<N;k++){c++;
             if(i*i+(i+1)*(i+1)==k*k)
                 System.out.println(i+" "+(i+1)+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");

   t=System.currentTimeMillis();c=0;
   for(i=2;i<N;i++)
       for(k=(int)(i*1.4);k<N;k++){c++;
             if(i*i+(i+1)*(i+1)==k*k)
                 System.out.println(i+" "+(i+1)+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");

    }
}

N=1000

C:\__>java -cp . jie
3 4 5
20 21 29
119 120 169
696 697 985
用时6529毫秒
3 4 5
20 21 29
119 120 169
696 697 985
用时10毫秒

N=3000

C:\__>java -cp . jie
3 4 5
20 21 29
119 120 169
696 697 985
用时176764毫秒
3 4 5
20 21 29
119 120 169
696 697 985
用时40毫秒


N=2000

C:\__>java -cp . jie
3 4 5次数3996004
20 21 29次数71894062
119 120 169次数467300400
696 697 985次数-1523126926
用时60066毫秒
3 4 5次数1999
20 21 29次数35802
119 120 169次数226913
696 697 985次数1145736
用时10毫秒
3 4 5次数2000
20 21 29次数35745
119 120 169次数224226
696 697 985次数1049714
用时30毫秒

hot_ice

import java.io.*;
import java.sql.*;
import java.math.BigDecimal;
import java.lang.Math;

/**
* oracle数据库thin协议下操作测试.
*/
public class jie
{
    public static void main(String[] args)
    {
   int i,j,k;
   int N=15000;
   int c;
   long t=System.currentTimeMillis();c=0;
/*   for(i=2;i<N;i++)
       for(j=2;j<N;j++)
           for(k=2;k<N;k++){c++;
             if((i*i+j*j==k*k)&&(j==i+1))
                 System.out.println(i+" "+j+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");
*/
   t=System.currentTimeMillis();c=0;
   for(i=2;i<N;i++)
       for(k=i+1;k<N;k++){c++;
             if(i*i+(i+1)*(i+1)==k*k)
                 System.out.println(i+" "+(i+1)+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");

   t=System.currentTimeMillis();c=0;
   for(i=2;i<N;i++)
       for(k=(int)(i*1.4);k<N;k++){c++;
             if(i*i+(i+1)*(i+1)==k*k)
                 System.out.println(i+" "+(i+1)+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");

   double r;
   for(i=3;i<N;i+=2){
   r=Math.sqrt(2*i*i-1);
   if(r-(int)r<0.0005)
   System.out.println((int)((r-1)/2)+" "+(int)((r-1)/2+1)+" "+i);
   }
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");




    }
}

C:\__>java -cp . jie
3 4 5次数14999
20 21 29次数269802
119 120 169次数1747913
696 697 985次数10167736
4059 4060 5741次数52616915
用时891毫秒
3 4 5次数15000
20 21 29次数269745
119 120 169次数1745226
696 697 985次数10071714
4059 4060 5741次数49326832
用时621毫秒
3 4 5
20 21 29
119 120 169
696 697 985
2377 2378 3363 *
4059 4060 5741
8815 8816 12467 *
10496 10497 14845 *
用时631毫秒

hot_ice

import java.io.*;
import java.sql.*;
import java.math.BigDecimal;
import java.lang.Math;

/**
* oracle数据库thin协议下操作测试.
*/
public class jie
{
    public static void main(String[] args)
    {
   int i,j,k;
   int N=150000;
   int c;
   long t=System.currentTimeMillis();c=0;
/*   for(i=2;i<N;i++)
       for(j=2;j<N;j++)
           for(k=2;k<N;k++){c++;
             if((i*i+j*j==k*k)&&(j==i+1))
                 System.out.println(i+" "+j+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");
*/
   t=System.currentTimeMillis();c=0;
   for(i=2;i<N;i++)
       for(k=i+1;k<N;k++){c++;
             if(i*i+(i+1)*(i+1)==k*k)
                 System.out.println(i+" "+(i+1)+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");

   t=System.currentTimeMillis();c=0;
   for(i=2;i<N;i++)
       for(k=(int)(i*1.4);k<N;k++){c++;
             if(i*i+(i+1)*(i+1)==k*k)
                 System.out.println(i+" "+(i+1)+" "+k+"次数"+c);}
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");
   
   t=System.currentTimeMillis();c=0;
   double r;
   for(i=3;i<N;i+=2){
       r=Math.sqrt(2*i*i-1);
       if(r-(int)r<0.000001)
          System.out.println((int)((r-1)/2)+" "+(int)((r-1)/2+1)+" "+i);
   }
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");

   t=System.currentTimeMillis();c=0;
   for(i=3;i<N;i++){
       r=Math.sqrt(i*i+(i+1)*(i+1));
       if(r-(int)r<0.000001)
          System.out.println(i+" "+(i+1)+" "+(int)r);
   }
   i=(int)(System.currentTimeMillis()-t);
   System.out.println("用时"+i+"毫秒");



    }
}

C:\__>java -cp . jie
3 4 5次数14999
20 21 29次数269802
119 120 169次数1747913
696 697 985次数10167736
4059 4060 5741次数52616915
用时891毫秒
3 4 5次数15000
20 21 29次数269745
119 120 169次数1745226
696 697 985次数10071714
4059 4060 5741次数49326832
用时611毫秒
3 4 5
20 21 29
119 120 169
696 697 985
4059 4060 5741
用时0毫秒
3 4 5
20 21 29
119 120 169
696 697 985
4059 4060 5741
用时0毫秒
但是当N更大，又出问题了
C:\__>java -cp . jie
3 4 5次数149999
20 21 29次数2699802
119 120 169次数17542913
696 697 985次数103857736
4059 4060 5741次数600311915
23660 23661 33461次数-1026167122
65536 65537 65537次数-907351004
67648 67649 69697次数-731192316
73676 73677 81003次数-252940588
89731 89732 108667次数843563301
105428 105429 133923次数1666409600
109716 109717 140643次数1848341152
131072 131073 131073次数-1814402012
用时92433毫秒
3 4 5次数150000
20 21 29次数2699745
119 120 169次数17540226
696 697 985次数103761714
4059 4060 5741次数597021832
23660 23661 33461次数-1138096685
用时61639毫秒
3 4 5
20 21 29
119 120 169
696 697 985
4059 4060 5741
6267 6268 47181
17603 17604 84037
用时20毫秒
3 4 5
20 21 29
119 120 169
696 697 985
4059 4060 5741
23660 23661 33461
46564 46565 6445
46811 46812 9363
47863 47864 16937
48439 48440 19945
51860 51861 32925
83367 83368 31865
93243 93244 14451
96532 96533 38173
114500 114501 21235
139343 139344 13361
用时40毫秒

hot_ice

原帖由 liuke432 于 2008-4-17 13:35 发表
有一种数组(a,b,c)，满足条件: a*a+b*b=c*c和b=a+1。例如（3,4,5)。
用程序找出指定范围(1

如果还要求出a^2+b^2=(b+1)^2
比如：5*5+12*12=13*13,怎么解

ypxing

讨论具有这种性质的勾股数的帖子有不少，可以搜索一下