首页 C语言求最大公约数和最小公倍数算法总结

C语言求最大公约数和最小公倍数算法总结

举报
开通vip

C语言求最大公约数和最小公倍数算法总结C语言求最大公约数和最小公倍数算法总结 单位:隆回县职业中等专业学校 作者:刘小华 摘 要:介绍自己通过学习使用C语言求任意两个数的最大公约数和最小公倍数的基本算法思想、算法过程、代码实现以及分析比较。 关键词:C语言 算法 最大公约数 最小公倍数 中图分类号: TP312 文献标识码:A The algorithm summarization of evaluating the highest common divisor and the lowest common multiple in C Lan...

C语言求最大公约数和最小公倍数算法总结
C语言求最大公约数和最小公倍数算法总结 单位:隆回县职业中等专业学校 作者:刘小华 摘 要:介绍自己通过学习使用C语言求任意两个数的最大公约数和最小公倍数的基本算法思想、算法过程、代码实现以及 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 比较。 关键词:C语言 算法 最大公约数 最小公倍数 中图分类号: TP312 文献标识码:A The algorithm summarization of evaluating the highest common divisor and the lowest common multiple in C Language Zhao Ye Lin Tutor Teacher:Liu Xiao Hua Abstract:Introduction to the algorithm basic thought, algorithm process and code realization and its analysing comparison in terms of evaluating the highest common divisor and the lowest common multiple of any two positive integers by learning to using C Language Keywords:C Language algorithm the highest common divisor the lowest common multiple C语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点,它常常作为计算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 定义法、递归调用法等。下面结合我学习以来的笔记整理、总结几种常用的方法进行比较,以便能够更好的理解、应用、共勉。 前提:假设求任意两个整数的最大公约数和最小公倍数,采用函数调用形式进行。 1、辗转相除法 辗转相除法(又名欧几里德法)C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的定理: a b=0 gcd(a,b) = gcd(b,a mod b) b!=0 根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下: ?、函数嵌套调用 其算法过程为: 前提:设两数为a,b设其中a 做被除数,b做除数,temp为余数 1、大数放a中、小数放b中; 2、求a/b的余数; 3、若temp=0则b为最大公约数; 4、如果temp!=0则把b的值给a、temp的值给a; 5、返回第第二步; 代码: int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ { int temp; /*定义整型变量*/ if(a 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。 2、穷举法(利用数学定义) 穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始 由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。 ?、定义1:对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被 a和b所整除,则temp即为最大公约数。 代码为: int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ { int temp; /*定义义整型变量*/ temp=(a>b)?b:a; /*采种条件运算 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式求出两个数中的最小值*/ while(temp>0) { if (a%temp==0&&b%temp==0) /*只要找到一个数能同时被a,b所整除~则中止循环*/ break; temp--; /*如不满足if条件则变量自减~直到能被a,b所整除*/ } return (temp); /*返回满足条件的数到主调函数处*/ } #include "stdio.h" main() { int m,n,t1; printf("please input two integer number:"); scanf("%d%d",&m,&n); t1=divisor(m,n); printf("The higest common divisor is %d\n",t1); getch(); } ?、定义2:对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除,则 该和数即为所求的最小公倍数。 代码为: int multiple (int a,int b) { int p,q,temp; p=(a>b)?a:b; /*求两个数中的最大值*/ q=(a>b)?b:a; /*求两个数中的最小值*/ temp=p; /*最大值赋给p为变量自增作准备*/ while(1) /*利用循环语句来求满足条件的数值*/ { if(p%q==0) break; /*只要找到变量的和数能被a或b所整除~则中止循环*/ p+=temp; /*如果条件不满足则变量自身相加*/ } return (p); } #include "stdio.h" main() { int m,n,t2; printf("please input two integer number:"); scanf("%d%d",&m,&n); t2=multiple(m,n); printf("The least common multiple is %d\n",t2); getch(); } 启示:根据数学定义求任意两个正整数的最大公约数和最小公倍数,相对辗转相除法来说,易 懂,容易被学习者接受,但也请读者注意强制退出循环过程的条件、变量的特点及控制语句的使用。 结束语 C语言编程关键在于确定好算法及算法过程,同时要合理定义变量和函数及控制语句操作,只 有这样才能保证编程的正确性、、可读性、实用性。 参考文献 [1] C程序设计 第二版 谭浩强 清华大学出版社 2004 [2] 常用算法程序集(C语言描述)第三版 徐士良 清华大学出版社 2004 [3] 数据结构(C语言版)严蔚敏 吴伟民 清华大学出版社 2002 [4] 算法与程序设计 南志红 中国物资出版社 2002年
本文档为【C语言求最大公约数和最小公倍数算法总结】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_569018
暂无简介~
格式:doc
大小:25KB
软件:Word
页数:0
分类:高中语文
上传时间:2017-09-30
浏览量:25