โปรแกรมหาผลรวมของอนุกรม 1 + 2 + 2 + 3 + 3 + 3 + .. + n ใน C++

ในปัญหานี้ เราได้รับตัวเลข n ซึ่งหมายถึงเทอมที่ n ของอนุกรมนั้น งานของเราคือสร้าง โปรแกรมเพื่อค้นหาผลรวมของซีรีส์ 1 + 2 + 2 + 3 +3 + 3 + .. + n ใน C++ .

คำอธิบายปัญหา − ในที่นี้ เราจะหาผลรวมของอนุกรมที่มีพจน์ที่ n คือ n คูณผลรวมของหมายเลข n ซึ่งหมายความว่าเป็นชุดของเลขกำลังสอง

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

n = 4

ผลลัพธ์

30

คำอธิบาย

ผลรวมของอนุกรมจนถึงเทอมที่ 4 =1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 =30

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาที่มีประสิทธิภาพมากที่สุดคือการใช้สูตรทั่วไปสำหรับผลรวมของอนุกรม

แต่มาพูดคุยถึงวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมดที่อาจคิดได้

วิธีแก้ปัญหาที่ง่ายที่สุด ปัญหาคือโดยตรงโดยการเพิ่มจำนวนชุดจนถึง n การดำเนินการนี้จำเป็นต้องมีการวนซ้ำซ้อน 2 ลูป หนึ่งเทอมและวงในสำหรับค่าในแต่ละเทอม

อัลกอริทึม

เริ่มต้น − sumVar =0;

• ขั้นตอนที่ 1 − วนรอบสำหรับ i -> 1 ถึง n.
  • ขั้นตอนที่ 1.1 − วนสำหรับ j -> 1 ถึง i.
    • ขั้นตอนที่ 1.1.1 − อัปเดต sumVar, sumVar+=i;
• ขั้นตอนที่ 2 − พิมพ์ sumVar

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
   int sumVar = 0;
   for(int i = 1; i <= n; i++){
      for(int j = 1; j <= i; j++){
         sumVar += i;
      }
   }
   return sumVar;
}
int main(){
   int n = 7;
   cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
   return 0;
}

ผลลัพธ์

The sum of series till 7 is 140

วิธีแก้ปัญหานี้เรียบง่ายแต่ไม่ได้ผลเนื่องจากมีการวนซ้ำซ้อนสองรอบ ทำให้เวลาของลำดับมีความซับซ้อน O(n2) .

โซลูชันที่มีประสิทธิภาพ ขึ้นอยู่กับข้อเท็จจริงที่ว่าถ้าบวกตัวเลข (n) ในตัวมันเอง n ครั้ง จากนั้น ผลลัพธ์สามารถทำได้โดยการคูณตัวเลขด้วยตัวมันเอง

เช่น 5+5+5+5+5 =5*5

ดังนั้นเราจึงสามารถใช้การคูณแทนการวนซ้ำเพื่อแก้ปัญหาได้

อัลกอริทึม

เริ่มต้น − sumVal =0;

• ขั้นตอนที่ 1 − ลูปสำหรับ i -> 0 ถึง n.
  • ขั้นตอนที่ 2 − อัปเดต sumVal, sumVal +=(i*i)

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
   int sumVar = 0;
   for(int i = 1; i <= n; i++){
      sumVar += (i*i);
   }
   return sumVar;
}
int main(){
   int n = 7;
   cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
   return 0;
}

ผลลัพธ์

The sum of series till 7 is 140

วิธีแก้ปัญหาดีกว่าเพราะใช้เพียงลูปเดียวและมีเวลาซับซ้อนของลำดับ O(n) แต่ก็ไม่ใช่วิธีแก้ปัญหาที่ดีที่สุดเท่าที่จะสามารถทำได้ในความซับซ้อนของเวลา O(1)

วิธีแก้ปัญหาที่มีประสิทธิภาพที่สุด กำลังใช้สูตรทั่วไปสำหรับผลรวมของอนุกรมที่กำหนด

ผลรวมของอนุกรม =

1 + 2 + 2 + 3 + 3 + 3 + …. N.

สามารถทำได้เป็น

1 + (2+2) + (3+3+3) + … + (N+N+N..N)
1*1 + 2*2 + 3*3 + … N*N.
12 + 22 + 32 + … N2.

$Sum =\sum_{\square=1}^\square\blacksquare\square^2$

สูตรสำหรับผลรวมของกำลังสองคือ n*(n+1)*(2n+1)/6 และเราสามารถหาผลรวมโดยใช้สูตรนี้ได้เช่นกัน

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
   int sumVar = 0;
   sumVar = ((n*(n + 1)*( 2 * n + 1))/6 );
      return sumVar;
}
int main(){
   int n = 7;
   cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
   return 0;
}

ผลลัพธ์

The sum of series till 7 is 140