डेलानॉय नंबर - एक डेलानॉय नंबर D एक आयताकार ग्रिड में दक्षिण-पश्चिम कोने (0,0) से उत्तर-पूर्व कोने (a,b) तक केवल अनुमत चरणों पूर्व ( → ), उत्तर-पूर्व ( ↗ ) और उत्तर ( ↑ ) का उपयोग करके पथों की संख्या दर्शाता है।
इस प्रकार, हम कह सकते हैं कि एक पुनरावृत्ति संबंध है,
D(a,b) = D(a-1,b) + D(a, b-1) + D(a-1, b-1) जहां D(0,0)=1।
उदाहरण के लिए, डेलानॉय नंबर D(3,3) 63 के बराबर है।
डेलानॉय नंबर ढूंढने का एल्गोरिदम
- दो कोऑर्डिनेट्स (a,b) को इनपुट के रूप में लें।
- एक पूर्णांक फ़ंक्शन generateDelannoy(int a, int b) जो कोऑर्डिनेट्स 'a' और 'b' को इनपुट के रूप में लेता है।
- बेस केस में, हम जांचेंगे कि क्या कोऑर्डिनेट्स 'a' और 'b' शून्य हैं तो 1 लौटाएं।
- अन्य मामले में डेलानॉय नंबर उत्पन्न करें और डेलानॉय नंबर उत्पन्न करने के लिए पुनरावृत्ति संबंध D(a-1,b) + D(a,b-1) + D(a-1,b1) का उपयोग करके परिणाम लौटाएं।
उदाहरण
#include<iostream>
using namespace std;
int generateDelannoy(int a, int b){
int d=1;
if((a==0) || (b==0)){
d=1;
} else {
d = generateDelannoy(a-1,b) + generateDelannoy(a,b-1) + generateDelannoy(a-1,b-1);
}
return d;
}
int main(){
int a=3;
int b=3;
int result=0;
result= generateDelannoy(a,b);
cout<<result<<endl;
}
आउटपुट
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
63
दिए गए पॉइंट्स (a,b) = (3,3) के लिए, पुनरावृत्ति संबंध D(a-1,b) + D(a,b-1) + D(a-1,b-1) का उपयोग करके डेलानॉय नंबर '63' आउटपुट के रूप में उत्पन्न होगा।
