Đếm các cách khác nhau để biểu thị N thành tổng của 1, 3 và 4 trong C ++

Cho một số dương N làm đầu vào. Mục đích là tìm ra số cách mà chúng ta có thể biểu diễn N dưới dạng tổng của các số 1, 3 và 4. Ví dụ, nếu N là 4 thì nó có thể được biểu diễn dưới dạng 1 + 1 + 1 + 1, 3 + 1, 1 + 3, 4 nên số cách sẽ là 4.

Hãy cho chúng tôi hiểu với các ví dụ.

Ví dụ

Đầu vào - N =5

Đầu ra - Đếm các cách khác nhau để biểu thị N thành tổng của 1, 3 và 4 là:6

Giải thích - 5 có thể được biểu diễn dưới dạng:

• 1 + 1 + 1 + 1 + 1
• 1 + 3 + 1
• 3 + 1 + 1
• 1 + 1 + 3
• 4 + 1
• 1 + 4

Đầu vào - N =6

Đầu ra - Đếm các cách khác nhau để biểu thị N thành tổng của 1, 3 và 4 là:9

Giải thích - 9 có thể được biểu diễn dưới dạng:

• 1 + 1 + 1 + 1 + 1 + 1
• 3 + 1 + 1 + 1
• 1 + 3 + 1 + 1
• 1 + 1 + 3 + 1
• 1 + 1 + 1 + 3
• 3 + 3
• 4 + 1 + 1
• 1 + 4 + 1
• 1 + 1 + 4

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trong cách tiếp cận này, chúng tôi sẽ sử dụng một cách tiếp cận lập trình động để đếm số cách chúng tôi có thể biểu diễn N dưới dạng tổng của 1, 3 và 4. Lấy mảng arr [i] trong đó tôi đại diện cho số và arr [i] làm các cách để biểu diễn nó. như tổng.

Các trường hợp cơ bản sẽ là

arr [0] =0 (Không được)

arr [1] =1 (chỉ một chiều, 1)

arr [2] =1 (chỉ một chiều, 1 + 1)

arr [3] =2 (1 + 1 + 1, 3)

Bây giờ các số khác 4, 5… i, v.v. sẽ có các cách là arr [i-1] + arr [i-3] + arr [i-4].

• Lấy một số dương N làm đầu vào.
• Hàm Expres_sum (int N) nhận N và trả về số lượng theo các cách khác nhau để biểu thị N thành tổng của 1, 3 và 4.
• Lấy mảng arr [N + 1] để lưu trữ số lượng các cách.
• Khởi tạo các trường hợp cơ sở arr [0] =1, arr [1] =1, arr [2] =1 và arr [3] =2.
• Di chuyển đối với các giá trị còn lại từ i =4 đến i <=N.
• Kết quả rút ra arr [i] dưới dạng tổng của arr [i - 1] + arr [i - 3] + arr [i - 4].
• Ở cuối vòng lặp for, kết quả là trả về arr [N].

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int Expres_sum(int N) {
   int arr[N + 1];
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 1;
   arr[3] = 2;
   for (int i = 4; i <= N; i++) {
      arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4];
   }
   return arr[N];
}
int main() {
   int N = 5;
   cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N);
   return 0;
}

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Đầu ra

Count of different ways to express N as the sum of 1, 3 and 4 are: 6