1과 2의 합으로 숫자를 만드는 방법

Aug 16 2020

1과 2만을 사용하여 숫자를 합하는 가능한 방법을 세는 방법이 있는지 궁금합니다.

예를 들면 :

우리는 숫자 10을 가지고 있습니다. 숫자 10은 다음과 같이 더할 수 있습니다.

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1  
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2
2 + 2 + 2 + 2 + 2 
etc...

미리 감사드립니다!

답변

1 amit Aug 17 2020 at 03:22

코멘트 설명대로 요소의 순서는 중요하지 않습니다 경우 (즉 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2동일 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1당신이 단순히 요소의 수를 선택되면 어디서든 10 (5) 사이가 될 수 요약 요소의 수를 선택하고있다) 정확히 몇 개가 1이되어야하고 몇 개가 2가되어야하는지 정확히 알 수 있습니다. x 요소의 경우 10-x 2가 있고 나머지는 1입니다.

선택할 수있는 숫자가 6 개이므로 10 개를 만드는 방법의 수입니다.

another_CS_guy Aug 17 2020 at 05:36

복잡한 수학 공식에 들어가는 대신 DP 접근 방식을 권장합니다.


    int arr[N+1]; // Represents no. of ways to produce a number at index 1
    // Like arr[5] is no. of ways to produce number 5
    
    for(int i=0;i<=N;i++) {
      arr[i] = 1; // As all 1s
    }
    
    for(int i=2;i<=N;i++) {
      // if we add 2 now, check for no. of ways i-2 can be made, 
      // add it to current arr[i] value.
      arr[i] += arr[i-2];
    }
    
    cout<< (arr[N]); // print

RahulBhobe Aug 17 2020 at 18:07

1 만 1
사용하여 숫자를 만드는 방법의 수 = 적어도 하나를 사용하여 숫자를 만드는 방법의 수 = 둘 = floor(n/2)
합계 =1 + floor(n/2)

아래 javascript코드 스 니펫을 참조하세요.

let numWays = n => 1 + Math.floor(n/2);

for (let i=1; i<=20; i++)
    console.log("Number of ways to create " + i + " is: " + numWays(i));