तो मेरे पास यह सूत्र है:
P(n, 1) = P(n, n) = 1
P(n + k, k) = P(n, 1) + P(n, 2) + ... + P(n, k)
लेकिन मुझे यह समझ में नहीं आ रहा है।
क्या मैंने कुछ गलत लिखा? मुझे समझ में नहीं आता कि P(n + k, k) में "n+k" क्यों है
मान लीजिए कि P एक फंक्शन है और मैं P(6, 2) को कॉल करता हूं। P(n + k, k) क्या करता है? क्या यह P(8, 2) या P(4 + 2, 2)...
मुझे समझ में नहीं आता कि यह कैसे काम करता है, हो सकता है कि कोई मुझे एक उदाहरण देता है, कदम से कदम ...
2 जवाब
दो सूत्र रेखाएं गणितीय परिभाषा हैं, प्रोग्रामिंग एल्गोरिदम नहीं। और उम्मीद है कि वे पर्याप्त जानकारी प्रदान करते हैं ताकि आप किसी भी P(x,y) के लिए मूल्य का पता लगा सकें।
चूंकि पहली पंक्ति दो अलग-अलग मामलों को प्रभावी ढंग से परिभाषित करती है, इसलिए मैं सूत्रों को फिर से लिखना चाहता हूं:
(A) P(n, 1) = 1
(B) P(n, n) = 1
(C) P(n + k, k) = P(n, 1) + P(n, 2) + ... + P(n, k)
इसलिए, यदि आप उन्हें P(6,2) पर लागू करना चाहते हैं तो केवल (C) मेल खा सकते हैं, क्योंकि (A) केवल P(6,1), और (B) जैसी चीजों से मेल खाता है। P(6,6).
P(6,2) के विरुद्ध P(n+k,k) के मिलान का अर्थ है कि k 2 होना चाहिए, और n+k 6 होना चाहिए, जिससे n=4 मिलता है।
फिर (C) के दाहिने हाथ का विस्तार P(4,1) + P(4,2) तक हो जाता है। इसका पहला भाग (A) से मेल खाता है, और दूसरा भाग (C) से मेल खाता है। तो, पहला भाग 1 देता है, और दूसरे भाग को P(6,2) की तरह ही विस्तारित करना होता है। और इसी तरह...
यदि आप P(x,y) मानों की गणना करने वाले फ़ंक्शन को लागू करना चाहते हैं, तो परिभाषा सूत्रों को पुनरावर्ती गणना में बदलने का सीधा तरीका होगा।
ठीक है, आपको बार-बार सूत्र लागू करने होंगे:
P(6, 2) = P(4 + 2, 2) = P(4, 1) + P(4, 2)
अब P(4, 1) के लिए हमारे पास है
P(4, 1) = P(3 + 1, 1) = P(3, 1) = P(2 + 1, 1) = P(2, 1) = P(1 + 1, 1) = P(1, 1) = 1
प्रेरण की सहायता से हम यह सिद्ध कर सकते हैं कि P(N, 1) = 1 जब N >= 1
P(4, 2) के लिए हमारे पास है
P(4, 2) = P(2 + 2, 2) = P(2, 2) + P(2, 1) = 1 + P(2, 1) =
= 1 + P(1 + 1, 1) = 1 + P(1, 1) = 1 + 1 = 2
आखिरकार
P(6, 2) = P(4 + 2, 2) = P(4, 1) + P(4, 2) = 1 + 2 = 3
सामान्य स्थिति में (फिर से प्रेरण) P(2 * N, 2) = N
सबसे आसान C# कार्यान्वयन (कुछ इनपुट के लिए काम नहीं करता, जैसे P(0, 1)):
private static Dictionary<Tuple<int, int>, int> s_Cached =
new Dictionary<Tuple<int, int>, int>();
private static int P(int n, int k) {
if (n == k)
return 1;
if (s_Cached.TryGetValue(new Tuple<int, int>(n, k), out var value))
return value;
int result = 0;
for (int i = 1; i <= k; ++i)
result += P(n - k, i);
s_Cached.Add(new Tuple<int, int>(n, k), result);
return result;
}
परीक्षण
Console.WriteLine(P(6, 2));
संबंधित सवाल
नए सवाल
algorithm
एक एल्गोरिथ्म अच्छी तरह से परिभाषित चरणों का एक क्रम है जो एक समस्या के सार समाधान को परिभाषित करता है। जब आपकी समस्या एल्गोरिथम डिज़ाइन से संबंधित हो तो इस टैग का उपयोग करें।