CodePanada

panada 不是熊猫 胜似熊猫
posts(7) comments(3) trackbacks(0)
  • C++博客
  • 联系
  • RSS 2.0 Feed 聚合
  • 管理

常用链接

  • 我的随笔
  • 我的评论
  • 我参与的随笔

留言簿

  • 给我留言
  • 查看公开留言
  • 查看私人留言

随笔分类

  •  C/C++(1)
  •  读研那些事(1)
  •  设计模式(2)
  •  算法(2)
  •  心情(1)

随笔档案

  • 2011年6月 (1)
  • 2011年5月 (6)

常去的地方

  •  C++标准库
  •  陈硕的Blog

搜索

  •  

最新评论

  • 1. re: 用位操作实现的n皇后问题
  • 主要是位操作在线性上的二进制优化。
  • --。。。
  • 2. re: 用位操作实现的n皇后问题
  • 因为一直在做理论研究,所以程序几乎很多都看不懂了。。。谢谢你的推荐~ ps:我是C/C++的坚定粉丝。。呵呵@SonicMisora
  • --熊猫呵呵
  • 3. re: 用位操作实现的n皇后问题[未登录]
  • 八皇后的位运算写法是很基本的……然后要看精彩程序的话建议看下有个用下划线写成的PI计算程序,以及某个开根程序。
    当今世界上用C的程序员有95%都没有真正学会C,当然我也是其中一个。
  • --SonicMisora

阅读排行榜

评论排行榜

View Post

大整数算法之gcd(最大公约数)

欧几里德算法(Euclid)阐述了一种gcd算法。gcd(greatest common divisor),简言之,我们想求gcd(x,y),假设(x>y),如果存在下式:x =  q*y + r,那么则有gcd(x,y) = gcd(y,r) ,其实上式也称为gcd递归定理,即gcd(a,b) = gcd (b,a mod  b)。
这个递归式看似很简单。实则它还是很值得推敲的,首先,它怎么证明?其次,该算法的运行时间为如何?
在密码学中,欧几里德算法有着相当广泛的应用,譬如求乘法逆元,大整数分解等等。。
在<<编程之美>>一书中,给出了不少gcd算法的简单实现。因为gcd算法的实现是递归,所以要特别注意栈溢出。先做个标记,以后会把栈详细分析一下。
 最简单的gcd算法:
         
1int gcd(int x, int y)
2{
3     if(y == 0) return x;    
4     if(x < y)      return gcd(y,x);    
5     else        return gcd(y, x%y); 
6}
 

ACM中常用的gcd算法:
1int gcd(int a, int b){ return a == 0 ? b : gcd(b % a, a); } 

经过优化的gcd算法(分成奇偶两种情况):
 1int gcd(int x,int y )
 2{
 3    if(x < y) return gcd(y,x);  // x>y
 4    if( y == 0) return x;  // if y=0, x is GCD 
 5    else
 6    {
 7         if( !(x%2) )
 8         {                 
 9           if( !(y%2) )  //x,y both even
10               return 2*gcd(x >> 1, y >> 1);    
11           else      // x is even, y is odd
12               return gcd(x >> 1, y );  
13         }

14         else 
15         {
16           if( !(y%2) )  // x is  odd,  y is even
17               return gcd(x, y >> 1);
18           else       // x, y both odd
19               return gcd(y,x-y); 
20         }

21    }

22}

23

posted on 2011-05-19 16:18 熊猫呵呵 阅读(21068) 评论(0)  编辑 收藏 引用 所属分类: 算法


只有注册用户登录后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
  • 大整数算法之gcd(最大公约数)
  • 大整数算法之求阶乘
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


 
Powered by:
C++博客
Copyright © 熊猫呵呵