求完全平方数C语言多种算法

在C语言中，求一个整数是否为完全平方数可以采用几种不同的算法。这里简单介绍两种常见的方法：

1. **试除法**（Brute Force Method）：
这是最直观的方法。遍历从1到该整数平方根的所有数字，看能否找到一个数乘以其本身等于给定的数。如果找到，则它是完全平方数；否则不是。

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

int isPerfectSquare(int num) {
    int root = sqrt(num);
    if (root * root == num)
        return 1; // 返回1表示是完全平方数
    else
        return 0; // 返回0表示不是完全平方数
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    if (isPerfectSquare(n))
        printf("%d is a perfect square.", n);
    else
        printf("%d is not a perfect square.", n);
    return 0;
}

2. **二分查找法**（Binary Search）：
利用完全平方数的性质，我们知道它们在有序列表中的位置会形成一个等差序列。我们可以先计算出需要查找范围的上限（即目标数开方后的整数部分），然后在范围内使用二分查找寻找符合条件的平方数。

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

int binarySearchForPerfectSquare(int low, int high, int num) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (mid * mid == num)
            return mid;
        else if (mid * mid > num)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1; // 如果没有找到则返回-1
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    int result = binarySearchForPerfectSquare(0, n, n);
    if (result != -1)
        printf("%d is a perfect square of %d.", n, result * result);
    else
        printf("%d is not a perfect square.", n);
    return 0;
}