C++求最大公约数四种方法解析

2024-12-20 08:32:43

C++求最大公约数的四种方法思路，供大家参考，具体内容如下

将最近学的求最大公约数的四种方法总结如下：

第一种：穷举法之一

解释：拿其中一个数出来，用一个临时变量（tem）保存，每次都把那两个数除以这个临时变量。如果能除断，直接返回tem；如果不能除断，tem- -，直到都能除断，再返回tem。tem就是它们的最大公约数。

#include <iostream>
using namespace std;
int CommFactor1(int m, int n); //函数的声明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "这两个数的最大公约数为：" << CommFactor1(a,b)<< endl;
 return 0;
}
int CommFactor1(int m,int n)
{
 int tem;
 for (tem = m;; tem--)
 {
 if (m % tem == 0 && n % tem == 0)
 {
  break;
 }
 }
 return tem;
}

第二种：穷举法之二

解释：求出两数的所有公因子，再把公因子累乘得到最大公约数。

#include <iostream>
using namespace std;
int CommFactor2(int m, int n); //函数的声明
int main()
{
  int a, b;
  cin >> a >> b;
  cout << "这两个数的最大公约数为：" << CommFactor2(a,b)<< endl;
  return 0;
}
int CommFactor2(int m,int n)
{
  int i;
  int factor = 1;
  for (i=2;i<=m&&i<<n;i++)
  {
    while(m % i == 0 && n % i == 0)  //这里不能用if语句，因为可能会有重复的公因子
    {
      factor = factor * i;
      m = m / i;
      n = n / i;
    }
  }
  return factor;
}

第三种：辗转相除法

解释：将两个数辗转相除直到余数为0。（具体思想请问度娘）

#include <iostream>
using namespace std;
int CommFactor3(int m, int n); //函数的声明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "这两个数的最大公约数为：" << CommFactor2(a,b)<< endl;
 return 0;
}
int CommFactor3(int m,int n)
{
 int z = n;
 while (m % n != 0)
 {
 z = m % n;
 m = n;
 n = z;
 }
 return z;
}

第四种：辗转相减法

解释：将两个数辗转相减直到两数相等。（具体思想请问度娘）

#include <iostream>
using namespace std;
int CommFactor4(int m, int n); //函数的声明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "这两个数的最大公约数为：" << CommFactor4(a,b)<< endl;
 return 0;
}
int CommFactor4(int m,int n)
{

 while (m != n)
 {
 if (m > n)
 {
 m = m - n;
 }
 else
 {
 n = n - m;
 }
 }
 return m;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C++ 实现求最大公约数和最小公倍数

C++ 实现求最大公约数和最小公倍数最大公约数辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a, int b) { while (a != b) { if (a>b) a = a - b; else b = b - a; } return a; } 感谢阅读,希望能帮助到大家,谢
C++求四个正整数最大公约数的方法

本文实例讲述了C++求四个正整数最大公约数的方法.分享给大家供大家参考,具体如下: /* * 作者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版本号:v1.0 * * 输入描述: 输入四个正整数,输出其最大公约数. * 问题描述: * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std; int f(int,int); int g(int,int,int,int); int main()
C++ 实现多数的最大公约数的实例

C++ 实现多数的最大公约数的实例题目:求最大公约数输入一组正整数(数量小于20),输出其最大公约数. 输入:121 33 44 11 1111 输出:11 基本思路: 从第一个数开始,和第二个数比较找它两的最大公约数,然后找出的最大公约数和第三个数比较,依次类推... #include <stdio.h> int gcd(int a,int b) { return a%b?gcd(b,a%b):b; } int main() { int N,a[20],k,i; while(~scanf
C++求最大公约数四种方法解析

C++求最大公约数的四种方法思路,供大家参考,具体内容如下将最近学的求最大公约数的四种方法总结如下: 第一种:穷举法之一解释:拿其中一个数出来,用一个临时变量(tem)保存,每次都把那两个数除以这个临时变量.如果能除断,直接返回tem:如果不能除断,tem- -,直到都能除断,再返回tem.tem就是它们的最大公约数. #include <iostream> using namespace std; int CommFactor1(int m, int n); //函数的声明 int ma
IOS中Json解析实例方法详解(四种方法)

作为一种轻量级的数据交换格式,json正在逐步取代xml,成为网络数据的通用格式. 有的json代码格式比较混乱,可以使用此"http://www.bejson.com/"网站来进行JSON格式化校验(点击打开链接).此网站不仅可以检测Json代码中的错误,而且可以以视图形式显示json中的数据内容,很是方便. 从IOS5开始,APPLE提供了对json的原生支持(NSJSONSerialization),但是为了兼容以前的iOS版本,可以使用第三方库来解析Json. 本文将介绍Tou
php 解析xml 的四种方法详细介绍

php 解析xml 的四种方法 XML处理是开发过程中经常遇到的,PHP对其也有很丰富的支持,本文只是对其中某几种解析技术做简要说明,包括:Xml parser, SimpleXML, XMLReader, DOMDocument. 1. XML Expat Parser: XML Parser使用Expat XML解析器.Expat是一种基于事件的解析器,它把XML文档视为一系列事件.当某个事件发生时,它调用一个指定的函数处理它.Expat是无验证的解析器,忽略任何链接到文档的DTD.但是,如
Oracle连接远程数据库的四种方法

Oracle数据库的远程连接可以通过多种方式来实现,本文我们主要介绍四种远程连接的方法和注意事项,并通过示例来说明,接下来我们就开始介绍第一种方法: 若oracle服务器装在本机上,那就不多说了,连接只是用户名和密码的问题了. 不过要注意环境变量%ORACLE_HOME%/network/admin/是否设置. 第二种方法: 本机未安装oracle服务器,也未安装oracle客户端.但是安装了pl sql development.toad sql development.sql navigat
java读取XML文件的四种方法总结(必看篇)

JAVA操作XML文档主要有四种方式,分别是DOM.SAX.JDOM和DOM4J,DOM和SAX是官方提供的,而JDOM和DOM4J则是引用第三方库的,其中用的最多的是DOM4J方式.运行效率和内存使用方面最优的是SAX,但是由于SAX是基于事件的方式,所以SAX无法在编写XML的过程中对已编写内容进行修改,但对于不用进行频繁修改的需求,还是应该选择使用SAX. 下面基于这四种方式来读取XML文件. 第一,以DOM的方式实现. package xmls; import org.w3c.dom.D
汇编语言有关在屏幕区显示字符的四种方法(推荐)

李忠老师的<x86汇编语言:从实模式到保护模式>中第五章到第七章的部分,每一章在讲述知识点的同时,分别使用了三种不同的显示字符的方法,加上调用BIOS的10h中断的方法,这里做出一次简单梳理: 一:第五章,最基础的直接用mov 的方法代码如下: ;代码清单5-1 ;文件名:c05_mbr.asm ;文件说明:硬盘主引导扇区代码 ;创建日期:2011-3-31 21:15 mov ax,0xb800 ;指向文本模式的显示缓冲区 mov es,ax ;以下显示字符串"Label of
Java中求最大值的4种方法实例代码

前言本文主要给大家分享了关于java求最大值的4中方法,文中给出了完整的示例代码,下面话不多少了,来一起看看吧示例代码: /** *@author Prannt *求最大值(或最小值) *本例以int数据类型为例,可指定其他数据类型 */ //方法一:直接法,求最小值类似 public class Deno05ArrayMax { public static void main(String[] args) { //数据类型可指定 int [] array = {5,15,20,30,100
VUE的tab页面切换的四种方法

1.静态实现方法: 效果图: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="widt
java调用WebService服务的四种方法总结

目录一.前言二.简介三.具体解析第一种方式,首先得下载axis2的jar包,Axis2提供了一个wsdl2java.bat命令可以根据WSDL文件自动产生调用WebService的代码. 第二种RPC 方式,强烈推荐. 第三种:利用HttpURLConnection拼接和解析报文进行调用. 第四种,利用httpclient 总结一.前言本来不想写这个的,因为网上类似的是在是太多了.但是想想自己前面段时间用过,而且以后可能再也没机会用了.所以还是记录一下吧.我这儿是以C语言生成的W
AJAX跨域请求数据的四种方法(实例讲解)

由于浏览器的同源策略 ajax请求不可以接收到请求响应回来的数据请求数据需要调用浏览器的内置构造函数 XMLHttpRequest() 进行实例对象 var xhr = new XMLHttpRequest(); 注意点在IE8之前支持的 ActiveXobject("Microsoft.XMLHTTP"); 记住要进行兼容处理哦在这里我就不写了通过该对象进行获取获取数据的四种状态 xhr.readyState 该属性保存着请求数据的几种状态 1.xhr.open(请

C++求最大公约数四种方法解析

相关推荐

随机推荐