精华内容
下载资源
问答
  • //用递归方法求最小公倍数 public static int zxgbs(int x,int y){ if(x>=y){ if(x==y){ return x; }else{ if(x%y==0){ return y; }else{ return zxgbs(y,x%y); } } }else...

    public class Test {

    public static void main(String[] args) {
    //测试下
    int zxgbs = zxgbs(32,112);
    System.out.println(zxgbs);
    int zdgys = zdgys(112,32);
    System.out.println(zdgys);
    }

    //用递归方法求最小公倍数
    public static int zxgbs(int x,int y){
    if(x>=y){
    if(x==y){
    return x;
    }else{
    if(x%y==0){
    return y;
    }else{
    return zxgbs(y,x%y);
    }
    }
    }else{
    //两数交换
    x=x^y;
    y=x^y;
    x=x^y;
    return zxgbs(x,y);
    }
    }

    //调用最小公倍数的方法间接求得最大公约数
    public static int zdgys(int x,int y){
    int zdgys = (x/zxgbs(x, y))*(y/zxgbs(x, y))*zxgbs(x, y);
    return zdgys;
    }

    }
    展开全文
  • 主要介绍了Python基于递归算法求最小公倍数和最大公约数,结合实例形式分析了Python使用递归算法进行数值计算的相关操作技巧,需要的朋友可以参考下
  • 最近做题目发现一些题目需要求数的最大公约数和最小公倍数,想想最大公约数和最小公倍数平时做数学的时候感觉不是很难,但是突然要编程来实现,却一下子不知所措了,后来看了下别人写的,发现其实也不算特别难。最小...

    最近做题目发现一些题目需要求数的最大公约数和最小公倍数,想想最大公约数和最小公倍数平时做数学的时候感觉不是很难,但是突然要编程来实现,却一下子不知所措了,后来看了下别人写的,发现其实也不算特别难。最小公倍数其实只要一个公式,即整数A和整数B的最小公倍数为A*B/gcd(A,B)(gcd(A,B)为A和B的最大公约数),可见A和B的最小公倍数就为A和B的乘积再除以它俩的最大公约数,也就是说最终还是要求最大公约数,所以以下主要讨论最大公约数算法。最大公约数的算法原来还分为两种,一种是用非递归的算法,一种是递归的算法。递归的算法在二叉树里面是很常见的,以及斐波那契数列的实现上,对于递归算法的优点就是代码可以极其简短,缺点则是需要不断调用函数,效率不用直接用循环。

    无论是通过递归还是非递归的方法,一下的代码都是基于一种求两个数最大公约数的算法——辗转相除法。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 / 105 = 2余42,所以105和42的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。

    以下是求最大公约数递归算法

    //最大公约数(递归算法)
    int gcd( int x , int y){
    	if( y == 0 )
    		return x;
    	else
    		return gcd(y,x%y);
    }
    从上面可以看出,递归算法极其简短,而下面的非递归算法相对则长一点。

    //最大公约数(非递归算法)
    int gcd( int x , int y){
    	int max,min,temp;
    	max = x > y ? x : y ;
    	min = x < y ? x : y ;
    	while( max % min ){
    
    		temp = max % min;
    		max = min;
    		min = temp;
    	}
    	return min;
    }
    //最小公倍数
    int lcm( int x , int y ){
    	return x*y/gcd(x,y);
    }
    

    展开全文
  • 数组所有数据的最小公倍数,可以先将问题简化为两个正整数的最小公倍数,再通过递归或数组累加器来出最后结果。 而两个正整数a,b的最小公倍数c,可先出最大公约数d,则最小公倍数就显而易见c=...

    任务:求数组arr[]中所有数据的最小公倍数。

    任务解析:

            求数组所有数据的最小公倍数,可以先将问题简化为求两个正整数的最小公倍数,再通过递归或数组累加器来求出最后结果。

            而求两个正整数a,b的最小公倍数c,可先求出最大公约数d,则最小公倍数就显而易见c=a*b/d;

           求最大公约数的方法参见:https://my.oschina.net/flyyourdream/blog/867327

    JS算法实现:

    //算法:利用最大公约数求两整数的最小公倍数
    function twoSmallestCommonMultiple(a,b){
      var c=mostCommonDivisor(a,b);
      return a*b/c;
    }
    //算法:辗转相减法求两个整数的最大公约数
    function mostCommonDivisor(a,b){
    	var c=Math.min(a,b);
    		a=Math.max(a,b);
    		b=c;
    	if(b===0){
    		return  alert("error,please input a number bigger than zero");
    	}
    	var c=a-b;
    	while(c>0){
    		a=Math.max(b,c);
    		b=Math.min(b,c);
    		c=a-b;
    	}
    	return b;
    } 
    //使用函数调用和递推的方式求数组所有元素的最小公倍数
    function smallestCommonMultiple(arr){
    	if(arr.length<2){
    		return arr[0];
    	}
    	var a=0;
    	var result=1;
    	for(var i=0;i<arr.length;i++){
    		result=twoSmallestCommonMultiple(result,arr[i]);
    	}
    	return result;
    }

          上述smallestCommonMultiple(arr),也可以使用Arr.prototype.reduce()累加器进行计算,具体实现方式如下:

    function smallestCommonMultiple(arr){
    	if(arr.length<2){
    		return arr[0];
    	}
    	var a=0;
    	var result=arr.reduce(function(acc,val){
    		return twoSmallestCommonMultiple(acc,val);
    	},1);
    	return result;
    }

          

           

        

     

     

    转载于:https://my.oschina.net/flyyourdream/blog/867338

    展开全文
  • 欧几里得递归算法求最大公约数和最小公倍数 代码: 最大公约数: int gys(int a,int b) { if(a%b==0) return b; else return gys(b,a%b); } 最小公倍数(需要用到最大公约数的代码): int gbs(int a,int b) ...

    欧几里得递归算法求最大公约数和最小公倍数

    代码:

    最大公约数:

    int gys(int a,int b)
    {
    	if(a%b==0)
    		return b;
    	else return gys(b,a%b);
     }
    

    最小公倍数(需要用到最大公约数的代码):

    int gbs(int a,int b)
     {
     	return a*b/gys(a,b);
      } 
    

    例题:
    核桃的数量

    资源限制
    时间限制:1.0s 内存限制:256.0MB
    问题描述
    小张是软件项目经理,他带领3个开发组。工期紧,今天都在加班呢。为鼓舞士气,小张打算给每个组发一袋核桃(据传言能补脑)。他的要求是:

    1. 各组的核桃数量必须相同

    2. 各组内必须能平分核桃(当然是不能打碎的)

    3. 尽量提供满足1,2条件的最小数量(节约闹革命嘛)

    输入格式
    输入包含三个正整数a, b, c,表示每个组正在加班的人数,用空格分开(a,b,c<30)
    输出格式
    输出一个正整数,表示每袋核桃的数量。
    样例输入1
    2 4 5
    样例输出1
    20
    样例输入2
    3 1 1
    样例输出2
    3

    代码实现:

    #include<bits/stdc++.h>
    using namespace std;
    int gys(int a,int b)
    {
    	if(a%b==0)
    		return b;
    	else return gys(b,a%b);
     }
     int gbs(int a,int b)
     {
     	return a*b/gys(a,b);
      } 
    int main()
    {
    	int a,b,c;
    	cin>>a>>b>>c;
    	cout<<gbs(gbs(a,b),c)<<endl;
    } 
    
    展开全文
  • 主要介绍了Python基于递归和非递归算法求两个数最大公约数、最小公倍数,涉及Python递归算法、流程循环控制进行数值运算相关操作技巧,需要的朋友可以参考下
  • 使用scala语言求解两个数的最大公约数和最小公倍数最大公约数 //欧几里得算法递归方式) def gcdLoop(a:Long,b:Long): Long ={ var x=a var y=b while(y!=0){ val tmp=x%y x=y y=tmp } x  } //(非递归...
  • 最小公倍数算法分析

    万次阅读 多人点赞 2019-03-09 14:26:08
    一、实验内容 运行最大公约数的常用算法,并进行程序的调式与测试,要求程序设计...根据这一定理可以采用函数嵌套调用和递归调用形式进行两个数的最大公约数和最小公倍数,现分别叙述如下 // 非递归实现: public ...
  • 两个或多个整数公有的倍数叫做它们的公倍数。 两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。直接贴出两个正数的最小公倍数法,这是我在大学学习java的时候的想法,虽然性能不好,但还是可以实现的.
  • HJ108:求最小公倍数

    2020-08-08 12:25:06
    题目描述: 正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的最小公倍数。... * 求最小公倍数:公式法 * 两个数a,b的最小公倍数是a*b/gcd(a,b) * 由于两个数的乘积等
  • 两个数的最小公倍数和最大公约数") def gys(a, b):  tmp = max(a, b) % min(a, b)  if tmp == 0:  return min(a, b)  else:  return gys(tmp,min(a,b)) num1 = int(input("输入数字一")) num2...
  • 最大公约数及最大公倍数 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num1 = sc.nextInt(); int num2 = sc.nextInt(); ...
  • 问题:用递归实现求最大公约数和最小公数的算法 代码如下: //递归实现求最大公约数 //递归求最大公数 int g(int num1,int num2) { int r; r = num1%num2; if( r == 0 )//递归结束条件 return num2; g...
  • 最大公约数和最小公倍数算法

    万次阅读 2009-12-25 13:39:00
    先用辗转相除法出最大公约数,然后再利用(最小公倍数=两数乘积/最大公约数)求得最小公倍数。辗转相除算法: //非递归算法int gcd(int a, int b) { int temp; if(a ) //swap(a,b) 交换a和b { temp=b; b=a; a=...
  • 包含了:1.辗转相除法函数嵌套流程图2.辗转相除法函数递归流程图3.穷举法求最小公倍数流程图4.穷举法求最大公约数流程图5.更相减损术流程图
  • 1.最大公约数 最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。最大公约数的常用方法为辗转相除法。...2.最小公倍数 两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外...
  • 递归算法就是指一个方法直接或间接地自己调用自己的过程,那么为完成这个计算任务,我们需要定义一个用于取最大公约数和最小公倍数的方法,并定义一个完成输入、输出以及调用方法的主函数。 ...
  • 而对于两个正整数的最小公倍数呢,有这样一个定理: 对于两个正整数 a 和 b,有gcd(a, b) * lcm(a, b) == a * b。 下面看具体的实现代码: /* * 求解最大公约数(递归实现) */ public static int gcd...
  • 递归实现两个正整数的最大公约数与最小公倍数递归:方法定义中调用方法本身的现象 注意事项:1、递归一定要有出口,否则此递归就是一个死递归 2、递归的次数不能太多,否则会内存溢出 3、构造方法不能使用...
  • #include "stdio.h" int gys(int a,int b)//最大公约数,递归 { if(a%b==0) return b;...int main(){//求最小公倍数 int a,b; while(scanf("%d%d",&a,&b)!=EOF){ int t; if(a<b){//让a>...
  • Java最大公约数和最小公倍数

    千次阅读 多人点赞 2019-03-19 12:01:47
    * 算法思想:(非递归)最大公约数和最小公倍数 * 最大公约数:for循环从二者最小的数到1遍历,能共同 被整除的最大整数即为最大公约数 * 最小公倍数:最大公约数*两个数与最大公约数的商 */ public class Main { ...
  • 编写一函数lcm,两个正整数的最小公倍数。 样例输入 一个满足题目要求的输入范例。 例: 3 5 样例输出 与上面的样例输入对应的输出。 例: 数据规模和约定  输入数据中每一个数的范围。  例:两个数都小于65536...
  • 1. /** 2. * 冒泡排序算法 3. */ 4. public class BubbleSort { 5. public static void sort(int[] values) { 6. int temp; 7. for (int i = 0; i 8.

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 175
精华内容 70
关键字:

递归求最小公倍数算法