伪代码分别用辗转相除法和定义法求a和b的最大公约数,并比较两种算法运行时间的差异
时间: 2024-05-25 21:18:33 浏览: 17
1. 辗转相除法
function gcd(a, b):
while b != 0:
r = a % b
a = b
b = r
return a
时间复杂度:O(log(min(a, b)))
2. 定义法
function gcd(a, b):
if a == b:
return a
elif a > b:
return gcd(a-b, b)
else:
return gcd(a, b-a)
时间复杂度:O(max(a, b))
从时间复杂度可以看出,辗转相除法的效率要高于定义法。因为辗转相除法每次操作都会将较大数除以较小数,而定义法每次操作都会减去一个较小数,所以当a和b相差较大时,定义法的递归深度会很大,效率会很低。
实际运行时间上,也可以通过比较两种算法的运行时间来验证这一点。
相关问题
伪代码写辗转相除法和定义法求a和b的最大公约数
1. 辗转相除法:
输入:a, b
输出:a和b的最大公约数
1. 如果b等于0,则返回a
2. 令r等于a对b的余数
3. 令a等于b,b等于r
4. 重复执行步骤2和3,直到b等于0
5. 返回a
2. 定义法:
输入:a, b
输出:a和b的最大公约数
1. 如果a等于b,则返回a
2. 如果a大于b,则令a等于a-b,返回步骤1
3. 如果b大于a,则令b等于b-a,返回步骤1
用流程图、ns图、伪代码分别描述解决如下实际问题的算法。求两个数m和n的最大公约数
流程图:
开始 -> 输入m和n -> 如果m小于n,则交换m和n -> 如果n等于,则输出m为最大公约数,结束 -> 否则,令r为m除以n的余数 -> 将m赋值为n,将n赋值为r -> 返回第三步
NS图:
伪代码:
function gcd(m, n)
if m < n then
swap(m, n)
end if
while n != do
r = m % n
m = n
n = r
end while
return m
end function
其中,swap函数用于交换两个变量的值。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)