给定两个正整数m和n,求它们的最大公因子,即能够同时整除m和n的最大正整数。
E1.【求余数】
以n除m并令r为所得余数。(我们将有0<=r<n)
E2.【余数为零?】若r=0,算法结束,n即为答案。
E3.【减少】置mß---n,nß-r,并返回步骤E1
package com.javaeye.rsrt;
/**
* @description 求两个数的最大公因子
* @author nishiting
* @date 2010-9-15
*/
public class CommonFactor {
/**
* @param arags
*/
public static int result=0;
public static void main(String[] args) {
int a = 77;
int b = 21;
CommonFactor cf = new CommonFactor();
cal c = cf.new cal();
c.calculate(a, b);
System.out.println(a + "与" + b + "的最大公因子为:" + ((Integer)result).toString());
}
private class cal {
public cal() {
}
public void calculate(int a, int b) {
// 如果a比b小,那么a与b交换
if (a < b) {
int temp = a;
a = b;
b = temp;
}
if (a % b == 0) {
result = b;
} else {
int r = a % b;
a = b;
b = r;
calculate(a, b);
}
}
}
}
分享到:
相关推荐
在C#中,计算两个整数的最大公约数(Greatest Common Divisor, GCD)可以通过多种算法实现,其中最著名和高效的是欧几里得算法。欧几里得算法基于这样一个事实:两个整数的最大公约数等于其中较小的数和两数的差的...
·动态规划的两个应用(第15.1节和第15.5节)。 ·利用随机化和线性规划技术的近似算法(第35.4节)。 ·为了使更多的算法可以更早地在书中出现,第1版中有关数学背景知识的三章内容从第一部分移到了附录中,即现在...
例1 求两个正整数最大公因子的一个实例 假设 m=21 和 n=45,求21和45的最大公因子 第一步:r=m%n=21%45=21; 第二步:r 不等于0,转入第三步; 第三步:互换,m=n=45, n=r=21,返回第一步。 第一步:r=m%n=45%21=3...
5、求两个数的最大公约数和最小公倍数。 6、有两只兔子,每三个月生育两只兔子,生下来的兔子每过3个月又可以生兔子,求n个月后,一共有多少只兔子? 第二次编程题目: 1.输入一行字符,分别统计出其中英文字母、...
最大公约数:最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。 界面模块 界面分为了主界面和菜单界面,二者通过 menu 按钮相互联系,菜单界面主要提供了数学计算所需要的内容,按下...
8.1写两个函数,分别求两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果,两个整数由键盘输入。 47 8.2 47 8.3写一个判素数的函数,在主函数输入一个整数,输出是否素数的信息。 49 8.4写一...
用辗转相除法计算任意两个整数a、b的最大公因子。进一步求出整数s、t,使得sa+tb=(a,b)。特别地,当a=3378,b=231时,求出相应的s,t以及a与b的最大公因子(a,b)。
辗转相除法是整数和多项式理论中求最大公因数和最大公因式的一类重要方法,对于较大的两个整数和次数较高的两个多项式而言,利用辗转相除法手动计算它们的最大公因数和最大公因子运算量非常大,基于减少运算时间并...
题目:输入两个正整数m和n,求其最大公约数和最小公倍数。 1.程序分析:利用辗除法。 【程序7】 题目:输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1.程序分析:利用while语句,条件为...
最大公约数 a^b mod n 扩张欧几里德算法 素数表质因子分解 Stirling公式 中国剩余定理 欧拉数(递推法) 欧拉数(公式法) 十进制转负进制 归并排序求逆序数 Pell方程 Catalan数,100以内 欧拉函数讲解 组合...
程序23: 最大公约数 20 程序24: 最小公倍数 21 程序25: 字符串判断 22 程序26: 合并文件数据 23 程序27: 猜数游戏 24 程序28:为数据加密 25 程序29:平方运算 26 程序30: 计算0-7组成的奇数个数 27 程序31:...
题目:输入两个正整数m和n,求其最大公约数和最小公倍数。 1.程序分析:利用辗除法。 【程序7】 题目:输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1.程序分析:利用while语句,条件为...
给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得a*m+b*n=d 算法流程 E1.置a’=b=1;a=b’=0;c=m,d=n; E2.计算d和r,使得c=q*d+r; E3.若r==0;则退出,当前已有a*m+b*n=d; E4;c=d;d=r;t=a’;a’...
最大公约数 Euclid算法 扩展的Euclid算法 同余方程 / 二元一次不定方程 同余方程组 线性方程组 高斯消元法 解mod 2域上的线性方程组 整系数方程组的精确解法 矩阵 行列式的计算 利用矩阵乘法快速计算...
循环结构习题:输入两个整数,输出它们的最大公约数 66%(4379/6621) 36% 2020-4-23 1008 顺序结构习题:求三个数的平均值 63%(4500/7162) 39% 2020-4-23 1009 顺序结构习题:求两点之间的距离 61%(4135/6812) 41% ...
实例038 不用strcat连接两个字符串 46 实例039 删除字符串中连续字符 47 实例040 字符升序排列 49 实例041 在指定的位置后插入字符串 50 1.7 函数 51 实例042 求字符串中字符的个数 51 实例043 递归...
不使用中间变量 把两个变量的值互换 int a=10; int b=100; a=a*b; b=a/b; a=a/b; System.out.print("a="+a+" b="+b); 折半查找 public class Test { public static int[] data = { 12, 15, 20, 10, 19, 3, 89, ...
最大公约数 8-2. 使用算术操作符 8-3. 使用&&和||进行混合状态的test 8-4. 数字常量的处理 9-1. $IFS和空白 9-2. 时间输入 9-3. 再来一个时间输入 9-4. Timed read 9-5. 我是root? 9-6. arglist:通过$*和$@列出所有...
最大公约数 8-2. 使用算术操作符 8-3. 使用&&和||进行混合状态的test 8-4. 数字常量的处理 9-1. $IFS 和空白 9-2. 时间输入 9-3. 再来一个时间输入 9-4. Timed read 9-5. 我是root? 9-6. arglist:通过$*和$@列出...
常用算法一 一、计数、求和、求阶乘...二、求两自然数的最大公约数和最小公倍数 三、判断素数 四、验证哥德巴赫猜想 五、穷举法 五、穷举法 常用算法二 排序问题 1.选择法排序 2.冒泡法排序(升序) 数据查找 ……