个人任务5.有效的完全平方数

╰半橙微兮° 2023-09-28 11:53 2阅读 0赞

## 数据结构课设——个人任务5. 有效的完全平方数 ##

> 题目描述：  
> 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。  
> 进阶：不要 使用任何内置的库函数，如 sqrt 。  
> 示例 1：  
> 输入：16  
> 输出：true  
> 示例 2：  
> 输入：14  
> 输出：false

> 输入说明：  
> 输入一个整数num.  
> 提示： 1 <= num <= 2^31 - 1

> 输出说明：  
> 输出一个布尔值表示结果。

> 输入范例：  
> 16

> 输出范例：  
> false

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<stdlib.h>
    #include<stdio.h>
    #include<fstream>
    #include<iomanip>
    using namespace std;
    
    bool isSqare(int n){
        
        if(n==0||n==1||n==4)
            return true;
        for(double i=3;i<n/2;++i){
        //以这个数的一半为临界点
            if(n/i>i)//i的平方小于n说明此时的完全平方数小于n,再增大i之后再与n比较
                continue;
            else if(n/i<i)//如果i的平方大于n，说明n不是完全平方数
                return false;
            else if(n/i==i)//如果正好存在某个i等于n，则说明n是一个完全平方数
                return true;
        }
        return false;//以上情况都不符合是负数的情况
    }
    
    int main(){
        
        int num;
        cin>>num;
        if(isSqare(num))
            cout<<"true"<<endl;
        else
            cout<<"false"<<endl;
        return 0;
    }

我们首先要知道：一个数如果是完全平方数，那么它开方之后的数一定是小于这个数的一半的。  
比如说：16开根号是4,16的一半是8，因为4乘4=16, 8乘2=16，完全平方的2个因子相等，所以所以8和2一平均的话就会比8小，比2大。也就是说开平方的数一定是小于这个数的一半的。

如果输入的数是1或4，就直接返回true，其他的数从3开始判断，一直判断到n/2，如果在这范围内有一个i的平方等于n，那么n就是完全平方数，否则不是。  
1.如果i的平方小于n，说明此时i的平方在n的左侧，需要再循环一次，给i加1，再判断此时的i方与n的大小。  
2.如果i的平方大于n，说明n在（i-1）的平方和i的平方之间，此时n不是一个完全平方数。

还有对于0的特殊情况，我查之后发现0是完全平方数。所以就把0归到特殊情况里了。

是参考了一篇文章上写出这个题解，原文:[有效的完全平方数 C++][C]

[C]: https://blog.csdn.net/m1751250104/article/details/121152965?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%9C%89%E6%95%88%E7%9A%84%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0c++&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-121152965.nonecase&spm=1018.2226.3001.4187