लगातार 1 के बिना बाइनरी स्ट्रिंग्स की गणना संख्या क्या है?

आइए लगातार 1 के बिना बाइनरी स्ट्रिंग्स की गिनती की अवधारणा को समझाने के लिए एक उदाहरण पर विचार करें।

उदाहरण

मान लीजिए हम लंबाई 3 की बाइनरी स्ट्रिंग्स की संख्या गिनना चाहते हैं जिनमें लगातार 1 शामिल नहीं है। बाइनरी स्ट्रिंग एक स्ट्रिंग है जिसमें केवल 0 और 1 होते हैं।

लंबाई 3 की संभावित बाइनरी स्ट्रिंग हैं: 000, 001, 010, 011, 100, 101, 110, और 111।

हालाँकि, हमें केवल उन बाइनरी स्ट्रिंग्स को गिनने की ज़रूरत है जिनमें लगातार 1 नहीं है। इसलिए, हमें स्ट्रिंग्स 011, 101 और 111 को गिनती से बाहर करने की आवश्यकता है।

आइए शेष बाइनरी स्ट्रिंग्स का विश्लेषण करें:

• 000: यह एक वैध स्ट्रिंग है क्योंकि इसमें लगातार 1 नहीं है।

• 001: यह एक वैध स्ट्रिंग है क्योंकि इसमें लगातार 1 नहीं है।

• 010: यह एक वैध स्ट्रिंग है क्योंकि इसमें लगातार 1 नहीं है।

• 100: यह एक वैध स्ट्रिंग है क्योंकि इसमें लगातार 1 नहीं है।

• 110: यह एक अमान्य स्ट्रिंग है क्योंकि इसमें लगातार 1 है।

उपरोक्त विश्लेषण से, हम देख सकते हैं कि लगातार 1 के बिना 3 लंबाई की 4 वैध बाइनरी स्ट्रिंग हैं।

लगातार 1 के बिना बाइनरी स्ट्रिंग्स की संख्या की गणना करने के लिए PHP प्रोग्राम

विधि 1- डायनेमिक प्रोग्रामिंग का उपयोग करना

उदाहरण

आउटपुट

Number of binary strings without consecutive 1's: 13

कोड की व्याख्या

यह PHP कोड countBinaryStrings नामक एक फ़ंक्शन को परिभाषित करता है जो गतिशील प्रोग्रामिंग का उपयोग करके लगातार 1 के बिना $n लंबाई की बाइनरी स्ट्रिंग्स की संख्या की गणना करता है। यह एक सरणी $dp को आधार मामलों के साथ प्रारंभ करता है $dp[0] = 1 और $dp[1] = 2, जो स्ट्रिंग के लिए गिनती का प्रतिनिधित्व करता है लंबाई क्रमशः 0 और 1। इसके बाद यह लंबाई 2 से $n के लिए शेष गिनती को भरने के लिए एक लूप का उपयोग करता है, लंबाई के लिए गिनती को जोड़कर $i - 1 और $i - 2. अंत में, यह लंबाई के लिए गिनती लौटाता है $n और इसे प्रिंट करता है। इस विशिष्ट उदाहरण में, कोड 5 की लंबाई के लिए लगातार 1 के बिना बाइनरी स्ट्रिंग्स की संख्या की गणना करता है और परिणाम प्रदर्शित करता है।

विधि 2

आउटपुट

Number of binary strings without consecutive 1's: 13

कोड की व्याख्या

यह PHP कोड लगातार दो 1 के बिना $n लंबाई की अलग-अलग बाइनरी स्ट्रिंग्स की संख्या की गणना करता है। यह गिनती को संग्रहीत करने के लिए दो सरणियों, $a और $b को परिभाषित करता है। आधार मामलों को $a[0] = $b[0] = 1 के रूप में सेट किया गया है। फिर, लंबाई 1 से $ तक की लंबाई की गणना करने के लिए एक लूप का उपयोग किया जाता है। n-1. लंबाई की गिनती $i सरणी $a से लंबाई की गिनती $i-1 और लंबाई की गिनती $[ को जोड़कर प्राप्त की जाती है। &&&]i-1 सरणी से $बी। इसके अतिरिक्त, सरणी में लंबाई $i की गिनती $b लंबाई की गिनती से प्राप्त की जाती है $i-1 सरणी में $ एक। अंत में, कोड सरणी से लंबाई $n-1 के लिए गिनती का योग लौटाता है $a और लंबाई के लिए गिनती $n-1 सरणी से $b, लगातार 1 के बिना बाइनरी स्ट्रिंग्स की कुल संख्या का प्रतिनिधित्व करता है। इस विशेष उदाहरण में, कोड 5 की लंबाई के लिए गिनती की गणना करता है और परिणाम प्रदर्शित करता है।

निष्कर्ष

निष्कर्ष में, पहली विधि गतिशील प्रोग्रामिंग का उपयोग करती है, आधार मामलों के साथ एक सरणी को आरंभ करती है और बड़ी लंबाई के लिए गणना की गणना करती है। यह पिछली दो लंबाई की गणना करके कुशलतापूर्वक परिणाम की गणना करता है। दूसरी विधि एक सरल दृष्टिकोण अपनाती है, जिसमें गिनती को संग्रहीत करने के लिए दो सरणियों का उपयोग किया जाता है और पिछली लंबाई की गिनती के आधार पर उन्हें पुनरावृत्त रूप से अद्यतन किया जाता है। यह दो सरणियों को अलग-अलग जोड़ने की आवश्यकता के बिना सीधे कुल गणना की गणना करता है। दोनों विधियाँ लगातार 1 के बिना बाइनरी स्ट्रिंग्स के लिए सटीक गणना प्रदान करती हैं, और उनके बीच का चुनाव विशिष्ट आवश्यकताओं और प्रदर्शन संबंधी विचारों पर निर्भर हो सकता है।