Rumah > pembangunan bahagian belakang > C++ > Nombor piramid segi empat sama (jumlah kuasa dua)

Nombor piramid segi empat sama (jumlah kuasa dua)

PHPz
Lepaskan: 2023-09-04 23:57:08
ke hadapan
1333 orang telah melayarinya

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
Salin selepas log masuk

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

1*1 + 2*2 + 3*3 +4*4 = 30.
Salin selepas log masuk

Oleh itu, output hendaklah 4.

Contoh 2

Input = 54
Output = -1
Salin selepas log masuk

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
Salin selepas log masuk

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;
}
Salin selepas log masuk

Output

Number of Square Pyramidal Numbers whose sum is 30: 
4
Salin selepas log masuk

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
Salin selepas log masuk

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
Salin selepas log masuk

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;
}
Salin selepas log masuk

Output

Number of Square Pyramidal Numbers whose sum is 91: 
6
Salin selepas log masuk
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!

Label berkaitan:
sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan