Jujukan jumlah (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)

Dalam artikel ini, kita akan melihat cara yang berbeza untuk mengira jumlah jujukan - (n^2 - 1^2) + 2(n^2 - 2^2) + … - n^2 ). Dalam kaedah pertama, kita akan mengira jumlah jujukan bagi setiap i dalam julat 1 hingga n satu demi satu dan menambahnya kepada jumlah akhir.

Dalam kaedah kedua, kami akan memperoleh formula matematik untuk mengira jumlah siri yang diberikan, yang akan mengurangkan kerumitan masa program daripada O(n) kepada O(1).

Pernyataan Masalah − Kami diberi nombor “n” dan tugas kami ialah mengira jumlah jujukan yang diberi (n^2 - 1^2) + 2(n^2 - 2^2) + … ( n^2 - n^2).

Contoh

Input − nombor = 5

Output - Apabila n = 5, jumlah siri (n^2 - 1^2) + 2(n^2 - 2^2) + … n(n^2 - n^2) ialah 150 .

Input − nombor = 3

Output - Untuk n = 3, jumlah siri (n^2 - 1^2) + 2(n^2 - 2^2) + ….n(n^2 - n^2) ialah 18 .

Kaedah 1

Ini adalah kaedah brute force yang paling mudah untuk menyelesaikan masalah jumlah jujukan.

Selepas analisis teliti urutan ini, kita boleh membuat kesimpulan: untuk sebarang nombor n, kita ada

Jumlah = ∑ i*(n^2 - i^2) untuk i = 1 hingga i = n.

Jadi untuk kaedah brute force kita boleh menggunakan formula di atas dalam gelung dengan i dari 1 hingga n untuk menjana penjumlahan yang diperlukan.

Contoh

Kod untuk kaedah ini adalah seperti berikut:

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 3;
   long long sum=0;
   for (int i=1  ; i<num ; i++ ) {
      sum = sum+i*( num*num - i*i );
   }
   cout<< " The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = " << num << " is " <<sum;
   return 0;
}

Output

The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = 3 is 18

Kerumitan

Kerumitan masa - O(n) semasa kita melelang melalui gelung dari 1 hingga n.

Kerumitan Angkasa - Memandangkan kami tidak menggunakan sebarang ruang luaran, kerumitan ruang kaedah ini ialah O(1).

Kaedah 2

Dalam kaedah ini kita akan memperoleh formula yang akan mendapat jumlah jujukan yang diperlukan secara langsung, jadi tiada lelaran diperlukan dan kaedah ini akan menyelesaikan masalah yang diberikan dengan kerumitan masa yang berterusan.

Seperti yang dinyatakan sebelum ini, kami mendapat versi umum siri, diberikan sebagai

Sum = ∑ i*(n^2 - i^2) for i = 1 to i = n.

Siri yang sama boleh ditulis sebagai:

Sum =  n^2∑ i - ∑ i^3

Kita sudah mengetahui formula untuk mengira jumlah semua nombor dari 1 hingga n dan formula untuk mengira jumlah kubus semua nombor dari 1 hingga n, masing-masing:

Jumlah semua nombor dari 1 hingga n

n* ( n+1 )/2 

Di mana n ialah nombor yang diberikan.

Sekarang, cari jumlah kubus semua nombor dari 1 hingga n

(n*( n+1 )/2)^2

Jadi siri yang diberikan boleh ditulis sebagai -

Sum = n^2 * ( n*( n+1 )/2 ) – ( n*( n+1 )/2 )^2

Jumlah boleh dipermudahkan lagi kepada -

Sum = ( n * (n+1)/2 )*( n^2 - ( n * (n+1)/2 ))
Sum = n^2 * ( n+1 )/2 * ( n^2 – (n * ( n+1))/2)
Sum = n^2 * ( n+1 ) * ( n-1 )/4
Sum = n^2 * ( n^2 -1 )/4
Sum = (n^4)/4 – (n^2)/4

Jadi, kita hanya perlu mengira Sum = (n^4)/4 - (n^2)/4, untuk sebarang n, untuk mendapatkan jumlah jujukan yang dikehendaki.

Contoh

Kod untuk kaedah ini adalah seperti berikut:

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 5;
   long long sum = 0;
   sum = num*num*(num*num-1)/4;
   cout<< " The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = " << num << " is " <<sum;
   return 0;
}

Output

The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = 5 is 150

Kerumitan

Kerumitan masa - O(1) kerana kami hanya mengira jumlah yang diperlukan menggunakan formula yang kami peroleh.

Kerumitan Angkasa - Memandangkan kami tidak menggunakan sebarang ruang luaran, kerumitan ruang kaedah ini ialah O(1).

Kesimpulan - Dalam artikel ini kami membincangkan dua kaedah untuk mengira jumlah siri yang diperlukan dan dalam kaedah kedua kami mengurangkan kerumitan masa kepada pemalar.

Atas ialah kandungan terperinci Jujukan jumlah (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!