八角星数

---

在数学中，八角星数是一种基于八角星的图形数，其形式为 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 进行比较，这是一种更快、更有效的方法。