| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 573 人关注过本帖
标题:wp231957,关于勾股数
取消只看楼主 加入收藏
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
结帖率:91.67%
收藏
已结贴  问题点数:20 回复次数:0 
wp231957,关于勾股数
由 a*a + b*b = c*c
变形可得 a*a = (c-b) * (c+b)
因此遍历 c-b 就可以得到 b 和 c
比如 a=24
a*a = 576
576 可以是 8*72( 此时b=(72-8)/2,c=(72+8)/2 )
    可以是 6*96( 此时b=(96-6)/2,c=(96+6)/2 )
    可以是 4*144( 此时b=(144-4)/2,c=(144+4)/2 )
这个算法应该是最快的(当然,还可以继续优化,但主体算法不变)

程序代码:
#include <stdio.h>
#include <time.h>

#define N 10000 // 耗时0.140秒,总数12467

int main()
{
    int avoid_optimization = 0;
    clock_t t0 = clock();

    for( unsigned a=1; a<N; ++a )
    {
        for( unsigned c_minus_b=a-1; c_minus_b>0; --c_minus_b )
        {
            if( a*a % c_minus_b != 0 )
                continue;

            unsigned c_plus_b = a*a/c_minus_b;

            if( c_plus_b%2 != c_minus_b%2 )
                continue;

            unsigned b = (c_plus_b - c_minus_b)/2;
            unsigned c = (c_plus_b + c_minus_b)/2;

            if( a > b )
                continue;
            if( c >= N )
                break;

            ++avoid_optimization;
            //printf( "%2d^2 + %2d^2 = %2d^2\n", a, b, c );
        }
    }

    printf( "time = %.3f\ncount = %d\n", (clock()-t0+0.0)/CLOCKS_PER_SEC, avoid_optimization );
    return 0;
}

搜索更多相关主题的帖子: 变形 
2015-01-13 11:46
快速回复:wp231957,关于勾股数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021254 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved