posts - 1, comments - 1, trackbacks - 0

求两个数的最大公约数

   纵观历史，一个帝国辉煌的顶点，正是它衰落的开始；居安不思危，非王道也！

   这篇文章，主要是关于两个数的最大公约数的求法，分为递归和非递归两种方法求解。

/*************************************************************************
2

* Copyright (c) 2009
3

* All rights reserved.
4

*
5

* 文件名称：getmax.cpp
6

* 摘要：递归方法求解
7

*
8

* 当前版本：1.0
9

* 作者：fighter
10

* 完成日期：
11

*
12

***************************************************************************/
13

#include <iostream>
15

#include <stdint.h>
16

using namespace std;
18

uint64_t getmax( uint64_t m, uint64_t n)
20

{
21

uint64_t k = m % n;
22

if( 0 == k)
23

{
24

return n;
25

}
26

else
27

{
28

getmax( n , k);
29

}
30

}
31

int main( int argc, char ** argv)
33

{
34

uint64_t m = 66;
35

uint64_t n = 99;
36

uint64_t k = getmax( m, n);
38

cout << " zui da gong yue shu shi :" << k << endl;
40

return 0;
42

}

   递归：个人理解，递归最大的难点，首先，在于终结条件的确定；其次，在于递归调用函数的时候参数的选取，弄明白这两个问题，那么所有的问题就都不是问题了，呵呵，下面来个非递归的，不用递归，当然就用循环了！
   不多说了，直接上代码：

/*************************************************************************
3

* Copyright (c) 2009
4

* All rights reserved.
5

*
6

* 文件名称：getmax2.cpp
7

* 摘要：非递归方法求解
8

*
9

* 当前版本：1.0
10

* 作者：fighter
11

* 完成日期：
12

*
13

***************************************************************************/
14

#include <stdint.h>
16

#include <iostream>
17

using namespace std;
19

uint64_t getmax2( uint64_t m, uint64_t n)
21

{
22

uint64_t k = m % n;
23

while( 0 != k)
25

{
26

m = n;
27

n = k;
28

k = m % n;
29

}
30

return n;
32

}
33

int main( int argc, char ** argv)
35

{
36

uint64_t m = 66;
37

uint64_t n = 99;
38

uint64_t k = getmax2( m, n);
40

cout << " zui da gong yue shu shi :" << k << endl;
42

return 0;
44

}
45

非递归方法：注意while条件的选取，其他的就没有什么说的了！

posted on 2009-07-06 10:08 似水流年阅读(442) 评论(0) 编辑收藏引用所属分类: 练手的小例子

只有注册用户登录后才能发表评论。


相关文章: 单链表操作（包括创建、添加、删除、倒置等操作）找出数组的所有子集，要求子集的所有元素和为一定值，如{1,2,3,4,5,8}有子集{1,2,3,4}、{2,8}等。求两个数的最大公约数求1-100内的所有素数

网站导航: 博客园博客园最新博文博问管理

2026年6月

日

一

二

三

四

五

六

常用链接

留言簿

随笔分类

随笔档案

2009年7月 (1)

文章分类

文章档案

新闻分类

业界动态

相册

收藏夹

服务器设计