C++에서 홀수 정수의 합으로 'n'을 표현하는 방법 세기

입력으로 정수 n이 주어집니다. 목표는 'n'을 홀수 정수의 합으로 나타낼 수 있는 방법의 수를 찾는 것입니다. 예를 들어 n이 3이면 합( 1+1+1 )과 (3)으로 나타낼 수 있으므로 총 2가지입니다.

예를 들어

입력

n=6

출력

Count of ways to express ‘n’ as sum of odd integers are: 8

설명

The ways in which we can express ‘n’ as sum of odd integers −
1. 1+1+1+1+1+1
2. 3+1+1+1
3. 1+3+1+1
4. 1+1+3+1
5. 1+1+1+3
6. 3+3
7. 1+5
8. 5+1

입력

n=9

출력

Count of ways to express ‘n’ as sum of odd integers are: 34

설명

The some of the ways in which we can express ‘n’ as sum of odd integers:
1. 1+1+1+1+1+1+1+1+1
2. 3+3+3
3. 5+3+1
4. 7+1+1
5. ….and other such combinations

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -

이 접근법에서 우리는 n−1번째와 n−2번째 숫자인 이전 숫자의 홀수 정수의 합으로 숫자를 나타내는 방법을 확인할 것입니다. 길은 길(n−1) + 길(n−2)이 됩니다.

• 정수 n을 입력으로 받습니다.

• 함수 odd_ways(int n)는 숫자를 받아서 'n'을 홀수 정수의 합으로 표현하는 방법의 개수를 반환합니다.

• 홀수 정수의 합으로 숫자를 나타내는 방법을 저장하려면 길이가 n+1인 배열 arr를 사용합니다.

• 숫자 0의 경우 그런 방법이 없으므로 arr[0]을 0으로 설정합니다.

• 숫자 1의 경우 한 가지 방법만 있으므로 arr[1]을 1로 설정합니다.

• 나머지 숫자에 대해 우리는 2에서 n 사이의 i에 대해 arr[i−1]+arr[i−2]로 arr[i]를 설정할 수 있습니다.

• 끝에 n이 홀수 정수의 합으로 표현되는 방법의 수에 대한 arr[n]이 있습니다.

• 결과로 ar[n]을 반환합니다.

예

#include<iostream>
using namespace std;
int odd_ways(int n){
   int arr[n+1];
   arr[0] = 0;
   arr[1] = 1;
   for(int i = 2; i <= n; i++){
      arr[i] = arr[i-1] + arr[i-2];
   }
   return arr[n];
}
int main(){
   int n = 6;
   cout<<"Count of ways to express ‘n’ as sum of odd integers are: "<<odd_ways(n);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Count of ways to express ‘n’ as sum of odd integers are: 8