当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

辗转相处求最大公约数

发表于: 2015-06-09   作者:沐刃青蛟   来源:转载   浏览:
摘要: 无言面对”江东父老“了,接触编程一年了,今天发现还不会辗转相除法求最大公约数。惭愧惭愧!   为此,总结一下以方便日后忘了好查找。   1.输入要比较的两个数a,b   忽略:2.比较大小(因为后面要的是大的数对小的数做%操作)   3.辗转相除(用循环不停的取余,如a%b,直至b=0)   4.最后的a为两数的最大公约数 &

无言面对”江东父老“了,接触编程一年了,今天发现还不会辗转相除法求最大公约数。惭愧惭愧!

 

为此,总结一下以方便日后忘了好查找。

 

1.输入要比较的两个数a,b

 

忽略:2.比较大小(因为后面要的是大的数对小的数做%操作)

 

3.辗转相除(用循环不停的取余,如a%b,直至b=0)

 

4.最后的a为两数的最大公约数

 

于是代码如下:

//求最大公约数的函数
int maxGY(int a,int b)
{
	//判断大小(可以不判断)
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}
	while (b!=0)
	{
		//大的对小的取余
		int m = a%b;
		a = b;
		b = m;
	}
	//返回最大公约数
	return a;
}

 

有了最大公约数,最小公倍数也就easy了,

最小公倍数=数1*数2/最大公约数。

代码如下:

 

//求最小公倍数的函数
int minGB(int a,int b)
{
	//先求最大公约数
	int m = maxGY(a, b);
	int n = a*b / m;
	return n;
}

 

 

 

辗转相处求最大公约数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
/* * Copyright (c) 2013, 烟台大学计算机学院 * All rights reserved. * 作 者: 霍雨佳 * 完成日
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者:解晓东 * 完成日期
题目189 题目信息 运行结果 本题排行 讨论区 兔子的烦恼(一) 时间限制: 1000 ms | 内存限制: 655
典型例题: 一.辗转相除法 例1 。求两个正数8251和6105的最大公因数。 (分析:辗转相除→余数为零
/* *Copyright (c) 2013 ,烟台大学计算机学院 *All rights reserved. *作者:王至超 *完成日期:201
/* * 程序的版权和版本声明部分 * Copyright (c)2012, 烟台大学计算机学院学生 * All rightsreserve
* Copyright (c) 2012, 烟台大学计算机学院 03. * All rights reserved. 04. * 作 者:赵晓晨 05. *
/* * 程序的版权和版本声明部分 * Copyright (c)2012, 烟台大学计算机学院 * All rightsreserved. *
*/ * Copyright (c) 2011, 烟台大学计算机学院 * All rights reserved. * 作 者: 孙培培 * 完成日
/* * 程序的版权和版本声明部分 * Copyright (c)2012, 烟台大学计算机学院 * All rightsreserved. *
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号