不是完全平方数的最大数


在本文中,我们将讨论两种不同的方法来找出小于给定数字且不是完全平方数的最大数字。在第一种方法中,我们将运行一个循环来检查每个数字,直到找到所需的数字;而在第二种方法中,我们将使用平方根的概念来生成小于给定数字的完全平方数,并在此基础上找出小于“nums”且不是完全平方数的最大数字。

让我们首先了解问题陈述。

问题陈述

给定一个数字“nums”,我们的任务是找出小于“nums”且不是完全平方数的最大数字。

完全平方数 - 如果一个数可以表示为两个相等整数的乘积,则称该数为完全平方数。完全平方数的一些例子是 - 49、64、81 等。

让我们现在使用一个例子来理解问题陈述 -

Input: nums = 15
Output: The largest number smaller than 15, which is not a perfect square is 14. 
Input: nums = 17
Output: The largest number smaller than 17, which is not a perfect square is 15. 

方法 1:仅使用循环的简单方法

要找到不是完全平方数的最大数字,我们从用户那里获取输入,并检查小于输入的每个数字,直到找到不是完全平方数的数字。

要检查一个数字是否为完全平方数,我们使用 sqrt() 函数计算其平方根,并检查结果的平方是否等于原始数字。

我们使用 while 循环重复检查数字是否为完全平方数,每次递减 1,直到找到不是完全平方数的数字。

当循环找到第一个不是完全平方数的数字时,它将该数字存储为不是完全平方数的最大数字。

最后,我们打印结果。

示例

此方法的代码如下所示 -

#include <bits/stdc++.h>
using namespace std;
bool isPerfectSquare(int nums) {
   int sqrt_n = sqrt( nums );
   return (sqrt_n * sqrt_n == nums);
}

// main code
int main() {
   int nums =15;
   int temp = nums ;

   // keep decreasing the temp until we get a non – perfect square number
   while ( isPerfectSquare( temp ) ) {
      temp-- ;
   }
   cout <<   " The largest number that is not a perfect square is: " <<  temp  << endl;
   return 0;
}

输出

The largest number that is not a perfect square is: 15
  • 时间复杂度 - 此算法的时间复杂度为 O(sqrt(n)),其中 n 为输入。在这里,我们检查小于 n 的每个数字,直到找到不是完全平方数的数字。由于小于 n 的完全平方数的数量与 n 的平方根成正比,因此算法需要 O(sqrt(n)) 的时间。

  • 空间复杂度 - 此算法的辅助空间复杂度为 O(1),因为我们只使用了恒定的额外空间。

方法 2:基于公式的方法

让我们首先了解我们对此方法的直觉。

我们能否说小于“nums”的数字如果不是完全平方数?

即,如果 (nums-1) 不是完全平方数,则可以得出结论,nums − 1 是小于 nums 且不是完全平方数的最大数字。

但如果“nums” -1 是一个完全平方数,那么我们必须将“nums”递减 2 以获得一个非完全平方数,因此小于“nums”且不是完全平方数的最大数字是“nums” − 2。

因此,我们可以得出结论,我们只需要生成小于“nums”的完全平方数,然后相应地找出结果。

算法

让我们现在将此方法实现到算法中。

  • 步骤 1 - 将“nums”作为输入。

  • 步骤 2 - 计算小于“nums”的数字的完全平方数。

  • 步骤 3 - 如果获得的数字的较小完全平方数等于数字 -1,则我们必须从答案中减去 2(因为“nums” − 1 是一个完全平方数)。

  • 步骤 4 - 否则,我们必须从数字中减去 1,因为我们知道,获得的数字既不是完全平方数,也不是大于或等于原始数字。

示例

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

int justsmallerperfectsq(int nums){
   int ps = floor(sqrt(nums));  
      
   // If nums is already a perfect square decrease ps by 1.
   if (ps * ps == nums )
      ps -= 1; 
   return ps * ps;
}

// bolean function to check if the number is a perfect square or not
int main() {
   int nums = 17;
   int ans =0;
   int temp =  justsmallerperfectsq(nums);
   if(temp == nums-1){
      ans =  nums - 2;
   } else { 
      ans = nums-1;
   }
   cout << "The largest number smaller than " << nums << " that is not a perfect square is: " << ans << endl;
   return 0;
}

输出

The largest number smaller than 17 that is not a perfect square is: 15

结论

我们可以从上述方法中得出结论,如果“nums” -1 不是完全平方数,则小于给定数字“nums”的数字也可以是小于“nums”且不是完全平方数的最大数字。

更新于:2023年10月5日

浏览量:120

开启你的职业生涯

完成课程获得认证

开始学习
广告