检查一个数是否是C中的完全平方

mlmc2os5  于 2023-10-15  发布在  其他
关注(0)|答案(2)|浏览(136)

任务:

在一个无符号long long类型的N个元素(N < 20)的数组中,找到最大的满平方并打印其索引(从零开始)。如果没有完整的正方形,则打印-1。如果有一个以上的最大平方,打印第一个的索引。
输入数据:标准输入流,其中N是写在第一行第二行的数组元素中的一个空格。
输出数据:标准输出流中的数字

验证码:

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

int main() {
  
    unsigned short int n;
    unsigned long long mass[20];
    unsigned long long max = 0;
    int max_index = -1;
    
    scanf("%hu", &n);

    if (n >= 20) {

      do{
        
        scanf("%hu", &n);
        
      }while(n >= 20);
      
    }

    for (int i = 0; i < n; i++) {
        scanf("%llu", &mass[i]);

        long double root = (long double) sqrt(mass[i]);
        if (root * root == mass[i]) {

            if (mass[i] > max) {
                max = mass[i];
                max_index = i;
            }
        }
    }
    
    printf("%d\n", max_index);
    
    return 0;
}

编译时出现此错误
Error
我尝试使用不同类型的数据,但都没用。

vcirk6k6

vcirk6k61#

至少这些问题:

编译器错误

当C编译器应该用于C代码时,错误消息指示OP正在使用C编译器。函数重载(C的一部分)不是C的标准特性。

精度损失

sqrt(mass[i])可能会丢失精度。unsigned long long至少是一个64位类型,将其转换为double(以预形成平方根)可能会丢失所需的精度。浮点数学也引入了舍入问题,这可能导致此整数问题的错误结果。对于整数问题,最好使用整数数学而不是浮点数学。
类似于root * root == mass[i]的问题
考虑形成一个unsigned long long isqrt_ull(unsigned long long x)来找到平方根。
样品名称:

// Recursive version.
unsigned long long isqrt_ull(unsigned long long x) {
  if (x < 2) {
    return x;
  }
  unsigned long long s = isqrt_ull(x >> 2) << 1;
  unsigned long long t = s + 1;
  return (t > x / t) ? s : t;
}

**角箱:联系我们

如果数组的值都是0,则代码报告-1为mass[i] > max永远不会为true。最好是mass[i] > max || max_index == -1
其他次要问题

  • 不需要测试一个新的候选完美平方,除非它大于先验最大值。
  • 避免类型增殖:在本学员练习中,使用int阅读数组大小。
  • 检查scanf()的返回值以了解输入是否成功。
  • isqrt_ull()不是一个高效的整数平方根例程。它只是作为一个简单的占位符,没有浮点问题,但处理unsigned long long
vsnjm48y

vsnjm48y2#

看起来你在使用旧版本的Microsoft编译器。我不能在我现有的版本中重现你的编译器错误。
但你可以而且应该改变这一点:

long double root = (long double) sqrt(mass[i]);
    if (root * root == mass[i]) {

对此:

double value = (double)mass[i];
    double root = sqrt(value);
    if (root * root == value) {

转换回长双不会给你带来任何东西。mass[i] form unsigned long long到double的显式转换可能会修复编译器错误。

更新

如果你完全避免浮点数,可能会更好。某些编译器和运行时在实现sqrt函数时存在固有的精度问题。大多数情况下,它对整数都能正常工作,但为什么要冒险呢?让我们介绍一个有价值的平方根算法的无符号长长整数。这几乎只是一个二分搜索。

unsigned long long squareRoot(unsigned long long value) {

    // To prevent overflow, take advangage of the fact that sizeof(result) <= sizeof(value)/2
    // This likely assumes two's complement machine
    const unsigned long long max_value = (unsigned long long)(-1);
    const unsigned long long max_square_root = max_value >> (4 * sizeof(value));

    unsigned long long low = 0;
    unsigned long long high = (value > max_square_root) ? max_square_root : (value / 2);
    unsigned long long mid = value / 2;

    while (low <= high) {
        mid = (low + high) / 2;
        unsigned long long midSquared = mid * mid;
        if (midSquared == value) {
            return mid;
        }
        if (midSquared < value) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }

    // return the value closest to the actual square root without going over
    if (mid * mid > value) {
        mid--;
    }
    return mid;
}

那么你的主循环就是:

for (int i = 0; i < n; i++) {
    scanf("%llu", &mass[i]);

    unsigned long long root = squareRoot(mass[i]);
    if (root * root == mass[i]) {
        if (mass[i] > max) {
            max = mass[i];
            max_index = i;
        }
    }
}

相关问题