Nombor piramid segi empat sama (jumlah kuasa dua)

A nombor piramid persegi merujuk kepada hasil tambah kuasa dua nombor asli. Nombor asli termasuk semua nombor dari 1 hingga infiniti. Sebagai contoh, 4 nombor piramid persegi pertama ialah 1, 5, 14, dan 30.

Untuk memahami dengan lebih baik, pertimbangkan fakta berikut: Jika kita bermula dengan piramid segi empat sama nombor dan menyusun bola nombor dalam tertib menurun, ia akan membentuk piramid.

Pernyataan Masalah

Diberikan nombor Jumlah. Jika Jumlah ialah hasil tambah kuasa dua bagi n nombor asli pertama, kembalikan n, jika tidak, kembalikan palsu.

Contoh 1

diterjemahkan sebagai:

Contoh 1

Input = 30
Output = 4

Penjelasan = 30 ialah hasil tambah kuasa dua bagi 4 nombor asli yang pertama.

1*1 + 2*2 + 3*3 +4*4 = 30.

Oleh itu, output hendaklah 4.

Contoh 2

Input = 54
Output = -1

Penjelasan = Tiada jumlah kuasa dua mana-mana n nombor asli bersamaan dengan 54. Oleh itu, output hendaklah -1.

Penyelesaian kepada penyataan masalah

Ada dua penyelesaian untuk masalah ini.

Kaedah Pertama: Penyelesaian Keganasan

Kaedah keretakan brute force bermula dari n = 1. Buat 'jumlah' pembolehubah yang menambah kuasa dua nombor asli seterusnya kepada nilai jumlah sebelumnya. Mengembalikan n jika jumlah sama dengan Jumlah, sebaliknya mengembalikan palsu jika jumlah lebih besar daripada Jumlah.

pseudocode

start
n =1 
While (total < sum ):
   Total += n*n
   n=n+1
if(total == sum) : 
   Return n
Else:
   Return false
end

Contoh

Di bawah ialah program C++ untuk menyemak sama ada nombor yang diberikan ialah hasil tambah kuasa dua nombor asli.

#include <iostream>
using namespace std;
// This function returns n if the sum of squares of first 
// n natural numbers is equal to the given sum
// Else it returns -1
int square_pyramidal_number(int sum) {
   // initialize total
   int total = 0;
   // Return -1 if Sum is <= 0
   if(sum <= 0){
      return -1;
   }
   
   // Adding squares of the numbers starting from 1
   int n = 0;
   while ( total < sum){
      n++;
      total += n * n;
   }
   
   // If total becomes equal to sum return n
   if (total == sum)
   return n;
   
   return -1;
}
int main(){
   int S = 30;
   int n = square_pyramidal_number(S);
   cout<< "Number of Square Pyramidal Numbers whose sum is 30: "<< endl;
   (n) ? cout << n : cout << "-1";
   return 0;
}

Output

Number of Square Pyramidal Numbers whose sum is 30: 
4

Kerumitan masa - O(jumlah), dengan jumlah adalah input yang diberikan.

Kerumitan Ruang - O(1): Tiada ruang tambahan digunakan.

Kaedah 2 menggunakan kaedah Newton-Raphson

Kaedah lain ialah kaedah Newton-Raphson. Kaedah Newton-Raphson digunakan untuk mencari punca bagi fungsi tertentu f(x) dan tekaan awal punca.

sum of squares of first n natural numbers = n * (n + 1) * (2*n + 1) / 6, 

n * (n + 1) * (2*n + 1) / 6 = sum or 

k * (k + 1) * (2*k + 1) – 6*sum = 0

Jadi n ialah punca bagi persamaan padu ini dan boleh dikira menggunakan kaedah Newton-Raphson yang melibatkan bermula daripada nilai tekaan awal x0 dan menggunakan formula berikut untuk mencari nilai x seterusnya iaitu daripada nilai sebelumnya xn dapat xn+1.

$$mathrm{x_{1}=x_{0}-frac{f(x_{0})}{f^{'}(x_{0})}}$$#🎜 🎜#

pseudocode

Start
calculate func(x) and derivativeFunction(x) for given initial x
Compute h: h = func(x) / derivFunc(x)
While h is greater than allowed error ε 
   h = func(x) / derivFunc(x)
   x = x – h
If (x is an integer):
   return x
Else:
   return -1;
end

Contoh

Di bawah ialah program C++ untuk menyemak sama ada nombor yang diberikan ialah hasil tambah kuasa dua nombor asli.

#include<bits/stdc++.h>
#define EPSILON 0.001
using namespace std;
// According to Newton Raphson Method The function is
// k * (k + 1) * (2*k + 1) – 6*sum or 2*k*k*k + 3*k*k + k - 6*sum                  
double func(double k, int sum){
   return 2*k*k*k + 3*k*k + k - 6*sum;
}
// Derivative of the above function is 6*k*k + 6*k + 1
double derivativeFunction(double k){
   return 6*k*k + 6*k + 1;
}
// Function to check if double is an integer or not
bool isInteger(double N){
   int X = N;
   double temp2 = N - X;
   if (temp2*10 >=1 ) {
      return false;
   }
   return true;
}
// Function that finds the root of k * (k + 1) * (2*k + 1) – 6*sum
int newtonRaphson(double k, int sum){
   double h = func(k, sum) / derivativeFunction(k);
   while (abs(h) >= EPSILON){
      h = func(k, sum)/derivativeFunction(k);
      // k(i+1) = k(i) - f(k) / f'(k)
      k = k - h;
   }
   if (isInteger(k)) {
      return (int)k;
   }
   else {
      return -1;
   }
}
// Driver program
int main(){
   double x0 = 1; // Initial values assumed
   int sum = 91;
   int n = newtonRaphson(x0,sum);
   cout<< "Number of Square Pyramidal Numbers whose sum is 91: "<< endl;
   (n) ? cout << n : cout << "-1";
   return 0;
}

Output

Number of Square Pyramidal Numbers whose sum is 91: 
6

Kerumitan Masa - O((log n) F(n)) dengan F(n) ialah kos pengiraan f(x)/f'(x), dengan ketepatan n-digit.

Kerumitan Ruang - O(1): Tiada ruang tambahan digunakan.

KESIMPULAN

Artikel ini menyelesaikan masalah mencari nombor piramid segi empat sama bagi jumlah tertentu. Kami memperkenalkan dua kaedah: satu kaedah kekerasan dan satu lagi kaedah yang cekap. Kedua-dua kaedah menyediakan program C++.

Atas ialah kandungan terperinci Nombor piramid segi empat sama (jumlah kuasa dua). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!