Các cách tạo một con số với Tổng số Ones và Twos

Question

Tôi đang tự hỏi liệu có cách nào để đếm các cách có thể để tính tổng một số chỉ sử dụng một và hai không

Ví dụ:

Ta có số 10. Số 10 có thể được tính bằng:

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...

Trước tiên xin cảm ơn tất cả các bạn!

Answer 1

Nếu thứ tự của các phần tử không quan trọng, như các chú thích giải thích (tức 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2là giống hệt với 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), thì việc này chỉ đơn giản là chọn số phần tử trong tổng, có thể nằm trong khoảng từ 5 đến 10. Sau khi số phần tử được chọn, bạn biết chính xác có bao nhiêu phần tử phải là 1s và bao nhiêu phần tử phải là 2s: Đối với phần tử x, có 10-x 2s, còn lại là 1s.

Vì có 6 số để chọn nên đây là số cách tạo ra 10.

Answer 2

Thay vì đi sâu vào các công thức toán học phức tạp, tôi khuyên bạn nên sử dụng phương pháp 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

Answer 3

Số cách tạo một số chỉ sử dụng một số = 1
Số cách tạo một số sử dụng ít nhất một hai = floor(n/2)
Tổng =1 + floor(n/2)

Xem javascriptđoạn mã bên dưới:

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));