นับวิธีการแสดง N เป็นผลรวมของ 1, 3 และ 4 ใน C++

กำหนดจำนวนบวก N เป็นอินพุต เป้าหมายคือหาจำนวนวิธีที่เราสามารถแสดง N เป็นผลรวมของ 1, 3 และ 4 เท่านั้น ตัวอย่างเช่น ถ้า N คือ 4 แล้วสามารถแสดงเป็น 1+1+1+1, 3+1, 1+3, 4 ดังนั้นจำนวนวิธีจะเป็น 4

ทำความเข้าใจด้วยตัวอย่าง

ตัวอย่าง

Input - N = 5

Output - จำนวนวิธีการแสดง N เป็นผลรวมของ 1, 3 และ 4 คือ: 6

คำอธิบาย - 5 สามารถแสดงเป็น:

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

Input - N = 6

Output - จำนวนวิธีการแสดง N เป็นผลรวมของ 1, 3 และ 4 คือ: 9

คำอธิบาย - 6 สามารถแสดงเป็น:

• 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

แนวทางที่ใช้ในโปรแกรมด้านล่าง

ในแนวทางนี้ เราจะใช้แนวทาง dynamic programming เพื่อนับจำนวนวิธีที่เราสามารถแสดง N เป็นผลรวมของ 1, 3 และ 4 ใช้ อาร์เรย์ arr[i] โดย i แทนตัวเลขและ arr[i] แทนจำนวนวิธีแสดงเป็นผลรวม

กรณีฐาน (base cases) จะเป็น

arr[0] = 1 (1 วิธี คือ ไม่เลือกอะไร)

arr[1] = 1 (เพียง 1 วิธี คือ 1)

arr[2] = 1 (เพียง 1 วิธี คือ 1+1)

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

ตอนนี้ตัวเลขอื่นๆ 4, 5 ... i จะมีวิธีเป็น arr[i-1] + arr[i-3] + arr[i-4]

• รับจำนวนบวก N เป็นอินพุต
• ฟังก์ชัน Expres_sum(int N) รับ N และคืนค่าจำนวนวิธีการแสดง N เป็นผลรวมของ 1, 3 และ 4
• รับอาร์เรย์ arr[N+1] เก็บจำนวนวิธี
• เริ่มต้นกรณีฐาน arr[0] = 1, arr[1] = 1, arr[2] = 1 และ arr[3] = 2
• วนลูปสำหรับค่าที่เหลือจาก i = 4 ถึง i <= N
• ตั้ง arr[i] เป็นผลรวมของ arr[i-1] + arr[i-3] + arr[i-4]
• ในท้ายที่สุดของ for loop คืนค่า arr[N] เป็นผลลัพธ์

ตัวอย่าง

#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; 
}

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

ผลลัพธ์

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