นับวิธีแสดงจำนวน n เป็นผลรวมจำนวนคี่ด้วย C++

ได้รับจำนวนเต็ม n เป็นอินพุต เป้าหมายคือหาจำนวนวิธีที่เราสามารถแสดง 'n' เป็นผลรวมของจำนวนคี่ (odd integers) ตัวอย่างเช่น ถ้า n=3 สามารถแสดงเป็นผลรวม (1+1+1) และ (3) รวม 2 วิธี

ตัวอย่าง

Input

n=6

Output

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

Explanation

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

Input

n=9

Output

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

Explanation

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 จำนวนวิธีจะเป็น ways(n-1) + ways(n-2)

• รับจำนวนเต็ม n เป็นอินพุต
• ฟังก์ชัน odd_ways(int n) คืนค่าจำนวนวิธีแสดง n เป็นผลรวมจำนวนคี่
• สร้างอาร์เรย์ arr ความยาว n+1 เก็บจำนวนวิธี
• สำหรับเลข 0 ไม่มีวิธี ตั้ง arr[0] = 0
• สำหรับเลข 1 มี 1 วิธี ตั้ง arr[1] = 1
• สำหรับเลขอื่น ตั้ง arr[i] = arr[i-1] + arr[i-2] สำหรับ i ระหว่าง 2 ถึง n
• ในที่สุด arr[n] จะมีจำนวนวิธี
• คืนค่า arr[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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

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