递归法求最大公约数和最小公倍数的实现代码
发布时间:2023-10-07 02:11:34
数学原理:
设有两个数num1和num2,假设num1比较大。令余数r = num1 % num2。
当r == 0时,即num1可以被num2整除,显然num2就是这两个数的最大公约数。
当r != 0时,令num1 = num2(除数变被除数),num2 = r(余数变除数),再做 r = num1 % num2。递归,直到r == 0。
以上数学原理可以用具体的两个数做一下分析,这样容易理解。
代码实现(求最大公约数):
#include <iostream>
using namespace std;
int gcd(int a, int b);//声明最大公约数函数
int main()
{
int num1 = 1;
int num2 = 1;
cin >> num1 >> num2;
while(num1 == 0 || num2 == 0)//判断是否有0值输入,若有则重新输入
{
cout << "input error !" << endl;
cin >> num1 >> num2;
}
cout << "The gcd of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl;//调用最大公约数函数
return 0;
}
int gcd(int a, int b)//函数定义
{
int max = a > b ? a : b;
int min = a < b ? a : b;
a = max;
b = min;
int r = a % b;
if(0 == r)//若a能被b整除,则b就是最大公约数。
return b;
else
return gcd(b, r);//递归
}
最小公倍数的求法建立在求最大公约数的方法之上。因为最小公倍数等于两个数的积除以最大公约数。
代码实现(求最小公倍数):
#include <iostream>
using namespace std;
int gcd(int a, int b);//声明最大公约数函数
int main()
{
int num1 = 1;
int num2 = 1;
int lcm = 1;
cin >> num1 >> num2;
while(num1 == 0 || num2 == 0)//判断是否有0值输入,若有则重新输入
{
cout << "input error !" << endl;
cin >> num1 >> num2;
}
lcm = num1 / gcd(num1, num2) * num2;//先除后乘可以在一定程度上防止大数
cout << "The lcm of " << num1 << " and " << num2 << " is: " << lcm << endl;
return 0;
}
int gcd(int a, int b)//函数定义
{
int max = a > b ? a : b;
int min = a < b ? a : b;
a = max;
b = min;
int r = a % b;
if(0 == r)//若a能被b整除,则b就是最大公约数。
return b;
else
return gcd(b, r);//递归
}
以上是仅仅限与求两个书的最大公约数和最小公倍数,当数字有很多时,该法是否依然适用,还有待考证。
猜你喜欢
- 一般查询手机归属地内容应该很好用json格式保存,在网上找到了淘宝的归属地API,并下了处理json相关的jar包,做了这个手机归属地查询功
- 系统原来用的是BOSCH_BMA222的gsensor, 现在要求换成使用MMA7660,我们来看一下怎样增加驱动和调试过程。 1. 修改M
- 前言假如有人问你这么几个问题,看能不能答上来Mybatis Mapper 接口没有实现类,怎么实现的 * JDK * 为什么不能对类进
- Activity设置全屏和无标题栏,要用到andorid.view.Window和Android.view.WindowManager。 W
- 这篇文章主要介绍了Spring boot整合log4j2过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值
- 本文讲述了Java获取彩 * 像中的主色彩的实例代码。分享给大家供大家参考,具体如下:一:基本思路对于一张RGB色彩空间的彩 * 像,很多时间我
- Web服务器是运行及发布Web应用的容器,只有将开发的Web项目放置到该容器中,才能使网络中的所有用户通过浏览器进行访问。开发Java We
- 直接调用Math里面的random即可,简单方便int i = (int)(Math.random()*100+1);
- 文章开始之前,先看一下效果图,看是不是您正所需要的:一、构建计算器的界面要构建出一个好看点的计算器界面,还是需要颇费些小心思的,我做这个的时
- 一、引入先给出一个Num类的定义internal class Num{ public static int odd = 5000
- 最近公司项目需要在WebView上调用手机系统相册来上传图片,开发过程中发现在很多机器上无法正常唤起系统相册来选择图片。解决问题之前我们先来
- 对于ApplicationListener使用Spring的应该也熟悉,因为这就是我们平时学习的观察者模式的实际代表。Spring基于Jav
- 开始逐渐领略到ItemDecoration的美~今天让我 使用 ItemDecoration 来完成 可推动的悬浮导航栏的效果,最终实现的效
- Java是一种强类型, 许多流行的编程语言都已经支持局部变量类型推断,如js,Python,C++等JDK10 可以使用var作为局部变量类
- 本文实例为大家分享了C语言实现两个矩阵相乘的具体代码,供大家参考,具体内容如下程序功能:实现两个矩阵相乘的C语言程序,并将其输出代码如下:#
- 一、背景有时我们在做开发的时候需要记录每个任务执行时间,或者记录一段代码执行时间,最简单的方法就是打印当前时间与执行完时间的差值,一般我们检
- 前言当你编写一个应用时,你通常都会希望用户能够定制化他们和应用交互的方式,以及应用与系统进行交互的方式。这种方式通常被称为 &ldq
- 前言最近碰到了Mybatis一对多查询的场景,在这里总结对比下常见的两种实现方式。本文以常见的订单表和订单详情表来举例说明;数据库表准备订单
- 详解Android使用@hide的API的方法今天早上想修改MediaPlaybackService.Java(/packages/apps
- 第一种方法这种方法需要配置 hibernate.cfg.xml 的属性 hibernate.hbm2ddl.auto,该属性值的具体说明如下