本文实例讲述了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程序设计有所帮助。
本文向大家介绍Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例,包括了Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python基于递归和非递归算法求两个数最大公约数、最小公倍数。分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了
Python3 实例 以下代码用于实现最大公约数算法: 实例(Python 3.0+)# Filename : test.py # author by : www.runoob.com # 定义一个函数 def hcf(x, y): """该函数返回两个数的最大公约数""" # 获取最小值 if x > y: smaller = y else: smaller = x for i in range
本文向大家介绍java求最大公约数与最小公倍数的方法示例,包括了java求最大公约数与最小公倍数的方法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了java求最大公约数与最小公倍数的方法。分享给大家供大家参考,具体如下: Gongyueshu.java文件: 此处需要由控制台输入参数,eclipse环境运行的设置步骤为Run》Run Configurations进入运行的调试配置界面
我是新来这个网站的,希望在这里玩得开心。我现在正在做一个作业,现在我被困在第一个问题上,程序要求两个整数来计算和显示最大公约数(GCD)。 根据问题: 计算GCD的经典算法,称为欧几里德算法,如下所示:设m和n为包含这两个数字的变量。如果n为0,则停止;m包含GCD。否则,当m除以n时,计算余数。将n复制到m中,并将余数复制到n中。然后重复该过程,从测试n是否为0开始。 有了这个提示,我决定按如下
我正在做一些自学的Java,但似乎无法解决这个循环中的问题: 问题是找到两个整数n1和n2的最大公约数,其中d是较小的值。方法是递减d直到GCD或它达到1。。。以下是我目前的情况: 有什么指示吗?
本文向大家介绍python如何求解两数的最大公约数,包括了python如何求解两数的最大公约数的使用技巧和注意事项,需要的朋友参考一下 题目: 给定两个自然数,求这两个数的最大公约数。 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个。 但是这样做有几个缺点:一是做除法计算量比较大,二是遍历所有自然数完全没有必要。另外,如