求最大公约数 深碍√TFBOYSˉ_ 2023-01-04 10:30 134阅读 0赞 `迭代版本` function getCd(a, b) { if (a * b < 0) return 1 if (a ==0 || b == 0) return 0 while( a % b != 0 ){ var c = a % b; a = b; b = c; } return b } `递归版本` function getCd(a, b) { if (a == 0 || b == 0) return 0 if (a * b < 0) return 1 if( a % b ==0 ) { return b; //如果b能被a整除则b就是最大公约数 } else { return getCd(b, a % b); } } tip: 求多个数的最大公约数,只需要一次线性遍历即可,不用O(n^2)的时间复杂度 var getGroupsCd = (arr) => { if (!arr || arr.length < 1) return null if (arr.length === 1) return arr[0] let init = getCd(arr[0], arr[1]) for (let i = 2; i < arr.length; i++) { init = getCd(init, arr[i]) } return init }
还没有评论,来说两句吧...