नंबर खोजें। राशि प्राप्त करने की n n से भी कम समय सभी सकारात्मक पूर्णांकों के साथ तरीकों की

Question

दी गई संख्या के लिए एन, का कहना है कि 2 कितने तरीकों से हम एक योग 2 नंबर का उपयोग कम है कि 2.

1+1 = 2 
so, for 2 - just 1 way. 

n = 3 
1+1+1=3 
1+2=3 
so,for 3 - it is 2 ways 
n = 4 
1+1+1+1=4 
1+1+2=4 
1+3=4 
2+2=4 

so, for 4 - it is 4 ways 

वहाँ एक हो सकता है प्राप्त कर सकते हैं इस सवाल के लिए सामान्य पैटर्न/समाधान?

Answer 1

यह Partition Problem के रूप में जाना जाता है और आप संदर्भित लिंक में विस्तार देख सकते हैं। विकी है:

विभाजन समारोह पर एक हैंडल होने का

एक तरह से एक मध्यवर्ती समारोह p (k, n) है, जो केवल प्राकृतिक संख्या के रूप में कम से कम के रूप में बड़े का उपयोग कर n के विभाजन की संख्या का प्रतिनिधित्व शामिल है कश्मीर। कश्मीर की किसी भी मूल्य, p (k, एन) द्वारा गिना विभाजन के लिए बिल्कुल निम्नलिखित श्रेणियों में से एक में फिट:

smallest addend is k 
smallest addend is strictly greater than k. 

पहली शर्त बैठक विभाजन की संख्या p (k, n है - कश्मीर)। इसे देखने के लिए, संख्या n-k के सभी विभाजनों की सूची को कम से कम के आकार में कल्पना करें, फिर सूची में प्रत्येक विभाजन में "+ के" संलग्न करने की कल्पना करें। अब यह एक सूची क्या है? एक तरफ ध्यान दें के रूप में, एक p (k है,

1+ sum{k=1 to floor (1/2)n} p(k,n-k) = p(n), 

दूसरी शर्त बैठक विभाजन की संख्या मध्यवर्ती समारोह की अवधि में विभाजन समारोह के लिए प्रत्यावर्तन संबंध का एक तरह परिभाषित करने के लिए अर्थात् इसका उपयोग कर सकते + 1, एन) के बाद से कम से कम कश्मीर के कुछ हिस्सों में एक विभाजन है कि वास्तव में कश्मीर का कोई भागों में कम से कम k + 1.

के बाद से दो शर्तों परस्पर अनन्य हैं, विभाजन की संख्या बैठक सभी भागों होना आवश्यक है या तो स्थिति पी है (के + 1, एन) + पी (के, एन - के)। रिकर्सिवली परिभाषित समारोह इस प्रकार है:

p(k, n) = 0 if k > n 

p(k, n) = 1 if k = n 

p(k, n) = p(k+1, n) + p(k, n − k) otherwise. 

वास्तव में आप, memoization द्वारा सभी मूल्यों की गणना कर सकते हैं अतिरिक्त पुनरावर्ती कॉल से रोकने के लिए।

संपादित करें: unutbu उसकी टिप्पणी में उल्लेख किया है, पिछले पर आप 1 से उत्पादन यह है, वास्तव में सभी P मूल्यों विकि कड़ी के रूप में गणना की जाएगी करने के लिए परिणाम घटाना चाहिए, लेकिन अंत में जब आप उत्पादन परिणाम चाहते हैं, आपको इसे 1 द्वारा घटाना चाहिए।