C++编程 求最大公约数和最小公倍数
1.最大公约数 解题思想:
?1.辗转相除法(欧几里德算法),定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
2.辗转相减法(尼考曼彻斯法),其特色是做一系列减法,从而求得最大公约数。3.穷举法 从上往下减,保证最大!
代码实现:
#include
using namespace std;
//辗转相除法(欧几里德算法)
int measure1(int x, int y)
{
int z = y;
while(x%y!=0)
{//定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
z = x%y;
x = y;
y = z;
}
return z;
}//辗转相减法(尼考曼彻斯法)
int measure2(int a,int b)
{
while(a != b)
{//其特色是做一系列减法,从而求得最大公约数
if(a>b)
{
a = a - b;
}
else
{
b = b - a;
}
}
return a;
}//穷举法从上往下减,保证最大!
int measure3(int x,int y)
{
int temp = 0;
for(temp = x ;
;
temp-- )
{
if(x%temp == 0 && y%temp==0)
break;
}
return temp;
}void main(){
int x,y;
cout<<"请输入两个数字,并在中间用空格隔开:";
cin>>x;
cin>>y;
cout<<"辗转相除法得到的最大公约数为:"<
效果图展示:
文章图片
2.最小公倍数 解题思想:
?1.穷举法,从两者中最大的数开始,向上加,直到可以使对两数同时取余都为零。2.两个整数的最小公倍数等于两整数之积除以最大公约数。
代码实现:
#include
using namespace std;
void main(){
int n1, n2, max;
cout << "输入两个数: ";
cin >> n1 >> n2;
// 获取最大的数
max = (n1 > n2) ? n1 : n2;
do
{
if (max % n1 == 0 && max % n2 == 0)
{
cout << "LCM = " << max<
【C++编程 求最大公约数和最小公倍数】效果图展示:
文章图片
推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧(用class类实现链表)
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题
- 麦克算法|4指针与队列
- 遇见蓝桥遇见你|小唐开始刷蓝桥(一)2020年第十一届C/C++ B组第二场蓝桥杯省赛真题