当前位置：首页 > article >正文

【C语言程序设计——循环程序设计】求解最大公约数（头歌实践教学平台习题）【合集】

article 2025/1/5 6:33:39

目录😋

任务描述

本关任务：采用欧几里得算法（Euclidean Algorithm）求解两个正整数的最大公约数。

相关知识

为了完成本关任务，你需要掌握：

欧几里得算法（Euclidean Algorithm）；
公约数的判定；
循环控制/跳转语句的使用。

一、欧几里得算法（Euclidean Algorithm）

1. 基本原理

欧几里得算法用于计算两个整数的最大公约数（GCD - Greatest Common Divisor）。其基本思想是基于这样一个定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，对于 a整数和 b（a>b），gcd(a,b)=gcb(b,a%b)。这个过程不断重复，直到余数为 0，此时的除数就是最大公约数。

2. 示例代码
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
在这个代码中，gcd函数接受两个整数a和b。首先检查b是否为 0，如果是，那么a就是最大公约数，直接返回a。否则，递归调用gcd函数，将b和a % b作为新的参数传递进去。这个递归过程会不断进行，直到b变为 0，此时就找到了最大公约数。

3. 应用场景

欧几里得算法在很多数学和计算机科学问题中有广泛应用。例如，在分数化简中，可以用它来求出分子分母的最大公约数，从而将分数化为最简形式。在密码学中的一些加密算法和哈希函数的实现中，也会用到最大公约数的计算来保证数据的安全性和准确性。

二、公约数的判定在 C 语言中的应用

1. 基本原理

判定两个数是否有公约数，通常可以通过计算它们的最大公约数来实现。如果最大公约数大于 1，那么这两个数就有除 1 以外的公约数。另外，也可以通过遍历一定范围内的数来检查是否为两个数的公约数。例如，要检查整数a和b是否有在 1 到min(a, b)范围内的公约数，可以使用一个循环从 2 开始遍历到min(a, b)，检查每个数是否能同时整除a和b。

2. 示例代码（通过最大公约数判定）
int has_common_divisor(int a, int b) {
    int gcd_value = gcd(a, b);
    return gcd_value > 1;
}
这个函数has_common_divisor调用gcd函数来计算a和b的最大公约数，然后检查最大公约数是否大于 1。如果是，就返回 1，表示a和b有除 1 以外的公约数；否则返回 0。

3. 示例代码（通过遍历判定）
int has_common_divisor(int a, int b) {
    int min_value = a < b? a : b;
    for (int i = 2; i <= min_value; i++) {
        if (a % i == 0 && b % i == 0) {
            return 1;
        }
    }
    return 0;
}
4. 应用场景

公约数的判定在数论相关的算法中非常重要。例如，在判断两个数是否互质（即最大公约数为 1）时就会用到。在一些优化算法中，如分数运算的优化、多项式的化简等，如果能判定两个数有公约数，就可以进行约分等操作来简化计算。

三、循环控制 / 跳转语句的使用

1. 循环控制语句（for 循环）
基本原理：for循环是一种常用的循环结构，它允许您指定一个初始化表达式、一个循环条件和一个更新表达式。语法格式为for(初始化表达式; 循环条件; 更新表达式)。初始化表达式在循环开始时执行一次，用于初始化循环变量。循环条件在每次循环迭代开始时进行检查，如果为真，则执行循环体中的代码。更新表达式在每次循环体执行完后执行，用于更新循环变量。
示例代码
#include <stdio.h>
int main() {
    // 打印1到10的数字
    for (int i = 1; i <= 10; i++) {
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}
2. 循环控制语句（while 循环）
基本原理：while循环在循环开始时检查循环条件。只要条件为真，就会执行循环体中的代码。语法格式为while(循环条件)。循环条件是一个表达式，它返回一个布尔值（真或假）。在循环体中，通常需要包含一些能够改变循环条件的语句，否则可能会导致无限循环。
示例代码
#include <stdio.h>
int main() {
    int i = 1;
    while (i <= 10) {
        printf("%d ", i);
        i++;
    }
    printf("\n");
    return 0;
}
3. 跳转语句（break 语句）
基本原理：break语句用于立即跳出当前循环（for、while、do - while）或switch语句。当程序执行到break语句时，循环或switch语句会立即终止，程序控制流将跳转到循环或switch语句后的下一条语句。
示例代码（在循环中使用 break）
#include <stdio.h>
int main() {
    for (int i = 1; i <= 10; i++) {
        if (i == 5) {
            break;
        }
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}
4. 跳转语句（continue 语句）
基本原理：continue语句用于跳过当前循环迭代的剩余部分，直接开始下一次循环迭代。当程序执行到continue语句时，循环体中continue语句之后的代码将不会被执行，而是直接跳转到循环的更新表达式（对于for循环）或循环条件检查（对于while和do - while循环）。
示例代码（在循环中使用 continue）
#include <stdio.h>
int main() {
    for (int i = 1; i <= 10; i++) {
        if (i == 5) {
            continue;
        }
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}

编程要求

根据提示，在右侧编辑器Begin--End之间的区域内补充必要的代码。

测试说明

平台会对你编写的代码进行测试：

测试输入：
64，24

预期输出：
求出的最大公约数是8

开始你的任务吧，祝你成功！

通关代码

 /*9. 求两个正整数的最大公约数。*/
#include "stdio.h"
main(){
	int m,n,r; 
	scanf("%d %d",&m,&n);
    /************************begin***********************/
    r = m % n;
while(r != 0){
    m = n;
    n = r;
    r = m % n;
}
    /************************end************************/
	printf("求出的最大公约数是%d",n);
}