GESP二级 - 判断平方数 - C/C++ 算法

GESP二级 - 判断平方数 - C/C++ 算法

问题描述： 从键盘读入一个整数n（n≤109），判断是否是平方数，如果是输出Y，不是输出N。

输入描述： 输出一个整数n。

输出描述： 按题意输出Y或者N。

解法一：循环判断

我们可以使用循环来判断一个数是否是平方数。从1开始，依次计算每个数的平方，直到找到一个平方数大于等于给定数n，或者找到一个平方数等于n。

具体步骤如下：

1. 从1开始，依次计算每个数的平方，直到找到一个平方数大于等于给定数n。
2. 如果找到的平方数等于n，说明n是一个平方数，输出Y。
3. 如果找到的平方数大于n，说明n不是一个平方数，输出N。

时间复杂度分析： 最坏情况下，需要计算n个平方数，时间复杂度为O(n)。

解法二：数学性质判断

我们可以利用数学性质来判断一个数是否是平方数。一个数n是平方数，当且仅当n的平方根取整后的结果再平方后等于n。

具体步骤如下：

1. 计算给定数n的平方根的整数部分。
2. 将整数部分再平方后，得到一个数m。
3. 如果m等于n，说明n是一个平方数，输出Y。
4. 如果m不等于n，说明n不是一个平方数，输出N。

时间复杂度分析： 计算平方根的时间复杂度为O(1)，平方运算的时间复杂度也为O(1)。

C++ 代码实现 (解法二):

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;

    int sqrt_n = sqrt(n); // 计算n的平方根的整数部分
    int square_sqrt_n = sqrt_n * sqrt_n; // 将整数部分再平方

    if (square_sqrt_n == n) {
        cout << 'Y' << endl;
    } else {
        cout << 'N' << endl;
    }

    return 0;
}

时间复杂度：O(1)