C++ 八面体星体数

在数学中，八面体星体数是基于八面体星体的数量，形式为n(2n 2 − 1)。

八面体星体数中的完全平方数为 1 和 9653449 。

问题陈述

给定一个数n，检查它是否为八面体星体数。八面体星体数的序列是0、1、14、51、124、245、426、679、1016、1449、1990。

示例1

输入

x = 14

输出结果

Yes

解释

$当: n = 2, 表达式 :n\lgroup 2n^2 – 1\rgroup 的值为: 14$

示例2

输入

n = 22

输出

No

解释：

$\mathrm{没有 : 一个: n: 使得 : n(2n^2 – 1): 是: 22}$

解决方案

有两个可能的解。

方法1：

一个简单的方法是从0开始找到n使得n(2n2 – 1)的值，并将其与给定的数字（记为x）进行比较。我们将不断递增n并重新计算n(2n2 – 1)，直到它等于x，这意味着x是一个Stella八面体数。如果值变大于x，我们将停止，这意味着x不是一个Stella八面体数。

伪代码：

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++程序，使用上述讨论的方法来检查给定的数是否是Stella八角数。

#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)作为上界。

空间复杂度为O(1)，因为它不使用任何额外的空间。

方法2

检查一个数是否为斯特拉八角数的更有效方法是使用一个无界二分搜索。

在这种方法中，我们从n=1开始，每次将i的值加倍，计算表达式n(2n 2 - 1)的值，直到表达式的值小于x。

然后，我们将检查表达式的值是否等于x。如果等于x，则返回true，否则我们调用二分搜索。在这个调用中，我们将x与范围从n/2到n的表达式n(2n 2 - 1)的值进行比较，如果它们相等则返回true，否则返回false。

伪代码

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

示例

下面是一个使用上述讨论的方法来检查给定数字是否为Stella八面体数的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++ 程序将产生以下输出：