Rumah > Artikel > pembangunan bahagian belakang > 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.
Diberikan nombor Jumlah. Jika Jumlah ialah hasil tambah kuasa dua bagi n nombor asli pertama, kembalikan n, jika tidak, kembalikan palsu.
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.
Input = 54 Output = -1
Penjelasan = Tiada jumlah kuasa dua mana-mana n nombor asli bersamaan dengan 54. Oleh itu, output hendaklah -1.
Ada dua penyelesaian untuk masalah ini.
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.
start n =1 While (total < sum ): Total += n*n n=n+1 if(total == sum) : Return n Else: Return false end
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; }
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 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})}}$$#🎜 🎜#
pseudocodeStart 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
#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 Ruang - O(1): Tiada ruang tambahan digunakan.
KESIMPULAN
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!