Trong bài toán này, chúng ta được cung cấp hai số nguyên m và n. Nhiệm vụ của chúng ta là Tìm tổng thứ m của n số tự nhiên đầu tiên.
Mô tả sự cố: ta sẽ tìm tổng của n số tự nhiên m lần. Tổng được đưa ra bởi công thức,
nếu (m> 1),
sum (n, m) =sum (sum (n, (m-1)), 1)
nếu (m =1)
sum (n, m) =sum (n, 1) =tổng của n số tự nhiên
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: m =4, n =2
Đầu ra: 231
Giải thích:
sum (2, 4) =sum (sum (2, 3), 1)
=sum (sum (sum (2, 2), 1), 1)
=sum (sum (sum (sum (2, 1), 1), 1), 1)
=sum (sum (sum (3, 1), 1), 1)
=sum (sum (6, 1), 1)
=sum (21, 1)
=231
Phương pháp tiếp cận Giải pháp -
Một giải pháp đơn giản cho vấn đề là sử dụng hai vòng lặp lồng nhau. Cái bên ngoài sẽ dành cho m giá trị và cái bên trong sẽ dành cho n giá trị. Chúng tôi sẽ cập nhật giá trị của n và chúng tôi sẽ tính tổng của n số tự nhiên m lần.
Một cách tiếp cận hiệu quả hơn sẽ gọi một cách đệ quy tổng của n số tự nhiên m lần cập nhật giá trị với tổng trước đó mỗi khi thực hiện đệ quy.
Thuật toán:
Bước 1: cập nhật giá trị tổng với sum = sum (n, m-1) * (sum (n, m-1) +1) / 2 nếu tổng giá trị của m lớn hơn một.
Bước 2: Nếu giá trị của m =1, trả về sum =n * (n + 1) / 2.
Bước 3: trả về tổng.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
6-th summation of first 4 natural numbers is 125230148