C++完全平方数的实现代码 |21xrx.com

C++完全平方数的实现代码

2023-07-04 19:52:17 深夜i -- --

C++ 完全平方数实现代码

在C++中，完全平方数是一个平方数（即它可以表示为某个整数的平方），例如1、4、9、16、25等。在实际的程序开发工作中，我们有时需要判断一个数是否是完全平方数。本文将介绍如何使用C++实现完全平方数的判断功能。

方法一：暴力枚举

最简单的方法是使用暴力枚举。在这种方法中，我们可以使用一个循环来枚举所有可能的平方数，然后判断目标数是否等于其中的一个平方数。

下面是使用暴力枚举实现完全平方数判断功能的代码：


bool isPerfectSquare(int num) {
  for (long long i = 0; i <= num; i++) {
    if (i * i == num)
      return true;
     else if (i * i > num)
      break;
    
  }
  return false;
}

在上面的代码中，我们使用了一个long long类型的循环变量i，以防止i * i溢出。如果目标数是一个完全平方数，那么循环将会在某个位置被break语句打断，从而返回true；否则，循环结束后返回false。

方法二：二分查找

暴力枚举方法的效率不高，因为需要枚举所有可能的平方数。事实上，我们可以使用一个更快的算法，即二分查找。这种方法可以将判断一个数是否为完全平方数的时间复杂度从O(n)降为O(log n)。

下面是使用二分查找实现完全平方数判断功能的代码：


bool isPerfectSquare(int num) {
  long long left = 0;
  long long right = num;
  while (left <= right) {
    long long mid = (left + right) / 2;
    long long square = mid * mid;
    if (square == num)
      return true;
     else if (square > num)
      right = mid - 1;
     else {
      left = mid + 1;
    }
  }
  return false;
}

在上面的代码中，我们使用了一个左右指针来表示当前的搜索区间。在每次迭代中，我们计算左右指针的中间值mid，并计算mid的平方。如果mid的平方等于目标数，就直接返回true；否则，根据mid的平方与目标数的大小关系调整左右指针的位置。最后，如果找不到任何一个完全平方数，函数将返回false。

上一篇: idea打包java可执行jar包

下一篇: 如何增大C++代码字体

评论区

()

相似文章