हमें इनपुट के रूप में एक संख्या num दी गई है। लक्ष्य num लंबाई के संभावित स्ट्रिंग्स की संख्या गिनना है जैसे कि सभी आसन्न वर्णों के बीच ASCII मानों का अंतर 1 हो।
यदि num 2 है तो स्ट्रिंग्स होंगी "ab", "ba", "bc", "cb", ......"yz", "zy"।
आइए उदाहरणों से समझते हैं
इनपुट - num=3
आउटपुट - आसन्न वर्णों का अंतर एक होने वाले स्ट्रिंग्स की गिनती - 98
व्याख्या - कुछ नमूना स्ट्रिंग्स हैं: "abc", "aba", "cde" ...."xyx", "zyz", "xyz"।
इनपुट - num=2
आउटपुट - आसन्न वर्णों का अंतर एक होने वाले स्ट्रिंग्स की गिनती - 50
व्याख्या - कुछ नमूना स्ट्रिंग्स हैं: "ab", "ba", "cd" ...."xy", "zy", "yz"।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
लंबाई = 2 के लिए।
'a' से शुरू होने वाला स्ट्रिंग = "ab"
'b' से शुरू होने वाले स्ट्रिंग्स = "ba", "bc"
'c' से शुरू होने वाले स्ट्रिंग्स = "cd", "cb".................
लंबाई = n के लिए।
'a' से शुरू होने वाला स्ट्रिंग = लंबाई n-1 के 'b' से शुरू होने वाले स्ट्रिंग्स की संख्या के तरीके
'b' से शुरू होने वाला स्ट्रिंग = लंबाई n-1 के 'a' या 'c' से शुरू होने वाले स्ट्रिंग्स की संख्या के तरीके
'c' से शुरू होने वाला स्ट्रिंग = लंबाई n-1 के 'b' या 'd' से शुरू होने वाले स्ट्रिंग्स की संख्या के तरीके
हम इसे डायनामिक प्रोग्रामिंग का उपयोग करके हल करेंगे।
एक सरणी arr[num+1][27] लें। जिसमें arr[i][j] में लंबाई i के वर्णमाला संख्या j से शुरू होने वाले स्ट्रिंग्स की संख्या होगी। सभी arr[1][j] स्ट्रिंग्स "a", "b"..."z" के लिए 1 होंगे।
बाकी arr[2 से num+1][0 से 25] के लिए, j=0 के लिए arr[i][j]=arr[i-1][j+1] सेट करें। अन्यथा arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1] सेट करें;
परिणाम num-वीं पंक्ति की गिनती का योग होगा।
- इनपुट पूर्णांक num लें
- फ़ंक्शन difference_strings(int num) num लेता है और आसन्न वर्णों का अंतर एक होने वाले स्ट्रिंग्स की गिनती वापस करता है
- प्रारंभिक गिनती 0 लें।
- arr[num + 1][27] को सभी 0 से आरंभ करें।
- arr[1][0 से 25] को सभी 1 से आरंभ करें।
- दो फॉर लूप का उपयोग करके 2D सरणी arr[][] को दूसरी पंक्ति से अंतिम तक और कॉलम 0 से 25 तक सभी 26 वर्णमालाओं के लिए पार करें।
- j=0 के लिए, शुरुआती वर्ण 'a' है। वर्तमान गिनती को arr[i][j] = arr[i - 1][j + 1] के रूप में सेट करें;
- अन्यथा arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]) सेट करें
- अब उपरोक्त लूप के अंत के बाद, अंतिम पंक्ति को पार करें और arr[num][0 से 25] को गिनती में जोड़ें।
- परिणाम के रूप में गिनती वापस करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
long int count = 0;
long int arr[num + 1][27];
memset(arr, 0, sizeof(arr));
for (int i = 0; i <= 25; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= num; i++){
for (int j = 0; j <= 25; j++){
if (j == 0){
arr[i][j] = arr[i - 1][j + 1];
}
else{
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
}
}
}
for (int i = 0; i <= 25; i++){
count = (count + arr[num][i]);
}
return count;
}
int main(){
int num = 2;
cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
return 0;
}
आउटपुट
Count of strings where adjacent characters are of difference one are: 50