ในปัญหานี้ เราได้รับจำนวนเต็มสองจำนวน m และ n งานของเราคือ หาผลบวกที่ m ของจำนวนธรรมชาติ n ตัวแรก
คำอธิบายปัญหา: เราจะหาผลรวมของจำนวนธรรมชาติ n ตัว m ครั้ง ผลรวมถูกกำหนดโดยสูตร
ถ้า (ม> 1),
ผลรวม(n, m) =ผลรวม( ผลรวม(n, (m-1)), 1 )
ถ้า (ม =1)
sum(n, m) =sum(n, 1) =ผลรวมของ n จำนวนธรรมชาติ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: m =4, n =2
ผลลัพธ์: 231
คำอธิบาย:
ผลรวม(2, 4) =ผลรวม ( ผลรวม(2, 3), 1 )
=ผลรวม ( ผลรวม ( ผลรวม (2, 2), 1) , 1 )
=ผลรวม ( ผลรวม ( ผลรวม (ผลรวม (2, 1), 1) , 1 ), 1)
=ผลรวม ( ผลรวม ( ผลรวม (3, 1) , 1 ), 1)
=ผลรวม ( ผลรวม ( 6 , 1 ), 1)
=ผลรวม (21, 1)
=231
แนวทางการแก้ปัญหา -
วิธีแก้ปัญหาอย่างง่ายคือการใช้สองลูปที่ซ้อนกัน ตัวนอกจะเป็นค่า m และตัวในจะเป็น n ค่า เราจะอัปเดตค่าของ n และเราจะคำนวณผลรวมของ n จำนวนธรรมชาติ m ครั้ง
วิธีที่มีประสิทธิภาพมากขึ้นคือการเรียกผลรวมของจำนวนธรรมชาติ n จำนวน m คูณด้วยการอัปเดตค่าด้วยผลรวมก่อนหน้าในแต่ละครั้งที่มีการเรียกซ้ำ
อัลกอริทึม:
ขั้นตอนที่ 1: อัปเดตค่า sum ด้วย sum =sum(n, m-1)* (sum(n, m-1)+1) / 2 ถ้าผลรวมของ m มากกว่า 1
ขั้นตอนที่ 2: หากค่าของ m =1 ให้คืนค่า sum =n * (n+1) /2
ขั้นตอนที่ 3: ผลตอบแทนรวม
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int calcSumN(int n, int m) {
if (m == 1)
return (n * (n + 1) / 2);
return (calcSumN(n, m-1) * (calcSumN(n, m-1) + 1) / 2);
}
int main() {
int n = 4;
int m = 6;
cout<<m<<"-th summation of first "<<n<<" natural numbers is "<<calcSumN(n, m);
return 0;
} ผลลัพธ์
6-th summation of first 4 natural numbers is 125230148
