Chinaunix首页 | 论坛 | 博客
  • 博客访问: 9109
  • 博文数量: 2
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 10
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-02 09:29
文章分类
文章存档

2013年(2)

我的朋友

分类: C/C++

2013-10-16 00:12:26

综述:

    今天看了计算机编程艺术,第一张是关于最大公约数的,基本的算法思想是求m,n的最大公约数,我们假设m = tn + x;我们证明m,n的最大公约数,就是n与x的最大公约数。因为m能被k整除,n能被k整除,所以m/k = (tn + k)/k = tn/k + x/k, x必须也能被k整除。算法如下:

点击(此处)折叠或打开

  1. unsigned int greatest_common_dividor(unsigned int m,unsigned int n)
  2. {
  3.     unsigned int r;
  4.     while(true)
  5.     {
  6.         r = m % n;
  7.         if(r == 0)
  8.             return n;
  9.         m = n;
  10.         n = r;
  11.     }
  12. }
       我们可以看到从第一次开始不管m 〉n或者n〉m,从第二次开始总是m〉n。但是有两次赋值。所以能不能去掉这两次赋值呢。所以算法的魅力就在这里,我们看能不能把r去掉,只留m,n呢,我们知道m,n肯定最后只需要一个,其中较大的会被删掉。
        我们假设m〉n,此时我们可以让m=m%n,赋值之后此时m为较小的了,在下此迭代的时候,就会出现死循环,因为我们只能让m〉n才能使其能够正确运行。
        所以我们接下来令n=n%m就可以保证,n始终是较小的。又不会浪费循环次数。所以算法是

点击(此处)折叠或打开

  1. unsigned int greatest_common_dividor(unsigned int m,unsigned int n)
  2. {
  3.     while(true)
  4.     {
  5.         m = m % n;
  6.         if(0 == m)
  7.             return n;
  8.         n = n % m
  9.         if(0 == n)
  10.             return m;
  11.     }
  12. }
不禁感叹,没有想不到,只有做不到。算法真的太神秘了。


      


阅读(1116) | 评论(0) | 转发(0) |
0

上一篇:libevent event 事件的机制

下一篇:没有了

给主人留下些什么吧!~~