判断一个自然数是否是某个数的平方，不能使用开方运算 |
您所在的位置：网站首页 › 1681是哪个数的平方 › 判断一个自然数是否是某个数的平方，不能使用开方运算 |
|
方法1： 遍历从1到N的数字，求取平方并和N进行比较。 如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。 复杂度为O(n^0.5)。 // 方法1：遍历从1到N的数字，求取平方并和N进行比较。复杂度为O(n^0.5)。 public static boolean isSquare1(int num) { if (num == 0 || num == 1) { return true; } for (int i = 2; i < num / 2; i++) { if (i * i == num) { return true; } else { if (i * i > num) { return false; } } } return false; }方法2： 使用二分查找法，对1到N之间的数字进行判断。 复杂度为O(log n)。 // 方法2：使用二分查找法，对1到N之间的数字进行判断。复杂度为O(log n)。 public static boolean isSquare2(int num) { if (num == 0 || num == 1) { return true; } int mid = 0; int left = 0; int right = num / 2; while (left < right) { mid = left + (right - left) / 2; if (mid * mid == num) { return true; } else { if (mid * mid > num) { right--; } else { left++; } } } return false; }方法3： 由于 (n+1)^2 =n^2 + 2n + 1， = ... = 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1) 注意到这些项构成了等差数列（每项之间相差2）。 由于N = 1 + (2 + 1) + ( 4 + 1) + ( 6 + 1) + .... 所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的关系。 如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。 复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。 // 方法3：复杂度为O(n^0.5)。方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。 public static boolean isSquare3(int num) { int temp = 1; for (int i = 1; i < num; i++) { num -= temp; if (num < 0) return false; else if (num == 0) { return true; } temp += 2; } return false; }测试成绩 public static void main(String[] args) { int num = 10000; int sqrt = (int) Math.pow(num, 0.5); System.out.println(sqrt * sqrt == num); System.out.println(isSquare1(num)); System.out.println(isSquare2(num)); }
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |