C++中sqrt()函数的问题

fdbelqdn  于 2022-12-27  发布在  其他
关注(0)|答案(3)|浏览(274)

我用C++编写代码,这需要一个中间步骤来检查一个数是否是正方形。我写了下面的代码。

int sqrt_of_t = (int)sqrt(t);
if (sqrt_of_t*sqrt_of_t != t)
{
    cout << "NO" << endl;
}

这段代码在我的系统中给出了正确的结果,但是当它通过Codeforce中的在线判断时失败了。它失败的情况并没有任何溢出或任何相关的东西(非常小的测试用例)。那么,有没有人能解释一下哪里出了问题,并提出一些替代方法来检查一个数字是否是完美的正方形,它可以在所有系统上工作,不会显示这样的行为,这里t也是一个int。

g52tjvyc

g52tjvyc1#

sqrt()返回一个浮点数,您可以将其转换为int,它会截断任何小数部分。问题是浮点数不能精确地表示所有整数,因此您可能会得到类似19.9999999999999的结果,您期望它是20,但当转换为整数时实际上是19。
要修复此问题,请改用舍入:

long sqrt_of_t = lrint(sqrt(t));
watbbzwu

watbbzwu2#

sqrt,在许多系统上返回近似值。
例如,sqrt(25)可能返回类似于4.99999999的值。
因此,4.99999999 * 4.99999999略小于25。
我的建议是在数字空间中做一个二进制搜索,看看这个数字是否是一个完美的平方。当你需要精确的结果时,避免使用浮点。

bool isPerfectSquare(long long t)
{
    bool result = false;
    if ((t == 0) || (t == 1)) {
        return true;
    }
    if (t < 0) {
        return false;
    }

    long long low = 1;
    long long high = t / 2;

    while (low < high)
    {
        auto mid = (high + low) / 2;
        auto sq = mid * mid;
        if (sq == t) {
            result = true;
            break;
        }
        if (sq < t) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return result;
}
webghufk

webghufk3#

这是Knuth非常有趣的算法,只需要移位和加法就可以计算整数平方根。它对非平方输入进行四舍五入。

uint32_t isqrt1(uint32_t x) {
  uint32_t r = 0, r2 = 0; 
  for (int p = 15; p >= 0; --p) {
    uint32_t tr2 = r2 + (r << (p + 1)) + (1u << (p << 1));
    if (tr2 <= x) {
      r2 = tr2;
      r |= (1u << p);
    }
  }
  return r;
}

这个方法是将每一位设置为1,从高到低,保持到目前为止计算出的预期根的平方。如果每一位产生的平方不大于输入值,那么它就被“或“到结果中。它可以被修改以检测预期是精确平方的情况。

bool is_exact_square(uint32_t x) {
  if (x == 0) return true;
  uint32_t r = 0, r2 = 0; 
  for (int p = 15; p >= 0; --p) {
    uint32_t tr2 = r2 + (r << (p + 1)) + (1u << (p << 1));
    if (tr2 == x) return true;
    if (tr2 < x) {
      r2 = tr2;
      r |= (1u << p);
    }
  }
  return false;
}

我是为了大家的兴趣而添加的。二进制搜索的建议很好。也许更好,除非你在一台没有快速乘法的机器上工作。

相关问题