用C++编写计算平方根的程序

Question

我正在编写一个C++程序来计算一个数字的平方根。这个程序不使用“sqrt”数学内置操作。有两个变量，一个是用户将要输入的数字，另一个是该数字的平方根。这个程序效果不是很好，我相信有更好的方法可以做到:

以下是我的完整代码:

#include <iostream>
using namespace std;

int main(){
  int squareroot = 0;
  int number;

  cout << "enter a number sp that i can calculate its squareroot" << endl;

  cin >> number;

  while (squareroot * squareroot != number){

      squareroot+=0.1;

}
cout << "the square root is" << squareroot << endl;
return 0;
 }

我知道一定有更好的方法。请帮忙，我在谷歌上搜索过，但由于我还是初学者，不理解那里复杂的程序。提前感谢。

- Aryan C

---

这不是一个编程问题，而是一个数学问题。有几种（高效和低效）算法可供选择。首先，您应该选择一种算法并深入研究，直到完全理解，然后尝试实现它。 - CompuChip

首先，你需要知道未初始化的本地变量（比如你的“squareroot”变量）具有不确定的值，使用它们会导致未定义的行为。其次，你声明squareroot为一个整数变量，你不能添加一个浮点数的值并期望它正常工作。 - Some programmer dude

请在不使用sqrt函数的情况下找到平方根。 - vishal

抱歉，我犯了一个错误，刚刚编辑了squareroot = 1;。 - Aryan C

Answer 1

以下是关于整数平方根计算的解释：

在数论中，正整数n的整数平方根是最大的整数m，满足m小于或等于n的平方根。

你开始的方法很好，但需要进行一些更正才能使其正常工作：

1. 你正在使用int类型，想要将1添加到squareroot而不是0.1。 2. 当squareroot * squareroot大于或等于number时，你希望停止计算。考虑数字为26的情况，你没有一个整数可以相乘得到26。 3. 对于数字等于26的情况，你想返回5还是6？在while循环之后，squareroot的值将为6，因此如果squareroot * squareroot与number不同，你可能想将其反转为5。

以下是示例：

#include <iostream>
using namespace std;

int main(){
  int squareroot = 0;
  int number;

  cout << "enter a number sp that i can calculate its squareroot" << endl;

  cin >> number;

  while (squareroot * squareroot < number){
      squareroot+=1;
  }

  if (squareroot * squareroot != number) --squareroot;

  cout << "the square root is" << squareroot << endl;
  return 0;
}

以下是一种更为高效、优雅的二分查找求平方根的方法。 O(log(n))

int mySqrt(int x) {
    if (x==0) return 0;
    int left = 1;
    int right = x/2 + 1;
    int res;

    while (left <= right) {
        int mid = left + ((right-left)/2);
        if (mid<=x/mid){
            left = mid+1;
            res=mid;
        }
        else {
            right=mid-1;
        }
    }

    return res;
}

- Jérôme

---

我认为仅仅给出问题的解决方案并不能真正地帮助到提问者。或许更好的方式是指出他们代码存在的问题，并指引他们如何进行修改？ - default

但结果不一定是整数。 - user1095108

@user1095108，你说得对，上面的解释仅适用于整数平方根计算。 - Jérôme

谢谢回复。 - Aryan C

@Aryan.C 不客气！如果这个回答有帮助，请接受它。谢谢。 - Jérôme

你可以直接使用 return left - 1;，而不需要引入 res 变量。 - QtRoS

Answer 2

此函数使用嵌套区间（未经测试），您可以定义精度：

#include <math.h>
#include <stdio.h>

double mySqrt(double r) {
  double l=0, m;
  do {
     m = (l+r)/2;
     if (m*m<2) {
        l = m;
     } else {
        r = m;
     }
  } 
  while(fabs(m*m-2) > 1e-10);      
  return m;
}

请参见嵌套区间

- zwergmaster

---

我认为仅仅给出解决方案并不真正帮助提问者。也许更好的方法是指出他们的代码为什么不能工作，然后指导他们如何改变它？ - default

如所写，这只输出1.41421，即 sqrt(2)。如果你改变(m*m<2)和(m*m-2)不再固定在2上，而是使用r和你的原始输入来检查delta，那么它几乎就是一个二分查找。 - Alex Moore-Niemi

Answer 3

如果A不是完全平方数，此函数将计算其平方根的底部。该函数基本上使用二分查找。您事先知道的两件事是，一个数字的平方根将小于或等于该数字，并且它将大于或等于1。因此，我们可以在该范围内应用二进制搜索。以下是我的实现。如果您不理解代码中的任何内容，请告诉我。希望这有所帮助。

int sqrt(int A) {
    if(A<1)return 0;
    if(A==1)return 1;

    unsigned long long start,end,mid,i,val,lval;
    start = 1;
    end = A;
    while(start<=end){
        mid = start+(end-start)/2;
        val = mid*mid;
        lval = (mid-1)*(mid-1);

        if(val == A)return mid;     
        else if(A>lval && A<val) return mid-1;
        else if(val > A)end = mid;
        else if(val < A)start = mid+1;
    }
}

- Khatri

---

我认为仅仅给提问者一个解决方案并不能真正地帮助他们。也许更好的方法是指出他们的代码为什么不起作用，然后指引他们如何修正它？ - default

是的，你说得完全正确，但问题是在寻找可能更好的方法，这就是为什么我建议更好的方法。我认为了解不同的方法并没有什么坏处。也许我不应该发布代码，只是建议使用方法。 - Khatri

Answer 4

你的代码问题在于，它只能在数字的平方根恰好为N*0.1（其中N是整数）时才能正常工作，这意味着如果答案是1.4142而不是1.400000000，你的代码将失败。有更好的方法，但它们都更加复杂，并使用数值分析来逼近答案，其中最简单的是牛顿-拉夫森方法。

你可以使用下面的函数，该函数使用牛顿-拉夫森方法查找根，如果您需要更多关于牛顿-拉夫森方法的信息，请查看this维基百科文章。如果您需要更高的精度-但性能较差-可以将'0.001'减小到您喜欢的程度，或者增加它以获得更好的性能但精度较低。

float mysqrt(float num)   {  
    float x = 1;

    while(abs(x*x - num) >= 0.001 )
        x = ((num/x) + x) / 2;

    return x;

}  

如果您不想导入math.h，您可以编写自己的abs()函数：

float abs(float f) {
    if(f < 0)
        f = -1*f;
    return f;
}

- hassan arafat

Answer 5

如果一个数字是完全平方数，求它的平方根。

复杂度为log(n)。

/**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */
public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}

- Sajjad Ali Vayani

Answer 6

#include <iostream>
using namespace std;
int main()
{
    double x = 1, average, s, r;
    cout << "Squareroot a Number: ";
    cin >> s;
    r = s * 2;
    for ( ; ; ) //for ; ; ; is to run the code forever until it breaks
    {
        average = (x + s / x) / 2;
        if (x == average)
        {
            cout << "Answer is : " << average << endl;
            return 0;
        }
        x = average;
    }
}

你可以试试我的代码 :D 我在这里使用的方法是巴比伦平方根法，你可以在这里找到它 https://en.wikipedia.org/wiki/Methods_of_computing_square_roots。

- Donald Xu