精华内容
下载资源
问答
  • 寻找勾股数算法的实现和优化 深夜隔壁寝室的老哥来访,说他用python实现的寻找2000以内勾股数的算法跑了20秒钟。邀请我一起讨论优化思路,完成后记录如下: 朴素探数法寻找勾股数 首先实现那个需要20秒钟的朴素...

    快速寻找勾股数算法的实现和优化

    深夜隔壁寝室的老哥来访,说他用python实现的寻找2000以内勾股数的算法跑了20秒钟。邀请我一起讨论优化思路,完成后记录如下:

    朴素探数法寻找勾股数

    首先实现那个需要20秒钟的朴素算法,思路非常简单,三重for循环遍历,利用了勾股数的以下性质:

    a2 + b2 == c2

    python代码实现:

    def gcd(m,n):
        return m if n == 0 else gcd(n,m%n)
    def pytha_naive(max):
        results = []
        for a in range(1,max+1):
            for b in range(a,max+1):
                for c in range(b,max+1):
                    if a*a + b*b == c*c and gcd(a,b) == 1:
                        results.append([a,b,c])
        for l in results:
            print(l)
        print("total : " + str(len(results)))
        return results
        
    

    我已经对这种朴素算法进行了简单优化,以下是注意事项:
    1*,gcd()方法用于递归求公因数,此处用于除去派生勾股数,如6,8,10
    2,b,c两变量无需从1开始遍历
    3*,max是遍历边界,注意range()方法左闭右开的性质参数需填写(1,max+1)
    4*,网络上存在的一种python特色优化:

    def pytha_opt00(lim,x=1,y=3):
        results = []
        ind = 0
        N = [i for i in range(1,lim+1)]
        M = [i*i for i in range(1,lim+1)]
        for i in M:
            for j in M[ind:]:
                if i+j in M:
                    a = N[M.index(i)]
                    b = N[M.index(j)]
                    if gcd(a,b) == 1:
                        c = N[M.index(i+j)]
                        results.append([a,b,c])
            ind += 1
        for l in results:
            print(l)
        print("total : " + str(len(results)))
        return results
    

    算法优化

    尝试了以上算法,发现确实慢的离谱,我通过查阅资料发现一种数学上的优化思路:

    1. 定义:凡符合a2+b2=c2的正整数a,b,c我们称之为一组勾股数。a和b是直角边,c是斜边。
    2. 凡有公约数的勾股数我们称之为派生勾股数,例[30,40,50] 等;
    3. 无公约数的勾股数,例[3,4,5];[8,15,17]等,我们称之为勾股数。
    有:全是偶数的勾股数必是派生勾股数,三个奇数不可能符合定义公式。两偶一奇和两奇一偶都可以被证明不符合公式条件,因此,勾股数唯一的可能性是:
               a和b分别是奇数和偶数(偶数和奇数),斜边c只能是奇数。
    4. 勾股数具有以下特性:
    斜边与偶数边之差是奇数,这个奇数只能是某奇数的平方数, 例1,9,25,49,……
    斜边与奇数边之差是偶数,这个偶数只能是某偶数平方数的一半, 2,8,18,32,……
    5. 由以上定义我们推导出勾股公式:
               a = p2 + q2
               b = q2/ 2 + pq
               c =p2+ q2/ 2 + pq
    6,此公式涵盖了自然界的全部勾股数,包括派生勾股数。
    以任意奇数代入P ,任意偶数代入Q ,即可得到唯一一组勾股数。
    例如P = 5 ,Q = 8 ,得到
    X = 25 + 5×8 = 65
    Y = 32 + 5×8 = 72
    Z = 25 + 32 + 5×8 = 97
    当P与Q有公约数时,例如9与12 ,再例如21与28等,推导出来的是派生勾股数
    当P与Q无公约数时,例如9与8 ,再例如21与16等,推导出来的是勾股数

    (引用来自百度,有修改)
    根据以上数学方法,可以得到一种代码实现思路:
    双重for循环遍历max内的奇数a和偶数b,
    如果gcd(a,b) == 1:
    如果t = aa + bb <= max :
    寻找到一组勾股数(a,b,c=pow(t,0.5))
    优化:当 aa + bb > max时,跳出第二重循环
    最后对结果进行简单处理
    python实现如下:

    def gcd(m,n):
        return m if n == 0 else gcd(n,m%n)
    def pytha_opt01(max):
        # find numbers
        results = []
        for i in range(1,max+1,2):
            for j in range(2,max+1,2):
                if gcd(i,j) == 1 :
                    t = pow(i*i+j*j,0.5)
                    if t > max:
                        break
                    elif int(t) == t:
                        t = int(t)
                        results.append([i,j,t])
        # handle the resulta
        for l in results:
            l.sort()
        results.sort()
        for l in results:
            print(l)
        print("total : " + str(len(results)))
        return results
    

    效率提升非常明显,如果没有特殊需要,代码中的列表排序完全可以去除。

    展开全文
  • 算法提高 勾股数

    千次阅读 2017-02-15 11:53:58
     勾股数是一组三个自然数,a  输出所有a + b + c  a小的先输出;a相同的,b小的先输出。 输出格式  每行为一组勾股数,用空格隔开 样例输出 例如,结果的前三行应当是 3 4 5 5 12 13 6 8 10
    问题描述
      勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形
      输出所有a + b + c <= 1000的勾股数
      a小的先输出;a相同的,b小的先输出。
    输出格式
      每行为一组勾股数,用空格隔开
    样例输出
    例如,结果的前三行应当是
    3 4 5
    5 12 13
    6 8 10

    #include<stdio.h>
    int main()
    {
    	int i,j,k;
    	for(i=1;i<1000;i++)
    	{
    		for(j=i;j<1000;j++)
    		{
    			for(k=j;k<1000;k++)
    			{
    				if(i+j+k<=1000 && i*i+j*j==k*k)
    				{
    					printf("%d %d %d\n",i,j,k);
    				}
    			}
    		}
    	}
    	return 0;
    }


    展开全文
  • Java实现 蓝桥杯VIP 算法提高 勾股数

    万次阅读 多人点赞 2019-06-22 00:10:24
    算法提高 勾股数 时间限制:1.0s 内存限制:256.0MB 问题描述  勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形  输出所有a + b + c <= 1000的勾股数  a小的先...

    算法提高 勾股数
    时间限制:1.0s 内存限制:256.0MB
    问题描述
      勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形
      输出所有a + b + c <= 1000的勾股数
      a小的先输出;a相同的,b小的先输出。
    输出格式
      每行为一组勾股数,用空格隔开
    样例输出
    例如,结果的前三行应当是
    3 4 5
    5 12 13
    6 8 10

    
    public class 勾股数 {
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		for (int a = 3; a <=1000; a++) {
    			for (int b =a+1; b < 1000; b++) {
    				int c=(int) Math.sqrt(a*a+b*b);
    					if(a<b&&b<c){
    						if(a+b+c<=1000){
    							if(a*a+b*b==c*c){
    								System.out.println(a+" "+b+" "+c);
    							}
    						}
    					
    					
    				}
    			}
    			}
    		}
    
    }
    
    
    展开全文
  •  勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形  输出所有a + b + c <= 1000的勾股数  a小的先输出;a相同的,b小的先输出。 输出格式  每行为一组勾股数,用...

    问题描述
      勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形
      输出所有a + b + c <= 1000的勾股数
      a小的先输出;a相同的,b小的先输出。
    输出格式
      每行为一组勾股数,用空格隔开
    样例输出
    例如,结果的前三行应当是
    3 4 5
    5 12 13
    6 8 10
    资源限制
    时间限制:1.0s 内存限制:256.0MB

    PS:由勾股定理得:a×a + b×b = c×c

    代码块

    public class Main {
    	public static void main(String[] args) {
    		
    		for(long i = 3; i < 999; i++){
    			for(long j = i+1; j < 1000; j++){
    				for(long k = j+1; k <= 1000; k++){
    					if(i*i + j*j == k*k && i+k+j <= 1000){
    						System.out.println(i+" "+j+" "+k);
    						//System.out.println(" "+i*i+" "+j*j+" "+k*k);
    					}
    				}
    			}
    		}
    	}
    }
    

    评测结果
    在这里插入图片描述

    展开全文
  • 勾股数是一组三个自然数,a &amp;lt; b &amp;lt; c,以这三个数为三角形的三条边能够形成一个直角三角形  输出所有a + b + c &amp;lt;= 1000的勾股数  a小的先输出;a相同的,b小的先输出。 输出格式 ...
  • 勾股数的高效方法,避免三重循环,时间复杂度大大降低。当然,如果再其中应用一下快排函数sort()能够更快地实现。思想不难,代码清晰。
  • 勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形  输出所有a + b + c <= 1000的勾股数  a小的先输出;a相同的,b小的先输出。 输出格式 每行为一组勾股数,用空格...
  • 算法提高 勾股数 时间限制:1.0s 内存限制:256.0MB 问题描述  勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形  输出所有a + b + c <= 1000的勾股数  a小...
  • 勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形 输出所有a + b + c <= 1000的勾股数 a小的先输出;a相同的,b小的先输出。 输出格式 每行为一组勾股数,用空格隔...
  •  勾股数是一组三个自然数,a  输出所有a + b + c  a小的先输出;a相同的,b小的先输出。 输出格式  每行为一组勾股数,用空格隔开 样例输出  例如,结果的前三行应当是  3 4 5  5 12 13 ...
  •  勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形  输出所有a + b + c <= 1000的勾股数  a小的先输出;a相同的,b小的先输出。 代码如下: import java.util....
  • 题目描述 勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形 输出所有a + b + c < = 1000的勾股数 a小的先输出;a相同的,b小的先输出。 输入 无 输出 每行为一组勾股...
  • 勾股数是一组三个自然数,a < b < c,以这三个数为三角形的三条边能够形成一个直角三角形 输出所有a + b + c < = 1000的勾股数 a小的先输出;a相同的,b小的先输出。 输入 无 输出 每行为一组勾股数,...
  • 1000以内的勾股数算法流程图描述

    千次阅读 2011-02-27 08:56:00
    上节课给学生布置了3道课后作业题,其中一道题目是求1000以内的勾股数,用流程图描述出来。这节课上课前就要评讲的,本着对学生负责的态度,我也认真去思考了这3道题,其中就数这道最难。想上网搜搜又没有现成的,...
  • 这篇文章讲述的是算法趣味整数部分的勾股数问题的java实现,参考的书籍为清华大学出版社出版,贾蓓等编著的《c语言趣味编程1000例》,如有错误或者不当之处,还望各位大神批评指正。 问题描述 求100以内的所有勾股...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,143
精华内容 857
关键字:

勾股数的算法