C++에서 합계 N을 사용하여 가능한 모든 연속 숫자 합계 인쇄

이 문제에서 양의 정수 N이 주어지고 합계가 N인 가능한 모든 연속 숫자의 시퀀스를 인쇄해야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

Input: N = 15
Output: 1 2 3 4 5
7 8

이 문제에 대한 간단한 솔루션은 N/2까지 연속 시퀀스 조합을 추가하는 것입니다. 그런 다음 합이 N이 되는 시퀀스를 인쇄합니다.

예시

#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;
}

출력

합이 최대 25인 연속 숫자의 시퀀스는 -

3 4 5 6 7
12 13

이 방법은 쉽지만 그다지 효율적이지 않습니다.

따라서 미리 계산된 합계 배열을 사용하여 합계를 추적하는 더 복잡하지만 최적의 솔루션이 있습니다. 이렇게 하면 합계의 복잡성이 줄어듭니다.

예

#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;
}

출력

합이 최대 25인 연속 숫자의 시퀀스는 -

3 4 5 6 7
12 13