试编写程序,使用穷举法计算两个给定正整数的最大公约数。
时间: 2024-05-08 13:17:42 浏览: 20
以下是Python代码示例:
```python
def gcd(a, b):
"""
计算a和b的最大公约数
"""
if a == 0 or b == 0:
return 0
elif a == b:
return a
elif a > b:
for i in range(b, 0, -1):
if a % i == 0 and b % i == 0:
return i
else:
for i in range(a, 0, -1):
if a % i == 0 and b % i == 0:
return i
# 测试
print(gcd(12, 18)) # 输出6
print(gcd(15, 25)) # 输出5
```
其中,我们使用了两层循环,分别从小到大枚举a和b中的所有可能的公约数,直到找到最大的公约数为止。由于最大公约数一定小于等于a和b中较小的那个数,因此我们可以从小到大枚举这个较小的数。在每次循环中,我们判断这个数是否同时是a和b的公约数,如果是,就返回它。如果循环结束还没有找到公约数,那么a和b没有公约数,最大公约数就是0。
相关问题
试编写程序,使用穷举法计算两个给定正整数的最大公约数
以下是使用 Python 语言编写的程序,使用穷举法计算两个给定正整数的最大公约数:
```python
def gcd(a, b):
"""
计算a和b的最大公约数
"""
if a < b:
a, b = b, a # 交换a和b,使得a始终大于等于b
for i in range(b, 0, -1):
if a % i == 0 and b % i == 0:
return i
return 1 # 如果没有找到公约数,返回1
# 测试程序
a = 24
b = 36
print(gcd(a, b)) # 输出:12
```
程序中定义了一个名为 `gcd` 的函数,该函数接受两个正整数 `a` 和 `b` 作为输入参数,并返回它们的最大公约数。程序中使用 `if` 语句判断 `a` 和 `b` 的大小关系,并在必要时交换它们的值。然后,程序使用一个 `for` 循环从 `b` 开始向下枚举每个正整数,如果这个正整数同时是 `a` 和 `b` 的公约数,就返回这个正整数。如果循环结束后仍然没有找到公约数,就返回 1。最后,程序对一个示例数据进行了测试,输出了正确的结果。
使用穷举法计算两个给定正整数的最大公约数
1. 找到两个正整数a和b,且a>b。
2. 从1到b枚举所有可能的公约数,将它们存储在一个列表中。
3. 遍历列表,找到最大的公约数。
4. 返回最大公约数。
Python代码示例:
```python
def gcd(a, b):
"""
计算a和b的最大公约数
"""
common_divisors = [] # 存储公约数的列表
for i in range(1, b+1):
if a % i == 0 and b % i == 0:
common_divisors.append(i)
return max(common_divisors)
# 示例
print(gcd(12, 18)) # 输出:6
print(gcd(35, 49)) # 输出:7
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)