求两个数的最大公约数
求两个数的最大公约数
方法一/最简单的算法(效率最低)，如下:
public static int getMaxDivisor(int a, int b) {
int max = 0;
int temp = Math.min(a, b);
for (int i = temp; i > 0; i--) {
if (a % i == 0 && b % i == 0) {
max = i;
break;
}
}
return max;// 当max为0时，即没有最大公约数
}
方法二/代码最少的算法，如下:
public static int getMaxDivisor(int a, int b){
if(Math.min(a, b)==0){
return Math.max(a, b);
}else{
return getMaxDivisor2(Math.min(a, b), Math.max(a, b)%Math.min(a, b));
}
}
方法三/方法二的变换，如下:
public static int getMaxDivisor(int a,int b){
int x=a;
int y=b;
while(Math.min(x,y)!=0){
int temp=y;
y=Math.min(x,y);
x=Math.max(temp,x)%Math.min(temp,x);
if(Math.min(x,y)==0){
return Math.max(x,y);
}
}
return Math.max(a,b);
}
—[讨论]求两个数的最大公约数的问题的算法
主题：[讨论]求两个数的最大公约数的问题的算法
小弟是新人,请教各位了,M 和N 的最大公约数的算法是什么呢? 谢了!
m和n的最大公约数
int temp, r ,p;
if(n < m)
{
temp = n;
n = m;
m = temp;
}
p =n * m;
while(m != 0)
{
r = n % m;
n = m;
m = r
}
m是最大公约, p/n是最小公倍
#include "stdafx.h"
#include "iostream.h"
int main(int argc, char* argv[])
{
int m,n;
cin>>m>>n;
if(m<=n&&n%m==0)
cout<<"最大公约数是"< else { if(n<=m&&m%n==0) cout<<"最大公约数是"< else cout<<"最大公约数是"< } return 0; } 在c++6.0中试一下 用碾转相除法 #include void main() { int m,n,r,temp,p; printf("请输入两个正整数n,m:"); scanf("%d,%d",&m,&n); if(m>n) {temp=n; n=m; m=temp; //把大的整数放在n中，小的整数放在m中 } p=m*n; //先将n和m的乘积保存在p中，以便求最小公倍数时用while(m!=0) { r=n%m;//求n和m的最大公约数 n=m; m=r; } printf("它们的最大公约数为:%d\n",n); printf("它们的最小公倍数为:%d\n",p/n); } 作者：rickone 发表时间：2006-4-2 13:20:00 第5楼 求两个数的最大公约数： int euc_gcd(int a,int b) { /*if(a%b==0)return b; */ if(b==0)return a; return euc_gcd(b,a%b); } 非递归形式： int euc_gcd(int a,int b) { int r=a%b; while(r>0) { a=b; b=r; r=a%b; } return b; } 算法：-->（转https://www.sodocs.net/doc/912733546.html,/article.asp?id=48） 欧几里德算法又称辗转相除法，我们将两个不全为0的非负整数m和n的最大公约数记为gcd(m,n)，代表能够整除（即余数为0）m和n的最大正整数。欧几里得算法基于的方法是重复应用等式gcd(m,n)=gcd(n,m mod n)，直到m mod n等于0。 我们先来证明gcd(m,n)=gcd(n,m mod n)：m可以表示成m=kn+r，则r=m mod n；假设d 是m和n的一个公约数，则有d|m和d|n，而r=m-kn，因此d|r，因此d是(n,m mod n)的公约数；假设d 是(n,m mod n)的公约数，则d|n，d|r，但是m=kn+r，因此d也是(a,b)的公约数；因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。 具体步骤描述如下： 第一步：如果n=0，返回m的值作为结果，同时过程结束；否则，进入第二步。 第二步：用n去除m，将余数赋给r。 第三步：将n的值赋给m，将r的值赋给n，返回第一步。 伪代码描述如下： Euclid(m,n) // 使用欧几里得算法计算gcd(m,n) // 输入：两个不全为0的非负整数m，n // 输出：m，n的最大公约数 while n≠0 do r ←m mod n m ←n n ←r 作者：220500323lcq 发表时间：2006-10-30 18:25:00 第6楼 好像还3不错啊,不过好像还有更好理解的额...... 作者：WinWing 发表时间：2007-2-10 0:16:00 第7楼 贴多一种. stein算法(移位相减)： int Stein(int a, int b) { int aa[255] = {0}; int ba[255] = {0}; int ca[255] = {0}; aa[0] = a; ba[0] = b; ca[0] = 1; for (int i = 0; i < 255; i++) { if (0 == aa[i]) { return ba[i]; } if (0 == ba[i]) { return aa[i]; } if ((0 == (aa[i] & 1)) && (0 == (ba[i] & 1))) {// 都是偶数 aa[i+1] = aa[i] >> 1; ba[i+1] = ba[i] >> 1; ca[i+1] = ca[i] << 1; } if ((0 == (aa[i] & 1)) && (1 == (ba[i] & 1))) {// an是偶数，bn不是 aa[i+1] = aa[i] >> 1; ba[i+1] = ba[i]; ca[i+1] = ca[i]; } if ((0 == (ba[i] & 1)) && (1 == (aa[i] & 1))) {// bn是偶数，an不是 ba[i+1] = ba[i] >> 1; aa[i+1] = aa[i]; ca[i+1] = ca[i]; } if ((1 == (ba[i] & 1)) && (1 == (aa[i] & 1))) {// 都不是偶数 aa[i+1] = abs(ba[i] - aa[i]); ba[i+1] = aa[i] < ba[i] ? aa[i]:ba[i]; ca[i+1] = ca[i]; } } } 网上有种说法如下: 引用： 为了说明Stein算法的正确性，首先必须注意到以下结论： gcd(a,a) = a，也就是一个数和他自身的公约数是其自身 gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除 有了上述规律就可以给出Stein算法如下： 1.如果A=0，B是最大公约数，算法结束 2.如果B=0，A是最大公约数，算法结束 3.设置A1 = A、B1=B和C1 = 1 4如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可) 5.如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 6.如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 7.如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn n++，转4 其实应该还包括一个前提:gcd(a,b)=gcd(a-b,b) 作者：bpttc 发表时间：2007-2-11 1:10:00 第8楼 问题的引出：如何求出两个数x和y的最大公约数？ 最简单的思路，分别求出x和y的约数，再寻找最大公约数。这个方法是从公约数的定义入手，如果x和y比较大，工作量可想而只，能不能偷懒呢？ 不妨设x>y ，首先能想到的特殊情况是x是y的整倍数，即x=n*y时（n为正整数），x和y最大公约数就是y了。如果x不是y的整倍数呢？肯定是跟r=x%y 有某种联系。 我们令a为x和y的最大公约数，再令x=n*y+r，那么(x/a)=n*(y/a)+(r/a)。因为(x/a)是整数，(y/a)是整数，所以(r/a)是整数，即r可以被a整除。我们得出一个有用的结论，a 是y和r的公约数。 下面我们的问题是a是否是y和r的最大公约数，或者和最大公约数有某种联系？ 我们设y和r的最大公约数是b，则有a<=b，还是利用x=n*y+r，有(x/b)=n*(y/b)+(r/b)，因为(y/b)是整数，(r/b)是整数，所以(x/b)是整数，即x可以被b整除。得出结论：b是x和y的公约数。因为a是x和y的最大公约数，所以又有b<=a，结合前面的a<=b，得出a=b。即x和y的最大公约数是y和r的最大公约数。 回到前面的问题，我们已经找出x和y的最大公约数和r之间的某种联系，能否利用他求最大公约数呢？ 我们看看x y r 三者的大小，因为x%y=r，所以y>r ，又因为x=n*y+r ，所以x>r。我们令f(x,y)表示x和y的最大公约数。 那么有，设r1=max{x,y}；r2=min{x,y} f(r1,r2)=f(r2,r3) 其中r3=r1%r2 f(r2,r3)=f(r3,r4) 其中r4=r2%r3 ...... f( r[i],r[i+1] )=f( r[i+1],r[i+2] ) 其中r[i+2]=r[i]%r[i+1] 这样就可以将f内的两个数缩小下去，直到r[i]是r[i+1]的整倍数，那么r[i+1]即为x和y的最大公约数。 首先列出的是我采用了递归的算法。 //函数原型int gcd(int x,int y); //函数功能求正整数x和正整数y的最大公约数greatest common divisor //参数要求x>0,y>0 //返回值>0时为x和y的最大公约数，=-1时为参数错误 #define ERROR -1 //参数错误时的返回值 int gcd(int x,int y) { if( x<=0 || y<=0 ) return ERROR; int temp; if(x { temp=x;x=y;y=temp; } if(x%y==0) return y; else return gcd(y,x%y); } 接着就是非递归的算法 //函数原型int gcd(int x,int y); //函数功能求正整数x和正整数y的最大公约数greatest common divisor //参数要求x>0,y>0 //返回值>0时为x和y的最大公约数，=-1时为参数错误 #define ERROR -1 //参数错误时的返回值 int gcd(int x,int y) { if( x<=0 || y<=0 ) return ERROR; int r; if(x { r=x;x=y;y=r; } while( 0!=(r=x%y) ) { x=y; y=r; } return y; } #include "stdio.h" main() { int m,n,i; scanf("%d %d",&m,&n); while(m>n) { i=(m-n); if(i==n) printf("%d",n); if(i>n) m=i; else {m=n; n=i; } } while(n>m) { i=(n-m); if(i==m) printf("%d",m); if(i>m) n=i; else { n=m; m=i; } } } m和n的最大公约数 int temp, r ,p; if(n < m) { temp = n; n = m; m = temp; } p =n * m; while(m != 0) { r = n % m; n = m; m = r } m是最大公约, p/n是最小公倍 #include "stdafx.h" #include "iostream.h" int main(int argc, char* argv[]) { int m,n; cin>>m>>n; if(m<=n&&n%m==0) cout<<"最大公约数是"< else { if(n<=m&&m%n==0) cout<<"最大公约数是"< else cout<<"最大公约数是"< } } 这个#include "stdafx.h"~~~~~~ 昆明理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：算法设计与分析开课实验室：信自楼机房444 2011 年10月 12日 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数 1、连续整数检测法。 2、欧几里得算法 3、分解质因数算法 根据实现提示写代码并分析代码的时间复杂度： 方法一： int f1(int m,int n) { int t; if(m>n)t=n; else t=m; while(t) { if(m%t==0&&n%t==0)break; else t=t-1; } return t; } 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 方法二：int f2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } 根据代码辗转相除得到欧几里得的O(n)= log n 方法三： int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i . 求几个数的最大公因数的方法答案 知识梳理 教学重、难点 作业完成情况 典题探究 例1．数A、3×3×5，数B=2×2×3×5，数C=2×3×3×5，A、B、C三个数的最大公约数是15 ，最小公倍数是． 考点：求几个数的最大公因数的方法；求几个数的最小公倍数的方法． 专题：压轴题；数的整除． 分析：求最大公约数也就是这几个数的公有质因数的连乘积，最小公倍数是公有质因数与独有质因数的连乘积；对于三个数：三个数公有质因数的乘积是最大公约数，三个数的公有质因数、两个数的公有质因数与每个数独有质因数的连乘积是最小公倍数，由此解决问题即可． 解答：解：数A=3×3×5，数B=2×2×3×5，数C=2×3×3×5， 所以A、B、C三个数的最大公约数是：3×5=15， 最小公倍数是：3×5×2×3×2=； 故答案为：15，． 点评：此题主要考查求三个数的最大公约数与最小公倍数的方法：三个数的公有质因数连乘积是最大公约数，三个数的公有质因数、两个数的公有质因数与每个数独有质因数的连乘积是最小公倍数． 例2．集小学学前班买来一筐橙子，分给5个人最后余2个，分给7人最后余2个，分给9人也余2个，学前班最少买来多少个橙子？ 考点：求几个数的最小公倍数的方法． 专题：约数倍数应用题． 分析：根据分给5个人余2个，分给7人余2个，分给9人也余2个，可知这筐橙子的总个数减去2就是5、7和9的公倍数，要求至少也就是用5、7和9的最小公倍数加上2即可． 解答：解：因为5、7和9三个数两两互质， 所以它们的最小公倍数是它们的乘积，即5×7×9=315， 所以这筐橙子至少有：315+2=317（个）； 答：学前班最少买来317个橙子． 点评：解答本题关键是理解：这筐橙子的总个数减去2就是5、7和9的公倍数，求至少有的个数，就用它们的最小公倍数加上2即可． 例3．一次数学竞赛，结果学生中获得一等奖，获得二等奖，获得三等奖，其余获纪念奖．已知参加这次竞赛的学生不满50人，问获纪念奖的有多少人？ 考点：求几个数的最小公倍数的方法． 分析：即求在50以的7、3和2的公倍数，先求出这三个数的最小公倍数，因为这三个数两两互质，这三个数的最小公倍数即这三个数的乘积，然后根据题意，进行选择，判断出参加这次竞赛的学生的人数；然后把参加这次竞赛的学生的人数看作单位“1”，获 纪念奖的人数占参加竞赛人数的（1﹣﹣﹣），继而根据一个数乘分数的意义，用 乘法解答即可． 解答：解：2、3和7的最小公倍数是2×3×7=42， 因为在50以的7、3和2的公倍数只有1个42， 所以参加这次竞赛的学生有42个，纪念奖有： 42×（1﹣﹣﹣）， =42×， =1（人）； 答：获纪念奖的有1人． 点评：此题考查了求几个数的最小公倍数的方法，当三个数两两互质时，其最小公倍数就是这三个数的乘积． 例4．求下列每组数的最大公因数和最小公倍数． 9和11 28和7 10和25 最大公因数： 1 最大公因数：7 最大公因数： 5 最小公倍数：99 最小公倍数：28 最小公倍数：50 ． . 1、查找约数法． 先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是最大公约数． 例如，求12和30的最大公约数． 12的约数有：1、2、3、4、6、12； 30的约数有：1、2、3、5、6、10、15、30． 12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数． 2 更相减损术 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。 3、辗转相除法． 当两个数都较大时，采用辗转相除法比较方便．其方法是： 以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数． 例如：求4453和5767的最大公约数时，可作如下除法． 5767÷4453＝1余1314 4453÷1314＝3余511 1314÷511＝2余292 511÷292＝1余219 292÷219＝1余73 219÷73＝3 于是得知，5767和4453的最大公约数是73． 辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．4、求差判定法． 如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公约数就是原来两个数的最大公约数．例如：求78和60的最大公约数．78－60＝18，18和60的最大公约数是6，所以78和60的最大公约数是6． 如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数的最大公约数就是原来两数的最大公约数．例如：求92和16的最大公约数．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公约数是4，所以92和16的最大公约数就是4． 5、分解因式法． 先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相乘，得到的积就是这两个数的最大公约数． 例如：求125和300的最大公约数．因为125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公约数是5×5＝25． 6、短除法． 为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公约数就是所有除数的乘积． 例如：求180和324的最大公约数． 因为： 5和9互质，所以180和324的最大公约数是4×9＝36． 7、除法法． 当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能够整除，则较小的数是这两个数的最大公约数． 例如：求19和152，13和273的最大公约数．因为152÷19＝8，273÷13＝21．（19和13都是质数．）所以19和152的最大公约数是19，13和273的最大公约数是13． 1，写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果。这两个数由键盘输入。 程序设计： #include #include 算法设计与分析 11信本余启盛 118632011004 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图 （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件matlab .2008 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数 1、连续整数检测法。 2、欧几里得算法 3、蛮力法（短除法） 根据实现提示写代码并分析代码的时间复杂度： 算法一：连续整数检测法。 CommFactor1 输入：两个自然数m和n 输出：m和n的最大公约数 1.判断m和n哪个数小，t=min（m，n） 2.如果m%t==0&&n%t==0 ，结束 2.1 如果t不是m和n的公因子，则t=t-1; 3. 输出t ; 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 算法二：欧几里德算法 CommFactor2 输入：两个自然数m和n 输出：m和n的最大公约数 1. r = m % n; 2. 循环直到r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出n ; 根据代码辗转相除得到欧几里得的: O(n)= log n 算法三：蛮力法（短除法） CommFactor3 输入：两个自然数m和n 输出：m和n的最大公约数 1.factor=1； 2.循环变量i从2-min（m，n），执行下述操作： 2.1 如果i是m和n的公因子，则执行下述操作： 2.1.1 factor=factor*i； 2.1.2 m = m / i; n = n / i; 2.2 如果i不是m和n的公因子，则i=i+1； 3. 输出factor； 根据代码考虑最坏情况他们的最大公约数，循环做了i-1次;最好情况是只做了1次，可以得出: O（n）=n/2; MATLAB程序代码： main.m x=fix(rand(1,1000)*1000); y=fix(rand(1,1000)*1000); for i=1:1000 A(i)=CommFactor2(x(i),y(i)); end x=x'; y=y'; 第一章小学数学解题方法解题技巧之最大公约数法 通过计算出几个数的最大公约数来解题的方法，叫做最大公约数法。 例1 甲班有42名学生，乙班有48名学生，现在要把这两个班的学生平均分成若干个小组，并且使每个小组都是同一个班的学生。每个小组最多有多少名学生？（适于六年级程度） 解：要使每个小组都是同一个班的学生，并且要使每个小组的人数尽可能多，就要求出42和48的最大公约数： 2×3=6 42和48的最大公约数是6。 答：每个小组最多能有6名学生。 例2 有一张长150厘米、宽60厘米的长方形纸板，要把它分割成若干个面积最大，井已面积相等的正方形。能分割成多少个正方形？（适于六年级程度） 解：因为分割成的正方形的面积最大，并且面积相等，所以正方形的边长应是1 50和60的最大公约数。 求出150和60的最大公约数： 2×3×5=30 150和60的最大公约数是30，即正方形的边长是30厘米。 看上面的短除式中，150、60除以2之后，再除以3、5，最后的商是5和2。这说明，当正方形的边长是30厘米时，长方形的长150厘米中含有5个30厘米，宽6 0厘米中含有2个30厘米。 所以，这个长方形能分割成正方形： 5×2=10（个） 答：能分割成10个正方形。 例3 有一个长方体的方木，长是3.25米，宽是1.75米，厚是0.75米。如果将这块方木截成体积相等的小正方体木块，并使每个小正方体木块尽可能大。小木块的棱长是多少？可以截成多少块这样的小木块？（适于六年级程度） 解：3.25米=325厘米，1.75米=175厘米，0.75米=75厘米，此题实际是求325、175和75的最大公约数。 5×5=25 325、175和75的最大公约数是25，即小正方体木块的棱长是25厘米。 因为75、175、325除以5得商15、35、65，15、35、65再除以5，最后的商是3、7、13，而小正方体木块的棱长是25厘米，所以，在75厘米中包含3个25厘米，在175厘米中包含7个25厘米，在325厘米中包含13个25厘米。 可以截成棱长是25厘米的小木块： 3×7×13=273（块） 答：小正方体木块的棱长是25厘米，可以截成这样大的正方体273块。 例4 有三根绳子，第一根长45米，第二根长60米，第三根长75米。现在要把三根长绳截成长度相等的小段。每段最长是多少米？一共可以截成多少段？（适于六年级程度） 实验报告三JA VA程序设计基础 1．实验目的 熟练运用分支、循环等语句控制程序流程，掌握方法的声明和调用，以及字符串。掌握使用命令行参数作为输入数据的方法，找出程序错误位置和出错原因。 2．实验内容 （）：书上60页，2-26求N个整数的最大公约数。 代码： Gys.java——文件名 public class Gys { public static int gys(int a,int b) { int temp; while(b!=0) { temp=a%b; a=b; b=temp; System.out.print("gys("+a+","+b+")=");——输出运算过程 } System.out.println(a);——输出最大公约数 return a; } public static void main(String[] args) { int n=5,x,y,temp; int a[]={12,60,160,64,80}; temp=a[0]; for(int i=0;i （2）验证性实验：书上P54例2.10从标准输入流中读取一行字符串再转换成整数。 代码： Input.java——文件名 import mypackage.*; public class Input { public static String readLine()throws java.io.IOException { System.out.println("输入一行字符串，以回车换行符结束"); byte buffer[]=new byte[512]; int count=System.in.read(buffer); System.in.close(); return(count==-1)?null:new String(buffer,0,count-2); } public static void main(String args[])throws java.io.IOException { String s=readLine(); int value=MyInteger.parseInt(s); System.out.println("MyInteger.toString("+value+",2)="+MyInteger.t oString(value,2)); System.out.println("MyInteger.toString("+value+",16)="+MyInteger. toString(value,16)); } } MyInteger.java——文件名 package mypackage; public class MyInteger { public static int parseInt(String s) throws NumberFormatException { if(s==null) throw new NumberFormatException("null"); char ch=s.charAt(0); #pragma warning(disable:4786) #include while (true) { if ((m = m % n) == 0) return n; if ((n = n % m) == 0) return m; } } public static void main(String args[]) throws Exception { //取得输入值 //Scanner chin = new Scanner(System.in); //int a = chin.nextInt(), b = chin.nextInt(); int a=23; int b=32; int c = gcd(a, b); System.out.println("最小公倍数：" + a * b / c + "\n最大公约数：" + c); } } 理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：算法设计与分析开课实验室：信自楼机房444 2011 年10月 12日 一、上机目的及容 1.上机容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数 1、连续整数检测法。 根据实现提示写代码并分析代码的时间复杂度： 方法一： int f1(int m,int n) { int t; if(m>n)t=n; else t=m; while(t) { if(m%t==0&&n%t==0)break; else t=t-1; } return t; } 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 方法二：int f2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } 根据代码辗转相除得到欧几里得的O(n)= log n 方法三： int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i 论在小学教材中求最大公约数和最小公倍数的方法 班级：08数三班 学号：30308346 姓名：钟世校 初等数论是研究整数最基本性质的一门十分重要的数学基础课程,整除理论是初等数论的基础,其中心内容是最大公约数理论和算术基本定理,而我现在要论述的是求最大公约数和最小公倍数的几种方法 首先,让我们一起在来来了解一下最大公约数与最小公倍数的定义: 最大公约数: 设1a , 2a ,…，n a (n ≥2)是不全为零的整数,如果d| i a (i =1,2,3…,n),则称d 为 1a , 2a ,…，n a 的公约数,全体公约数中最大的一个数称为 1a , 2a ,…，n a 的最大公约数,记作(1a , 2a ,…，n a ). 最小公倍数: 设1a , 2a ,…，n a 是非零整数.若有整数M, 使 i a | M (i =1,2,3…,n ),则称 M 为1a , 2a ,…， n a 的公倍数,公倍数中最小的正数,称为1a , 2a ,…，n a 的最小公倍数,记作[1a , 2a ,…，n a ]。 求最大公约数的方法通常有两种,即用分解质因数法求最大公约数或用辗转相除法求最大公约数（亦称欧几里得算法），而求最小公倍数通常是用分解质因数或利用最大公约数来求最小公倍数,下最面我通过几道例题来演示上述方法. 一、 求最大公约数的方法. ⒈用分解质因数法求最大公约数. 例1. 求2700 、 7560、3960的最大公约数 解：把2700 、7560 、3960分别分解质因数. 得 2700=32 2 35 2?? 7560=3 3 357 2??? 3960= 2 3 352 11 ??? ∴ (2700,7560,3960)= 2 2 352 ??180 = 即2700 、 7560 、3960的最大公约数为180. 五年级数学教案：求两个数的最大公约数1 ①使学生理解公约数、最大公约数、互质数的概念。 ②使学生初步掌握求两个数最大公约数的一般方法。 ③培养学生抽象、概括的能力和动手实际操作的能力。 教学重点理解公约数、最大公约数、互质数的概念。 教学难点理解并掌握求两个数的最大公约数的一般方法。 教学用具投影仪等。 教学过程 一、创设情境 填空：①123=4，所以12能被4（）。4能（）12，12是3的（），3是12的（）。②把18和30分解质因数是，它们公有的质因数是（）。③10的约数有（）。 二、揭示课题 我们已经学会求一个数的约数，现在来看两个数的约数。 三、探索研究 1．小组合作学习 （1）找出8、12的约数来。 （2）观察并回答。 ①有无相同的约数？各是几？ ②1、2、4是8和12的什么？ ③其中最大的一个是几？知道叫什么吗？ （3）归纳并板书 ①8和12公有的约数是：1、2、4，其中最大的一个是4。 ②还可以用下图来表示。 813 24612 8和12的公约数 （4）抽象、概括。 ①你能说说什么是公约数、最大公约数吗？ ②指导学生看教材第66页里有关公约数、最大公约数的概念。 （5）尝试练习。 做教材第67页上面的做一做的第1题。 2．学习互质数的概念 （1）找出下列各组数的公约数来：5和78和912和251和9 （2）这几组数的公约数有什么特点？ （3）这几组数中的两个数叫做什么？（看书67页） （4）质数和互质数有什么不同？（使学生明确：质数是一个数，而互质数是两个数的关系） 3．学习例2 （1）出示例2并说明：我们通常用分解质因数的方法来求两个数的最大公约数。 （2）复习的第2题，我们已将18和30分解质因数（如后）18=23330=235 （3）观察、分析。 基本算法——辗转相除法 问题：输出两个正整数a,b,且0 改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q： q= a*b/p; 源程序2 #include 求最大公约数教案 道真县中等职业学校张学东 教学目标： 1．使学生进一步理解和掌握公约数和最大公约数的意义。 2．使学生理解和掌握用短除法、分解质因数的方法两个数的最大公约数的算理。 教学难点：用分解质因数的方法求两个数的最大公约数的算理。 教学设计： 一约数 【引例】看下面的式子： 18÷6 25÷5 24÷3 99÷11 169÷13这些除式中，商都是整数，余数为0.我们在数的整除中已经知道，这些除式都是整除式。 【小结】如果一个整数a除以整数b（b≠0）除得的商正好是整数而没有余数，那么我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。 上式中6是18的约数，5是25的约数，3是24的约数，11是99的约数，13是169的约数……，显然约数只存在于整除式中，故不是整除式就不存在约数。 二公约数及最大公约数 【引例】看下面的式子： 48÷8 24 ÷8 56÷8 ，显然，这些都是整除式，8是48、 24、56、这些所有整数的约数。 【小结】如果一个整数同时是几个整数的约数，那么就称这个 整数是它们的公约数。 公约数亦称公因数，公约数中最大的我们称它为最大公约数，若a 、b 的最大公约数为c ， 三 公约数与最大公约数的求法 求最大公约数的求法一般有：枚举法、短除法、分解质因数法、 1、短除法： 【讲解】 短除符号就像一个倒过来的除号，短除法就是先写出要求最大公因数的两个数A 、B ，再画一个短除号，接着在原本写除数的位置写两个数公有的质因数Z （通常从最小的质因数开始），然后在短除号的下方写出这两个数被Z 整除的商a 、b ，对a 、b 重复以上步骤，以此类推，直到最后的商互质为止，再把所有的除数相乘，其积即为A 、B 的最大公约数。 例1： 用短除法求12和18的最大公约数。 解:∵ ∴12和18的最大公约数为2×3=6 2、分解质因数法 【讲解】将要求最大公因数的两个数A 、B 分别分解质因数，再从中找出A 、B 公有的质因数，把这些公有的质因数相乘，即得到A 、2 12 18 6 9 3 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 C语言求最大公约数和最小公倍数算法 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 1.辗转相除法GCD算法的基本原理 DCD - Greatest Common Divisor 欧几里得定理： 若 a = b * r + q，则 GCD(a,b) = GCD(b,q)。 证明： 假设 c = GCD(a,b) 则存在m使得 a = m * c,b = n * c; 因为 a = b * r + q, 则 q = a - b * r = m * c - n * c * r = (m - n * r) * c; 因为 b = n * c , q = (m - n * r) * c 故要证明GCD(a,b) = GCD(b,q)，即证明 n 与 m - n * r互质 下面证明 m-n×r与n互质： 假设不互质，则存在公约数k使得 m - n * r = x * k, n = y * k. 则: a = m * c = (n * r + x * k) * c = (y * k * r + x * k) * c = (y * r + x) * k * c b = n * c = y * c * k 则GCD(a,b) = k * c,与 c=gcd(a, b) 矛盾 2.辗转相除法算法的实现 2.1递归实现 自己改进 2.2迭代实现 3.更相减损法 更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。 例如：用更相减损术求260和104的最大公约数。 解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。此时65是奇数而26不是奇数，故把65和26辗转相减： 65-26=39 39-26=13 26-13=13 实验九 一、实验内容 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10 用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 二、实验目的 1、掌握函数的嵌套调用好递归调用 2、掌握递归算法 3、了解内联函数、重载函数、带默认参函数的定义及使用方法 4、掌握程序的多文件组织 5、掌握编译预处理的内容，理解带参数宏定义与函数的区别 三、实验步骤 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 四、实验数据及处理结果最大公约数的三种算法 复杂度分析 时间计算
求几个数的最大公因数的方法-答案
最大公约数的算法
c语言程序设计-求两个数最大公约数
matlab最大公约数 三种算法
小学数学解题方法解题技巧之最大公约数法
java求n个整数的最大公约数
c++实现计算任意多个三位数的最大公约数,直到输入-999为止,调用子函数求最大公约数
最大公约数的三种算法复杂度分析时间计算
论最小公倍数和最大公约数的方法
五年级数学教案：求两个数的最大公约数1
C语言算法——最大公约数
求最大公约数教学设计
最大公约数和最小公倍数算法
C语言求最大公约数和最小公倍数算法
求最大公约数的原理及算法实现
c++,使用欧几里得算法计算两个数的最大公约数,分别用递推和递归两种算法实现5
相关文档
- 求最大公因数和最小公倍数的方法(简单实用)
- 求最大公因数的特殊方法
- 求最大公因数和最小公倍数的方法(简单实用)
- 最大公因数和最小公倍数
- 求最大公因数和最小公倍数的方法(简单实用)
- 求最大公因数九种方法
- 求最大公因数的三种方法
- 最大公因数和最小公倍数讲解
- 求两个数最大公因数和最小公倍数的3种规律总结
- 公因数和最大公因数、公倍数和最小公倍数
- 最大公因数与最小公倍数
- 常用的两数的最大公因数
- 求最大公因数的诀窍
- 求最大公因数的方法辗转相除法
- 求两个数的最大公因数的方法
- 求两个数的最大公因数
- 最新小学人教版五年级下册求两个数最大公因数的实际应用教案设计
- 人教版五年级数学下册 《求两个数的最大公因数》教学设计
- Java求两个数的最大公约数和最小公倍数
- 用短除法求两个数的最大公因数