हमें इनपुट के रूप में एक अंक संख्या दी जाती है। लक्ष्य लंबाई संख्या के संभावित तारों की संख्या को गिनना है जैसे कि सभी आसन्न वर्णों में एएससीआई मानों के बीच अंतर हो 1.
अगर संख्या 2 है तो स्ट्रिंग्स "ab", "ba", "bc", "cb", ……..yz", "zy" होंगी।
आइए उदाहरणों के साथ समझते हैं
इनपुट - संख्या=3
आउटपुट - स्ट्रिंग्स की संख्या जहां आसन्न वर्ण एक अंतर के हैं - 98
स्पष्टीकरण - कुछ नमूना स्ट्रिंग हैं:"abc", "aba", "cde"…..xyx", "zyz", "xyz"।
इनपुट - संख्या=2
आउटपुट - स्ट्रिंग्स की संख्या जहां आसन्न वर्ण एक अंतर के हैं - 50
स्पष्टीकरण - कुछ सैंपल स्ट्रिंग्स हैं:"ab", "ba", "cd" …...xy", "zy", "yz"।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
लंबाई के लिए =2.
a=“ab” से शुरू होने वाली स्ट्रिंग
बी ="बीए", "बीसी" से शुरू होने वाली स्ट्रिंग्स
c="cd", "cb" से शुरू होने वाली स्ट्रिंग्स............
लंबाई के लिए =n.
ए से शुरू होने वाला स्ट्रिंग =लंबाई के स्ट्रिंग्स की संख्या के तरीके n-1 बी से शुरू होता है
b से शुरू होने वाली स्ट्रिंग =लंबाई n-1 के स्ट्रिंग्स की संख्या के तरीके a या c से शुरू होते हैं
c से शुरू होने वाली स्ट्रिंग =लंबाई n-1 के स्ट्रिंग्स की संख्या के तरीके जो b या d से शुरू होते हैं
हम इसे गतिशील प्रोग्रामिंग का उपयोग करके हल करेंगे।
एक सरणी गिरफ्तार करें [संख्या + 1] [27]। एआर [i] [जे] में वर्णमाला संख्या जे से शुरू होने वाली लंबाई के कई तार शामिल हैं। सभी arr[1][j] स्ट्रिंग्स "a", "b"..."z" के लिए 1 होंगे।
गिरफ्तारी के लिए आराम करें [2 से संख्या + 1] [0 से 25], गिरफ्तारी सेट करें [i] [j] =गिरफ्तारी [i-1] [j + 1] j =0 के लिए। एल्स एरर सेट करें[i][j] =arr[i-1][j-1] + arr[i-1][j+1];
परिणाम संख्या-वें पंक्ति गणना का योग होगा।
-
इनपुट पूर्णांक संख्या लें
-
फ़ंक्शन अंतर_स्ट्रिंग्स (इंट नंबर) संख्या लेता है और स्ट्रिंग्स की गिनती देता है जहां आसन्न वर्ण अंतर के होते हैं
-
प्रारंभिक गणना 0 के रूप में लें।
-
सभी 0s के साथ arr[num + 1][27] प्रारंभ करें।
-
सभी 1 के साथ arr[1][0 to 25] प्रारंभ करें।
-
ट्रैवर्स 2डी सरणी एआर [] [] पंक्ति 2 से अंतिम तक दो लूप के लिए और सभी 26 अक्षरों के लिए कॉलम 0 से 25 का उपयोग करके।
-
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 to 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