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

简介: 采用欧几里得算法(EuclideanAlgorithm)求解两个正整数的最大公约数。的最大公约数,然后检查最大公约数是否大于1。如果是,就返回1,表示。根据提示,在右侧编辑器Begin--End之间的区域内补充必要的代码。作为新的参数传递进去。这个递归过程会不断进行,直到。有除1以外的公约数;变为0,此时就找到了最大公约数。开始你的任务吧,祝你成功!是否为0,如果是,那么。就是最大公约数,直接返回。

目录😋

任务描述

相关知识

一、欧几里得算法(Euclidean Algorithm)

1. 基本原理

2. 示例代码

3. 应用场景

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

1. 基本原理

2. 示例代码(通过最大公约数判定)

3. 示例代码(通过遍历判定)

4. 应用场景

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

1. 循环控制语句(for 循环)

2. 循环控制语句(while 循环)

3. 跳转语句(break 语句)

4. 跳转语句(continue 语句)

编程要求

测试说明

通关代码

测试结果


任务描述

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


相关知识

为了完成本关任务,你需要掌握:

  1. 欧几里得算法(Euclidean Algorithm);
  2. 公约数的判定;
  3. 循环控制/跳转语句的使用。

一、欧几里得算法(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);
}
image.gif

在这个代码中,gcd函数接受两个整数ab。首先检查b是否为 0,如果是,那么a就是最大公约数,直接返回a。否则,递归调用gcd函数,将ba % b作为新的参数传递进去。这个递归过程会不断进行,直到b变为 0,此时就找到了最大公约数。

3. 应用场景

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

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

1. 基本原理

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

2. 示例代码(通过最大公约数判定)

int has_common_divisor(int a, int b) {
    int gcd_value = gcd(a, b);
    return gcd_value > 1;
}
image.gif

这个函数has_common_divisor调用gcd函数来计算ab的最大公约数,然后检查最大公约数是否大于 1。如果是,就返回 1,表示ab有除 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;
}
image.gif

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;
}
  • image.gif

2. 循环控制语句(while 循环)

  • 基本原理while循环在循环开始时检查循环条件。只要条件为真,就会执行循环体中的代码。语法格式为while(循环条件)。循环条件是一个表达式,它返回一个布尔值(真或假)。在循环体中,通常需要包含一些能够改变循环条件的语句,否则可能会导致无限循环。
  • 示例代码
#include <stdio.h>
int main() {
    int i = 1;
    while (i <= 10) {
        printf("%d ", i);
        i++;
    }
    printf("\n");
    return 0;
}
  • image.gif

3. 跳转语句(break 语句)

  • 基本原理break语句用于立即跳出当前循环(forwhiledo - 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;
}
  • image.gif

4. 跳转语句(continue 语句)

  • 基本原理continue语句用于跳过当前循环迭代的剩余部分,直接开始下一次循环迭代。当程序执行到continue语句时,循环体中continue语句之后的代码将不会被执行,而是直接跳转到循环的更新表达式(对于for循环)或循环条件检查(对于whiledo - 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;
}
  • image.gif

编程要求

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


测试说明

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

测试输入:

64,24
image.gif

预期输出:

求出的最大公约数是8
image.gif

开始你的任务吧,祝你成功!


通关代码

/*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);
}

image.gif


测试结果

image.gif


目录
相关文章
|
9月前
|
存储 编译器 C语言
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
201 3
|
9月前
|
存储 算法 安全
【C语言程序设计——函数】分数数列求和1(头歌实践教学平台习题)【合集】
if 语句是最基础的形式,当条件为真时执行其内部的语句块;switch 语句则适用于针对一个表达式的多个固定值进行判断,根据表达式的值与各个 case 后的常量值匹配情况,执行相应 case 分支下的语句,直到遇到 break 语句跳出 switch 结构,若没有匹配值则执行 default 分支(可选)。例如,在判断一个数是否大于 10 的场景中,条件表达式为 “num> 10”,这里的 “num” 是程序中的变量,通过比较其值与 10 的大小关系来确定条件的真假。常量的值必须是唯一的,且在同一个。
175 2
|
算法 C语言
《C语言及程序设计》实践参考——输出小星星(之3)
返回:贺老师课程教学链接  项目要求 要输出的星号图是:   将一个图,看作为6行,完成了第一级的分解,提到的算法框架为: i=1; While(i&lt;=6) //需要输出6行 { 输出第i行; 换行; ++i; } 对于“输出第i行”的任务,可以进行细化:先输出若干空格(多少个空格?第1行0个,第2行1个,第3行2……第6行5个); 再输出若
1097 0
|
C语言
《C语言及程序设计》实践参考——简单循环的流程图
返回:贺老师课程教学链接  项目要求 简单循环的流程图(提示:m是一个变量,在程序中输入)(1)求1到m的倒数和,即  [参考解答] (2)求1到m的平方和[参考解答] (3)求1到m间所有奇数的和[参考解答] (4)求值:  [参考解答] (5)求m!,即  [参考解答]
2026 0
|
C语言
《C语言及程序设计》实践参考——双分支结构流程图-大值
返回:贺老师课程教学链接  项目要求 【双分支结构流程图-大值】问题:画流程图,输入两个整数a和b,输出其中的大值。提示:采用双分支结构,输入a、b后,将大值赋值给另外一个变量,最后输出结果。 参考解答:
1712 0
|
C语言 知识图谱
《C语言及程序设计》实践参考——流程图综合-体重监测器
返回:贺老师课程教学链接  项目要求 【流程图综合-体重监测器】(1)成年男性的标准体重,标准体重(kg)= 身高(cm)-100,请画流程图,输入身高,输出标准体重。 (2)超标准体重20%为超重,请画流程图,先计算出标准体重,当超重时,请给出提示 (3)体重监测器需要在不超重时也给提示,请画流程图。 (4)若体重低于标准体重20%为超低,将这种情况也做出处理。 (5)除了为男生服务,还要
1509 0
|
C语言
《C语言及程序设计》实践参考——被3或者5整除的数
返回:贺老师课程教学链接  项目要求 【项目:被3或者5整除的数】编程序,输入一个数,判断它能否被3或者被5整除。如至少能被这两个数中的一个整除,则将此数打印出来,否则不打印。[参考解答] 解法1: #include &lt;stdio.h&gt; int main ( ) { int x; scanf("%d", &amp;x); if(x%3==0||x%5==
1364 0
|
C语言
《C语言及程序设计》实践参考——乱玩数字
返回:贺老师课程教学链接  项目要求 【项目2:乱玩数字】编程输入整数a和b,若两数之和大于100,则输出两数和百位以上的数字,否则输出两数之和。[参考解答] #include &lt;stdio.h&gt; int main ( ) { int a, b, c; scanf("%d %d", &amp;a, &amp;b); c = a + b; if (
1003 0
|
C语言
《C语言及程序设计》实践参考——我的加班费
返回:贺老师课程教学链接  项目要求 【项目:我的加班费】小贺刚上班,按工作时间小时制领取周工资,工资标准是,每小时rate元RMB。每周工作时间40小时,如果要加班,超出部分按正常工资的1.5倍计(老板还算不错喔!)。这周小贺上班的时间为hour小时,请编程序,输入rate和hour,输出小贺本周的薪水。[参考解答] #include &lt;stdio.h&gt; int main (
1098 0
|
C语言
《C语言及程序设计》实践参考——个人所得税计算器if语句版
返回:贺老师课程教学链接  项目要求 【项目:个人所得税计算器if语句版】编写选择结构程序,输入个人月收入总额,计算出他本月应缴税款和税后收入(计算办法见附:关于个人所得税的有关背景知识)。(1)用if语句的嵌套完成;(2)可以在下面程序的基本框架基础上完成,如需其他变量自行增加 #include &lt;stdio.h&gt; int main ( ) { double dSalary
1994 0