不是完全平方數的最大數

---

在本文中，我們將討論兩種不同的方法來找出小於給定數字且不是完全平方數的最大數字。在第一種方法中，我們將執行一個迴圈來檢查每個數字，直到找到所需的數字；而在第二種方法中，我們將使用平方根的概念來生成小於給定數字的完全平方數，並在此基礎上找出小於“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”且不是完全平方數的最大數字。