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

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

ให้เราเข้าใจด้วยตัวอย่าง

ตัวอย่าง

ป้อนข้อมูล - N=5

ผลลัพธ์ - การนับวิธีต่างๆ ในการแสดง N เป็นผลรวมของ 1, 3 และ 4 ได้แก่ 6

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

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

ป้อนข้อมูล - N=6

ผลลัพธ์ - การนับวิธีต่างๆ ในการแสดง N เป็นผลรวมของ 1, 3 และ 4 ได้แก่ 9

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

• 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

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

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

กรณีพื้นฐานจะเป็น

arr[0]=0 ( ไม่มีทาง )

arr[1]=1 ( มีทางเดียวเท่านั้น , 1 )

arr[2]=1 ( ทางเดียวเท่านั้น 1+1 )

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

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

• นำจำนวนบวก N เป็นอินพุต
• Function 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.
• Takeaways 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