最大公约数 (四种解法) 和最小公倍数 (两种解法) |
您所在的位置：网站首页 › 三十二十二和十六的最小公倍数 › 最大公约数 (四种解法) 和最小公倍数 (两种解法) |
|
求两个数的原理： 最大公约数： x%gcd==0 && y%gcd==0 最小公倍数： lcm%x==0 && lcm%y==0 一.最大公约数 1.穷举法采用循环暴力解决，比较简单 int gcd(int x,int y) { if (x == 0) return y; else if (y == 0) return x; else if (x == y) return x; int min = x > y ? y : x; //找出两个的最小值 while (min) { if (x % min == 0 && y % min == 0) return min; min--; } } 2.相减法对上面穷举法的优化，提高效率 int gcd(int x, int y) { if (x == 0) return y; else if (y == 0) return x; else if (x == y) return x; int n; //存差值的变量 while (x != y) { n= x > y ? (x -= y) : (y -= x); } return n; } 3.辗转相除法效率更高的一种方法，使用一些数学知识 int gcd(int x, int y) { if (x == 0) return y; else if (y == 0) return x; else if (x == y) return x; int mod=x%y; while (mod) { x = y; y = mod; mod = x % y; } return y; } 4.递归做法这是最好的方法，是辗转相除法的进阶，用的是辗转相除法的原理，但更加简洁高效 int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); }看，是不是简洁了很大，但其实还可以更简洁 int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }以后写最大公约数的代码采用上面这个代码就行了，太妙了^-^ 二.最小公倍数 1.穷举法根据原理暴力求解，不断循环 int lcm(int x, int y) { if (x * y == 0) return 0; int max = x > y ? x : y; //找到两个值的最大值 while (max) { if (max % x == 0 && max % y == 0) return max; max++; } } 2.公式法两个数的乘积等于最大公约数乘以最小公倍数。所以说公式法要用到上面求的最大公约数，函数也相对简单些 int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } int lcm(int x, int y) { if (x * y == 0) return 0; return (x * y) / gcd(x, y); }---------------------------------------------------------------------------------------------------------------------------------总结：两个数都可以采用循环暴力直接解决，但效率较低，当数字比较特殊时，处理的时间较长。 巧解效率高，代码相对简洁，应该着力去记住。 谢谢大家！ ^-^ |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |