[Intermediate Algorithm] - Smallest Common Multiple
2024-09-07 21:04:33
题目
找出能被两个给定参数和它们之间的连续数字整除的最小公倍数。
范围是两个数字构成的数组,两个数字不一定按数字顺序排序。
例如对 1 和 3 —— 找出能被 1 和 3 和它们之间所有数字整除的最小公倍数。
测试用例
smallestCommons([1, 5])
应该返回一个数字。smallestCommons([1, 5])
应该返回 60。smallestCommons([5, 1])
应该返回 60。smallestCommons([1, 13])
应该返回 360360。
分析思路
最小公倍数 = 两数相乘 / 最大公约数;
所以第一步是求两数的最大公约数。
代码
1.function greatestCommonDivisor(num1, num2) {
2. var retVal = 1;
3.
4. for (var i = 2; i <= Math.min(num1, num2); i++) {
5. if (num1 % i === 0 && num2 % i === 0) {
6. retVal = i;
7. }
8. }
9. return retVal;
10.}
11.
12.function smallestCommons(arr) {
13. var retVal = 1;
14.
15. for (var i = Math.min(arr[0], arr[1]); i <= Math.max(arr[0], arr[1]); i++) {
16. retVal = Math.floor(retVal * i / greatestCommonDivisor(retVal, i));
17. }
18.
19. return retVal;
20.}
21.
22.smallestCommons([1,5]);
在网上搜到一段经典的最大公倍数的版本:
注意:
这里涉及到经典算法:求最大公约数gcd(greatest common divisor)
和最小公倍数scm(smallest common multiple)
gcd
(最大公约数)算法过程(欧几里德算法/辗转相除法)
有两整数a和b:
① a%b得余数c,即c=a%b
② 若c=0,则b即为两数的最大公约数
③ 若c≠0,则a=b,b=c,再回去执行①
scm算法(最小公倍数算法)
最小公倍数=两整数的乘积÷最大公约数,即scm=sqrt(a*b)/gcd(a,b)1.//求val1和val2的最大公约数(greatest common divisor)
2.//欧几里德算法(辗转相除法)
3.function gcd(val1,val2){
4. if(val1%val2===0)
5. return val2;
6. else
7. return gcd(val2,val1%val2);
8.}
9.
10.function smallestCommons(arr) {
11. //将arr按升序排序
12. arr=arr.sort(function(a,b){
13. return a-b;
14. });
15. //求a和b的最小公倍数scm(smallest common multiple)
16. //scm=abs(a*b)/gcd(a,b)
17. var val=arr[0];
18. //这里求多个数的最小公倍数:先求出两个数的scm1,再求scm1与第三个数的scm2……依次循环
19. for(var i=arr[0]+1;i<=arr[1];i++){
20. val *=i/gcd(val,i);
21. }
22. return val;
23.}
24.
25.smallestCommons([1,5]);
最新文章
- Android随笔之——Android ADB详解
- Linux内核创建一个新进程
- 【Log4j2 配置详解】log4j2的资源文件具体怎么配置
- PL/SQL 听课笔记
- LayoutInflater和inflate()方法的用法
- 经典排序算法(Java版)
- [未完成]关于java基础数据类型中的一些总结
- 3DS MAX 导出FBX到Unity3D设置
- 在.NET MVC下不用iframe实现局部加载html
- C#操作Excel(读/写)
- Java中判断字符串中相同字符的个数
- sed命令基础
- swift之函数式编程(二)
- 黑盒测试实践——day06
- Android为TV端助力 http下载视频到指定目录
- hdu1878-并查集,欧拉回路
- 代码编辑器 - Visual Studio Code
- junit断言和junit注释assert
- mysql 案例 ~查询导致的tmp临时文件问题
- 2.2.11同步synchronized方法无限等待与解决
热门文章
- HDU 2268 How To Use The Car (数学题)
- [NOIP2018模拟赛]d
- linux文件的特殊权限及隐藏权限
- Linux 下的基本命令
- Python实现8中常用排序算法
- NumPy常见的元素操作函数
- WOJ 1538 B - Stones II
- c++0x11新特性:delete删除函数
- Optimization on content service with local search in cloud of clouds
- [bzoj3943][Usaco2015 Feb]SuperBull_Kruskal