八角星數

---

在數學中，八角星數是一種基於八角星的圖形數，其形式為 n(2n² − 1)。

是完全平方數的八角星數為 1 和 9653449。

問題陳述

給定一個數字 n，檢查它是否為八角星數。八角星數的序列為 0、1、14、51、124、245、426、679、1016、1449、1990。

示例1

輸入

x = 14

輸出

Yes

解釋

$$\mathrm{對於 n = 2，表示式 n\lgroup 2n^2 – 1\rgroup 為 14}$$

示例2

輸入

n = 22

輸出

No

解釋

$$\mathrm{不存在 n 使得 n(2n^2 – 1) 等於 22}$$

解決方案

有兩種可能的解決方案。

方法 1

解決此問題的一種簡單方法是從 n 等於 0 開始，找到 n(2n² – 1) 的值，然後將其與給定數字（將其視為 x）進行比較。我們將繼續增加 n 並重新計算 n(2n² – 1)，直到它等於 x，這將意味著 x 是八角星數。如果值變得大於 x，我們將停止，這意味著 x 不是八角星數。

虛擬碼

Start
while n*(2*n*n - 1) is less than x
	n = n + 1
if n*(2*n*n - 1) is equal to x
	then return yes
else return false
End

示例

下面是一個 C++ 程式，用於使用上述方法檢查給定數字是否為八角星數。

#include <iostream>
using namespace std;
// Function to check the input number
int checkStellaOctangula(int x){
   // Initiating n from 0
   int n = 0;
   // Calculating n*(2*n*n - 1) for each n
   // and incrementing n if it is less than x
   while(n*(2*n*n - 1)<x){
      n++;
   }
   // checking if the value of an expression is equal to x
   // if it's equal, return true
   if(n*(2*n*n - 1)==x){
      return true;
   }
   // otherwise return false
   return false;
}
int main(){
   int x = 51;
   if (checkStellaOctangula(x)){  
      cout << "Yes";
   }
   else{
      cout << "No";
   }
   return 0;
}

輸出

對於輸入 x = 52，上述 C++ 程式將產生以下輸出：

Yes

此方法的時間複雜度可能達到 O(x)，因為上限為 x。

此方法的空間複雜度為 O(1)，因為它不使用任何額外的空間。

方法 2

檢查數字是否為八角星數的更有效方法是使用無界二分搜尋。

在這種方法中，我們從 n = 1 開始，每次將 i 的值加倍時都計算 n(2n² – 1) 的值。我們將這樣做，直到表示式 n(2n² – 1) 的值小於 x。

之後，我們將檢查表示式的值是否等於 x。如果等於 x，則返回真，否則我們呼叫二分搜尋。在此呼叫中，我們將 x 與表示式 n(2n² – 1) 在 n/2 到 n 範圍內的值進行比較，如果它們相等則返回真，否則返回假。

虛擬碼

Start
while n*(2*n*n - 1) is less than x
	n = n * 2
if n*(2*n*n - 1) is equal to x
	then return yes
else 
	Repeat until low>=high
	mid=(low+high)/2 
	If n*(2*n*n - 1) < x, 
		low=mid+1 
	Else If n*(2*n*n - 1) > x 
		high=mid-1
	else 
		return true
End

示例

下面是一個 C++ 程式，用於使用上述方法檢查給定數字是否為八角星數。

#include <bits/stdc++.h>
using namespace std;
// Function to calculate value of n*(2*n*n - 1)
int calculateExp(int n) {
   return n*(2*n*n - 1);
}
// Using binary search to search for a value of n for which
// expression has value equal to x
// where n lies in the interval (low to high)
// low is n/2 and high is n
bool binarySearch(int low, int high, int x){
   while (low <= high) {
      int mid = (low + high) / 2;
      if (calculateExp(mid) < x){
         low = mid + 1;
      }
      else if (calculateExp(mid) > x){
         high = mid - 1;
      }
     else{
         return true;
      }
   }
   return false;
}
// Function to check the input number
bool checkStellaOctangula(int x){
   // Edge case
   if (x == 0)
   return true;
   // Starting from n = 1 and doubling it
   // while the value of expression is less than x
   int n = 1;
   while (calculateExp(n) < x){
      n = n*2;
   }
   // If the expression is equal to x
   // return true
   if (calculateExp(n) == x){
      return true;
   }
   // Otherwise call binary search
   // range for the search decided by
   // finding value of expression for n
   // in range n/2 to n
 return binarySearch(n/2, n, x);
}

int main(){
   int x = 51;
   if (checkStellaOctangula(x)){ 
      cout << "Yes";
   }
   else{
      cout << "No";
   }
   return 0;
}

輸出

對於輸入 x = 51，上述 C++ 程式將產生以下輸出：

Yes

時間複雜度為 O(log n)，因為我們每次迭代都將 n 的值加倍。

此方法的空間複雜度為 O(1)，因為它不使用任何額外的空間。

結論

我們討論了兩種方法。在第一種方法中，我們線性地遞增 n 並計算每個值的 n*(2*n*n - 1)，並將其與 x 進行比較。這種方法非常緩慢且效率低下。在第二種方法中，我們將 n 的值加倍，然後計算 n*(2*n*n - 1) 並將其與 x 進行比較，這是一種更快、更有效的方法。