Cho một số nguyên n làm đầu vào. Mục đích là tìm số cách mà chúng ta có thể biểu diễn ‘n’ dưới dạng tổng các số nguyên lẻ. Ví dụ, nếu n là 3 thì nó có thể được biểu diễn dưới dạng tổng (1 + 1 + 1) và (3) nên có tổng 2 cách.
Ví dụ
Đầu vào
n=6
Đầu ra
Count of ways to express ‘n’ as sum of odd integers are: 8
Giải thích
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
Đầu vào
n=9
Đầu ra
Count of ways to express ‘n’ as sum of odd integers are: 34
Giải thích
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
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 ta sẽ kiểm tra các cách biểu diễn một số dưới dạng tổng các số nguyên lẻ từ các số trước đó là số thứ n − 1 và thứ n − 2. Cách sẽ là cách (n − 1) + cách (n − 2).
-
Lấy một số nguyên n làm đầu vào.
-
Hàm retail_ways (int n) nhận một số và trả về số lượng các cách để biểu thị ‘n’ dưới dạng tổng các số nguyên lẻ.
-
Lấy một mảng có độ dài n + 1 để lưu trữ các cách đếm để biểu diễn các số dưới dạng tổng các số nguyên lẻ.
-
Đối với số 0, không có cách nào như vậy, vì vậy hãy đặt arr [0] bằng 0.
-
Đối với số 1, chỉ có một cách để đặt arr [1] với 1.
-
Đối với các số còn lại, chúng ta có thể đặt arr [i] với arr [i − 1] + arr [i − 2] cho i trong khoảng từ 2 đến n.
-
Cuối cùng, chúng ta có arr [n] cho số cách trong đó n được biểu diễn dưới dạng tổng các số nguyên lẻ.
-
Kết quả là trả về arr [n].
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of ways to express ‘n’ as sum of odd integers are: 8