Java求解两个非负整数最大公约数算法【循环法与递归法】
本文实例讲述了Java求解两个非负整数最大公约数算法。分享给大家供大家参考，具体如下：
代码功能：
1.Java实现（完整源码附测试用例）；
2.求解两个非负整数p，q（p>=q)的最大公约数；
3.循环法 以及 递归法两种求解思路；
完整源码：
/* GCD:Greateast Common Divisor */
public class GCD{
public static void main(String args[]){
/* Test Case */
int p = 32;
int q = 24;
System.out.println("The greatest divisior of "+p+" and "+q+" is \n"+
"[ gcd1 ] : "+gcd1(p,q)+"\n"+"[ gcd2 ] : "+ gcd2(p,q));
}
// (q % gcd ==0 AND p% gcd ==0 [gcd from q to 1])
public static int gcd1(int p,int q){
int gcd=1;
int d=q;
while(d>0){
d--;
if(q%d==0 && p%d==0){
gcd = d;
break;
}
}
return gcd;
}
// gcd(p,q)=gcd(q,p%q)[if q=0,gcd=p]
public static int gcd2(int p,int q){
if(q==0) return p;
int r = p%q;
//System.out.println("("+q+","+r+")");
return gcd2(q,r);
}
}
运行截图：
代码解释：
循环法 gcd1(p,q)
自然语言描述 ：循环法求解两个非负整数p，q（p>=q）的最大公约数，即求解q的公约数中为p的公约数的最大值。令d（被除数）从p开始递减（递减step = 1）d始终为“即将满足条件的最大值”，当d满足条件（既可以被p整除又可以被p整除时），d即p与q的公约数，d即为p、q的最大公约数；
递归法 gcd2(p,q)
自然语言描述： 递归法求解两个非负整数p，q（p>=q）的最大公约数 ，当q等于0时，最大公约数为p；否则，对p、q取余得r=p%q，p、q的最大公约数即为q、r的最大公约数；
代码心得：
关于循环法，一开始我想到的是，写一个求解公约数的方法、用整型数组存储一个非负整数的全部公约数，然后比较找出p、q中共同的那个最大的公约数也就是两个数的最大公约数了，后来想想，既然是求最大，那么就直接从后往前递减岂不是更省事儿，从后往前递减就可以保证这个数一直是当前最大，因为比它大的家伙都不符合条件（能同时被p、q整除）被淘汰掉了啦，就免去了最初需要的找最大这个麻烦，虽然求最大值方法多多，但是如果自己已经或者原本就是就不需要去证明和寻找了哈哈，怎么感觉有点在说哲学 ；
关于递归法，我能依靠我的直觉完全理解的还只有那句p、q的最大公约数就是q、r（r=p%q）的最大公约数这个环的开始，但是还是不太理解环的结束条件 q为0，返回p;
虽然是很简单的求解最大公约数算法，但是非要用两种思路来写一下，主要还是为了再感受一下我不是很熟悉的递归法，以前看求解汉诺塔和斐波那契数的递归算法那明白白的公式亮在那里，就在感慨，这完全就是数学啊！今天学习到的这个，感触居然比那时候还要震撼，不知道发生了什么问题奇妙地就解决了。我到时没太在意什么内存啊、效率之类的指标，只是觉得能想到这个的家伙真的太聪明，对他们而言计算机也好、编程语言也好，真正做到了只是解决问题的工具。有人说，递归是让人脑去思考让计算机去计算的算法，感觉真的是很贴切的说法呢。
参考资料
图灵程序设计丛书:算法(第4版) 塞奇威克 (Robert Sedgewick) (作者), 韦恩 (Kevin Wayne) (作者), 谢路云 (译者)
更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
相关推荐
-
java高效打印一个二维数组的实例(不用递归,不用两个for循环)
打印1个元素,不让循环变量i++,走出思维定式(执行一次循环体,就i++).public class OneForPrint2DArr { public static void main(String[] args) throws Exception { int[][] a = { { 1, 2, 3 }, { 4, 5} }; for (int i = 0, j = 0; i < a.length;) { System.out.println(a[i][j]); j++; if (j >=
-
Java 跳出递归循环问题解决办法
使用异常跳出循环 1.如果方法体内含有需要抛出异常的对象,让方法直接抛出异常,不要在方法体内捕获 public void xxxx() throws Exception 2.如果方法体内不含有需要抛出异常的对象 class Test { static class StopMsgException extends RuntimeException { } public static void main(String args[]) { try { run(0); } catch (StopMsgE
-
Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例
本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积.分享给大家供大家参考,具体如下: 什么是笛卡尔积? 在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员. 假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}. 如何用程序算法实现笛卡尔积? 如果编程前已知集合的数量
-
Java基于循环递归回溯实现八皇后问题算法示例
本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public
-
Java中递归、循环的优劣分析
介绍: 你用你手中的钥匙打开一扇门,结果去发现前方还有一扇门,紧接着你又用钥匙打开了这扇门,然后你又看到一扇门......但是当你开到一扇门时,发现前方是一堵墙无路可走了,你选择原路返回--这就是递归. 但是如果你打开一扇门后,同样发现前方也有一扇门,紧接着你又打开下一扇门.....但是却一直没有碰到尽头--这就是循环. 简单来说:循环是有去无回,而递归是有去有回(因为存在终止条件). 循环:当满足某一条件时反复执行某一操作(循环体). 递归:在一个方法内部对自身进行调用的方法. 递归结构包括两
-
Java求解两个非负整数最大公约数算法【循环法与递归法】
本文实例讲述了Java求解两个非负整数最大公约数算法.分享给大家供大家参考,具体如下: 代码功能: 1.Java实现(完整源码附测试用例): 2.求解两个非负整数p,q(p>=q)的最大公约数: 3.循环法 以及 递归法两种求解思路: 完整源码: /* GCD:Greateast Common Divisor */ public class GCD{ public static void main(String args[]){ /* Test Case */ int p = 32; int q
-
python如何求解两数的最大公约数
题目: 给定两个自然数,求这两个数的最大公约数. 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个. 但是这样做有几个缺点:一是做除法计算量比较大,二是遍历所有自然数完全没有必要.另外,如果能够循环,还是不要递归,因为Python的函数递归最大栈空间是1000(如果我没有记错的话),如果数字大一些,很容易出现爆栈. 所以在这里有两种处理方法: 1.如果较大的自然数除较小的一个自然数,取得余数,较小的自然数和余数的最大公约
-
Python实现的求解最大公约数算法示例
本文实例讲述了Python实现的求解最大公约数算法.分享给大家供大家参考,具体如下: 使用Python求解两个数的最大公约数的时候用到了前面介绍的分解质因式.其实,我写分解质因式程序的时候就是因为发现在实现最大公约数求解的过程中用到了这个功能. 比较令我开心的是之前学的一点Python集合处理功能居然在这个时候也派上了用场,小程序的完成让人感觉比较舒心. 代码实现如下: #!/usr/bin/python from collections import Counter def PrimeNum(
-
Java实现的两种常见简单查找算法示例【快速查找与二分查找】
本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng
-
JS求解两数之和算法详解
本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法 利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num
-
Java编程实现轨迹压缩之Douglas-Peucker算法详细代码
第一部分 问题描述 1.1 具体任务 本次作业任务是轨迹压缩,给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,所有记录的经纬度坐标构成一条轨迹,要求采用合适的压缩算法,使得压缩后轨迹的距离误差小于30m. 1.2 程序输入 本程序输入是一个GPS数据记录文件. 1.3 数据输出 输出形式是文件,包括三部分,压缩后点的ID序列及坐标.点的个数.平均距离误差.压缩率 第二部分 问题解答 根据问题描述,我们对问题进行求解,问题求解分为以下几步: 2.1 数据预处理 本次程序输入为GPS
-
Java 超详细讲解十大排序算法面试无忧
目录 排序算法的稳定性: 一.选择排序 二.冒泡排序 三.插入排序 四.希尔排序 五.堆排序 六.归并排序 七.快速排序 八.鸽巢排序 九.计数排序 十.基数排序 排序算法的稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,如果排序以后,保证这些记录的相对次序保持不变,即在原序列中,a[i]=a[j],且 a[i] 在 a[j] 之前,排序后保证 a[i] 仍在 a[j] 之前,则称这种排序算法是稳定的:否则称为不稳定的. 一.选择排序 每次从待排序的元素中选择最小的元素,依次
-
java 中冒泡、二分、快速算法详解
1.冒泡算法的原理: 冒泡排序算法的一般性策略:搜索整个值列,比较相邻元素,如果两者的相对次序不对,则交换它们,其结果是最大值"想水泡一样"移动到值列的最后一个位置上,这也是它在最终完成排序的值列中合适的位置.然后再次搜索值列,将第二大的值移动至倒数第二个位置上,重复该过程,直至将所有元素移动到正确的位置上. 下面是两个Java冒泡算法程序 2.冒泡代码如下: public class BubbleSort { public static void bubbleSort(int[] a
-
java 求解二维数组列最小值
java 求解二维数组列最小值 比较二维数组列最小值,组成一个新数组返回. 实现核心算法,不需要使用IO 输入:{{5,6,1,16},{7,3,9}} 输出:{1,3} import java.util.Arrays; public class Col { public static int[] getColMin(int a[][]) { int[] res = new int[a.length]; for (int i = 0; i < a.length; i++) { int[] s =
-
Java 选择排序、插入排序、希尔算法实例详解
1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu