एक धनात्मक संख्या 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 को इनपुट के रूप में लें।
- फ़ंक्शन 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 लूप के अंत में परिणाम के रूप में 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
