CMNSOFT
首页|算法设计|在线应用
04.求最大公约数
作者:孙自超发布时间:2024-10-08 12:32:19

复习


求最大公约数,最重要就是求出多个整数的共同因数。回忆一下,如何求1个整数包含所有的因数,要用到那些运算符?

新知识


例1.求最大公约数

输入两个非0正整数,输出它们最大的公约数。请写程序实现。

(1)题目分析

求两个整数的最大公约数方法与求一个整数的因数方法相似,都是用试商的方法。不同地方是求最大公约数时,试商要同时去除两个整数。只有两个整数都能整除试商值。那这个数就是最大公约数。由于是求最大的公约数,所以试商时可以从较小那个整数开始。


(2)流程图

    flowchart LR
    
    A(开始程序) --> B[/输入两个整数a,b/]
    B --> C[c=min#40;a,b#41;]
    C --> D{a%c!=0 或
b%c!=0 } D -- Yes --> E[c=c-1] E --> D D -- No --> F[/输出c值/] F -->G(结束程序)

思考一下,c=min(a,b)作用是什么?


(3)源代码

#include<bits/stdc++.h> using namespace std; int main() { int a,b; cin>>a>>b; int c = min(a,b); while(a%c!=0 || b%c!=0){ c -= 1; } cout<<c; return 0; }

课后练习


编写程序,求三个非零正整数的最大公约数。


桂ICP备11003301号 桂公网安备45040302000027号
Copyright @ 2011-2025 by Sun zi chao
平台运行天数:80天
阅读次数:3835次
展开目录
+  01.基础知识

01.算法是什么?

02.编程语言介绍

03.编程基础

04.控制结构-1

05.控制结构-2

06.控制结构-3

07.函数的使用

+  02.数值运算

01.取整与取模

02.寻找因数

03.寻找完全数

04.求最大公约数

05.求最小公倍数

06.斐波那契数列

+  03.字符串运算
+  04.搜索算法
+  05.排序算法
+  06.分治算法
+  07.回溯算法
+  08.动态规划
+  09.贪心算法
+  10.遗传算法

同步视频