इनपुट के रूप में एक सकारात्मक संख्या N दिया गया है। लक्ष्य उन तरीकों की संख्या ज्ञात करना है जिनसे हम N को केवल 1s, 3s और 4s के योग के रूप में व्यक्त कर सकते हैं। उदाहरण के लिए, यदि N 4 है तो इसे 1+1+1+1, 3+1, 1+3, 4 के रूप में दर्शाया जा सकता है, इसलिए तरीकों की संख्या 4 होगी।
आइए उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - एन=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
इनपुट - एन=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
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम 1, 3 और 4 के योग के रूप में एन का प्रतिनिधित्व करने के तरीकों की संख्या की गणना करने के लिए एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। सरणी एआर [i] लें जहां मैं संख्या का प्रतिनिधित्व करता हूं और एआर [i] इसे प्रतिनिधित्व करने के तरीकों के रूप में लेता हूं। योग के रूप में।
आधार मामले होंगे
arr[0]=0 (बिल्कुल नहीं)
arr[1]=1 (केवल एक ही रास्ता , 1 )
arr[2]=1 (केवल एक ही रास्ता, 1+1 )
गिरफ्तारी[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 के योग के रूप में व्यक्त करने के विभिन्न तरीकों की गिनती देता है।
- तरीकों की गिनती संग्रहीत करने के लिए सरणी गिरफ्तारी [N+1] लें।
- आधार मामलों को प्रारंभ करें arr[0] =1, arr[1] =1, arr[2] =1 और arr[3] =2.
- बाकी मानों के लिए i=4 से i<=N तक ट्रैवर्स करें।
- गिरफ्तारी के योग[i - 1] + arr[i - 3] + arr[i - 4]।
- लूप के अंत में परिणाम के रूप में वापसी गिरफ्तारी [एन]।
उदाहरण
#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