基础算法 |
您所在的位置：网站首页 › 辗转相除法求最大公约数程序 › 基础算法 |
|
题目背景
约数
如果数 a 能被数 b 整除，a 就叫做 b 的倍数，b 就叫做 a 的约数。 最大公约数最大公约数就是两个数中,大家都能相约且最大的数。 辗转相除法辗转相除法又名欧几里得算法（Euclidean algorithm）,目的是求出两个正整数的最大公约数。它是已知最古老的算法,其可追溯至公元前300年前。 这条算法基于一个定理：两个正整数 a 和 b（a 大于 b）,它们的最大公约数等于 a 除以 b 的余数 c 和 较小数 b 之间的最大公约数。 算法计算过程是这样的: 2个数相除，得出余数如果余数不为0，则拿较小的数与余数继续相除，判断新的余数是否为0如果余数为0，则最大公约数就是本次相除中较小的数。比如数字 25 和 10 ，使用辗转相除法求最大公约数过程如下： 25 除以 10 商 2 余 5根据辗转相除法可以得出，25 和 10 的最大公约数等于 5 和 10 之间的最大公约数10 除以 5 商 2 余 0， 所以 5 和 10 之间的最大公约数为 5，因此25 和 10 的最大公约数为 5 题目要求完善函数 gcd 的功能。函数 gcd 会计算并返回传入的两个正整数参数之间最大的公约数 如下所示： gcd(30，3); // 返回结果为 3 gcd(12, 24); // 返回结果为 12 gcd(111, 11); // 返回结果为 1function gcd(num1,num2){ var remainder = 0; do{ remainder = num1 % num2; num1 = num2; num2 = remainder; }while(remainder!==0); return num1; } console.log(gcd(24,12));
实现辗转相除法通常有两种思路，分别如下 1、使用循环实现 function gcd(number1, number2){ // 创建一个表示余数的变量 var remainder = 0; // 通过循环计算 do { // 更新当前余数 remainder = number1 % number2; // 更新数字1 number1 = number2; // 更新数字1 number2 = remainder; } while(remainder !== 0); return number1; } 2、使用函数递归 function gcd(number1, number2) { if (number2 == 0) { return number1; } else { return gcd(number2, number1 % number2); } }
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |