Trong bài toán này, chúng ta được cho một số nguyên dương N và chúng ta phải in ra dãy tất cả các số liên tiếp có thể có tổng bằng N.
Hãy lấy một ví dụ để hiểu vấn đề,
Input: N = 15 Output: 1 2 3 4 5 7 8
Một giải pháp đơn giản cho vấn đề này là cộng các tổ hợp chuỗi liên tiếp cho đến N / 2. Và sau đó in chuỗi có tổng lên đến N.
Ví dụ
#include<iostream>
using namespace std;
void printConsequtiveSum(int N){
int start = 1, end = (N+1)/2;
while (start < end){
int sum = 0;
for (int i = start; i <= end; i++){
sum = sum + i;
if (sum == N){
for (int j = start; j <= i; j++)
cout<<j<<" ";
cout<<endl;
break;
}
if (sum > N)
break;
}
sum = 0;
start++;
}
}
int main(){
int N = 25;
cout<<"Sequence of consicutive numbers that sum upto "<<N<<" are :\n";
printConsequtiveSum(N);
return 0;
} Đầu ra
Dãy các số liên tiếp có tổng bằng 25 là -
3 4 5 6 7 12 13
Phương pháp này dễ dàng nhưng không quá hiệu quả.
Vì vậy, chúng tôi có một giải pháp phức tạp hơn nhưng tối ưu hơn sẽ sử dụng một mảng tổng được tính toán trước để theo dõi tổng. Điều này sẽ làm giảm độ phức tạp của tổng.
Ví dụ
#include <iostream>
using namespace std;
void printConsequtiveSum(int N){
int start = 1, end = 1;
int sum = 1;
while (start <= N/2){
if (sum < N){
end += 1;
sum += end;
}
else if (sum > N){
sum -= start;
start += 1;
}
else if (sum == N){
for (int i = start; i <= end; ++i)
cout<<i<<" ";
cout<<endl;
sum -= start;
start += 1;
}
}
}
int main(){
int N = 25;
cout<<"Sequence of consicutive numbers that sum upto "<<N<<" are:\n";
printConsequtiveSum(N);
return 0;
} Đầu ra
Dãy các số liên tiếp có tổng đến 25 là -
3 4 5 6 7 12 13