前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】

【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】

作者头像
Rossy Yan
发布2025-01-13 08:17:59
发布2025-01-13 08:17:59
1130
举报

任务描述

本关任务:编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。


相关知识

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

  1. 循环控制 / 跳转语句的使用
  2. 如何求最大公约数
  3. 如何求最小公倍数
一、循环控制 / 跳转语句的使用
1. 循环控制语句(for 循环)

基本原理for循环是一种常用的循环结构,它允许您指定一个初始化表达式、一个循环条件和一个更新表达式。语法格式为for(初始化表达式; 循环条件; 更新表达式)。初始化表达式在循环开始时执行一次,用于初始化循环变量。循环条件在每次循环迭代开始时进行检查,如果为真,则执行循环体中的代码。更新表达式在每次循环体执行完后执行,用于更新循环变量。

示例代码

代码语言:javascript
复制
#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(循环条件)。循环条件是一个表达式,它返回一个布尔值(真或假)。在循环体中,通常需要包含一些能够改变循环条件的语句,否则可能会导致无限循环。

示例代码

代码语言:javascript
复制
#include <stdio.h>
int main() {
    int i = 1;
    while (i <= 10) {
        printf("%d ", i);
        i++;
    }
    printf("\n");
    return 0;
}
3. 跳转语句(break 语句)

基本原理break语句用于立即跳出当前循环(forwhiledo - while)或switch语句。当程序执行到break语句时,循环或switch语句会立即终止,程序控制流将跳转到循环或switch语句后的下一条语句。

示例代码(在循环中使用 break)

代码语言:javascript
复制
#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循环)或循环条件检查(对于whiledo - while循环)。

示例代码(在循环中使用 continue)

代码语言:javascript
复制
#include <stdio.h>
int main() {
    for (int i = 1; i <= 10; i++) {
        if (i == 5) {
            continue;
        }
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}

二、求最大公约数
1. 概念回顾

最大公约数(Greatest Common Divisor,简称 GCD),指两个或多个整数共有约数中最大的一个。例如,12 和 18 的最大公约数是 6。

2. 常用算法及代码实现
(1)辗转相除法(欧几里得算法)

算法原理:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的新余数(第二余数)去除第一余数,如此反复,直到最后余数是 0 为止。此时的除数就是最大公约数。

代码示例

代码语言:javascript
复制
#include <stdio.h>

// 辗转相除法求最大公约数的函数
int gcd(int a, int b) {
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1 = 24, num2 = 36;
    int result = gcd(num1, num2);
    printf("最大公约数为:%d\n", result);
    return 0;
}

在上述代码中:

  1. 定义了一个名为 gcd 的函数,它接受两个整数参数 ab,用于求这两个数的最大公约数。
  2. gcd 函数内部,通过 while 循环,只要 b 不为 0,就进行以下操作:
  • 先将当前的 b 值暂存到 temp 变量中。
  • 然后更新 b 的值为 a 除以 b 的余数(即 a % b)。
  • 再将之前暂存的 temp(也就是原来的 b)赋值给 a,相当于用除数和余数不断进行替换操作,直到余数为 0,此时的 a 就是最大公约数。
  • main 函数中,定义了两个示例数字 2436,调用 gcd 函数求出它们的最大公约数,并将结果输出显示。
(2)更相减损术(可用于优化辗转相除法等情况)

算法原理:可先判断两数是否都是偶数,如果是,则先同时除以 2,记录下约去的 2 的个数,然后用较大数减去较小数,接着把所得的差与较小数比较,并以大数减小数,继续这个操作,直到两数相等为止,最后将之前记录的约去的 2 的个数乘上此时相等的这个数,就是最大公约数。

代码示例(结合辗转相除法优化)

代码语言:javascript
复制
#include <stdio.h>

// 用更相减损术结合辗转相除法求最大公约数的函数
int gcd_optimized(int a, int b) {
    int factor = 1;  // 记录约去2的个数
    while (a % 2 == 0 && b % 2 == 0) {  // 判断两数是否都是偶数
        a /= 2;
        b /= 2;
        factor *= 2;
    }
    while (a!= b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a * factor;
}

int main() {
    int num1 = 24, num2 = 36;
    int result = gcd_optimized(num1, num2);
    printf("最大公约数为:%d\n", result);
    return 0;
}

在这个代码中:

  • gcd_optimized 函数首先通过一个 while 循环判断 ab 是否都是偶数,如果是就不断约去 2,并记录约去 2 的个数(通过 factor 变量)。
  • 然后再通过另一个 while 循环按照更相减损术的思路,用大数减小数,直到两数相等。
  • 最后返回的是约去 2 的个数乘以相等时的这个数,得到最大公约数。

三、求最小公倍数
1. 概念回顾

最小公倍数(Least Common Multiple,简称 LCM),是两个或多个整数公有的倍数中最小的一个。例如,4 和 6 的最小公倍数是 12。

2. 基于最大公约数求最小公倍数的方法及代码实现

两个数的最小公倍数等于这两个数的乘积除以它们的最大公约数。即 LCM(a, b) = a * b / GCD(a, b)

代码语言:javascript
复制
#include <stdio.h>

// 辗转相除法求最大公约数的函数(前面已讲,此处复用)
int gcd(int a, int b) {
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 求最小公倍数的函数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int main() {
    int num1 = 12, num2 = 18;
    int result = lcm(num1, num2);
    printf("最小公倍数为:%d\n", result);
    return 0;
}

在上述代码中:

  • 首先定义了 gcd 函数用于求最大公约数(采用辗转相除法),这部分代码和前面介绍的一样。
  • 然后定义了 lcm 函数用于求最小公倍数,它内部直接按照公式 a * b / gcd(a, b) 进行计算,也就是先获取两数的乘积,再除以它们的最大公约数。
  • main 函数中,定义了示例数字 1218,调用 lcm 函数求出它们的最小公倍数,并输出显示结果。

编程要求

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


测试说明

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

测试输入:

代码语言:javascript
复制
32
72

预期输出:

代码语言:javascript
复制
最大公约数是:8
最小公倍数是:288

测试输入:

代码语言:javascript
复制
56
98

预期输出:

代码语言:javascript
复制
最大公约数是:14
最小公倍数是:392

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


通关代码

代码语言:javascript
复制
#include <stdio.h>
int maxGYS(int a, int b)//求最大公约数子函数
{ 
int r;
r=a%b;
//请在此添加代码
/*********Begin*********/
while(r !=0)
{
    a=b;
    b=r;
    r=a%b;
    }
    return b;
}
/********* End *********/


int minGBS(int a, int b)//求最小公倍数子函数
{ int i;
//请在此添加代码
/*********Begin*********/
return (a*b) / maxGYS(a,b);
/********* End *********/
}


int main()
{
    int a,b,t;
    printf("请输入两个整数:\n");
    scanf("%d%d",&a,&b);
    if(a<b)
   //请在此添加代码
   /*********Begin*********/
    {
        t=a;
        a=b;
        b=t;
        printf("最大公约数是:%d\n",maxGYS(a,b));
        printf("最小公倍数是:%d",minGBS(a,b));
    }
    return 0;

   /********* End *********/
}

测试结果

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 任务描述
  • 相关知识
    • 一、循环控制 / 跳转语句的使用
      • 1. 循环控制语句(for 循环)
      • 2. 循环控制语句(while 循环)
      • 3. 跳转语句(break 语句)
      • 4. 跳转语句(continue 语句)
    • 二、求最大公约数
      • 1. 概念回顾
      • 2. 常用算法及代码实现
    • 三、求最小公倍数
      • 1. 概念回顾
      • 2. 基于最大公约数求最小公倍数的方法及代码实现
  • 编程要求
  • 测试说明
  • 通关代码
  • 测试结果
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档