रिकर्सन

Question

का उपयोग कर सूची में दूसरा सबसे छोटा नंबर खोजें मुझे पता है कि इस विषय पर एक प्रश्न पूछा गया है, लेकिन किसी भी उत्तर ने मेरी मदद नहीं की है। मुझे कोड को लागू करने में मदद की ज़रूरत नहीं है, मुझे इसके लिए रिकर्सिव प्रक्रिया के माध्यम से छंटनी में मदद की ज़रूरत है।

मैं मूल रूप से सोच रहा था कि प्रत्येक स्तर पर एक ट्यूपल लौटाएं और दूसरा सबसे छोटा मूल्य ढूंढने की तुलना करें। लेकिन यह काम नहीं करता है क्योंकि मैं चाहता हूं कि मेरा कार्य केवल अंत में 1 मान लौटाए- दूसरा सबसे छोटा मूल्य।

मैं इस समस्या के लिए पुनरावर्ती प्रक्रिया के बारे में कैसे जाऊं? धन्यवाद!

संपादित करें: पर्याप्त विवरण सहित शामिल होने के बारे में क्षमा करें, इसलिए यहां जाता है।

समारोह के रूप में काम करना चाहिए इस प्रकार है:

>>> sm([1,3,2,1,3,2]) 
>>> 2 

दूसरा संपादित करें: देरी के लिए क्षमा करें, मैं व्यस्त था अब तक, अंत में बैठ जाओ और डाल मैं क्या कोड में मन में था करने में सक्षम था। यह इरादे के रूप में काम करता है, लेकिन मैं ईमानदारी से सोचता हूं कि यह रिकर्सन करने का एक बहुत ही शर्मनाक और अक्षम तरीका है, क्योंकि आप शायद बता सकते हैं कि मैं अवधारणा के लिए नया हूं।

नीचे दिए गए छद्म कोड का उपयोग करके मेरे मूल प्रश्न को फिर से भरने के लिए: क्या मैंने ऐसा किया है जो मैंने किया था, लेकिन इसे दूसरे फ़ंक्शन में लपेटने के बिना? यही है, क्या यह एक ऐसा कार्य होना संभव है जो केवल अपने आप को कॉल करता है, और 1 नंबर लौटाता है- दूसरा सबसे छोटा नंबर?

def second_smallest(list): 
    def sm(list): 
     if base case(len of list == 2): 
      return ordered list [2nd smallest, smallest] 
     else: 
      *recursive call here* 
      compare list[0] with returned ordered list 
      eg: [3, [5,2]] 
      re-arrange, and return a new ordered list 
      [3,2] 
    return sm(list)[0] 

Answer 1

आप 3 तर्क लेने के लिए अपना रिकर्सिव फ़ंक्शन लिख सकते हैं: अब तक का पहला और दूसरा सबसे छोटा मूल्य, और शेष सूची, जिसकी आपने जांच नहीं की है।

फिर, सूची तर्क के पहले तत्व की तुलना दो सबसे छोटी-दूर तक की तुलना करके, आप चुन सकते हैं कि 3 में से कौन सा 2 अगले रिकर्सन के तर्क के रूप में पास हो।

आपको एक प्रस्तुति समारोह में इस रिकर्सिव फ़ंक्शन को लपेटने की आवश्यकता है, जो दो तत्वों से कम सूचियों जैसे मामलों को संभालने के दौरान, रिकर्सिव एक को सेट करता है और कॉल करता है।

def recurse(min1, min2, list): 
    if len(list)==0: 
     return min2 
    first, rest = list[0], list[1:] 
    if first < min1: 
     return recurse(first, min1, rest) 
    if first < min2: 
     return recurse(min1, first, rest) 
    return recurse(min1, min2, rest) 

def second_smallest(list): 
    if len(list) < 2: 
     raise ValueError("too few elements to find second_smallest") 
    a, b, rest = list[0], list[1], list[2:] 
    if b < a: 
     return recurse(b, a, rest) 
    else: 
     return recurse(a, b, rest) 

समाधान इस तरह की विशेष रूप से pythonic नहीं है - यह एक कार्यात्मक प्रोग्रामिंग शैली की अधिक है।

अंत में, आप सूची के मोर्चे पर बहस पारित कर सकते हैं, और दो कार्यों गठबंधन समाधान की तरह आप देख रहे हैं पाने के लिए:

def second_smallest(list): 
    if len(list) < 2: 
     raise ValueError("too few elements to find second_smallest") 
    a, b = list[0], list[1] 
    a, b = min(a,b), max(a,b) 
    if len(list) == 2: 
     return b 
    c, rest = list[2], list[3:] 
    if c < a: 
     return second_smallest([c,a]+rest) 
    if c < b: 
     return second_smallest([a,c]+rest) 
    return second_smallest([a,b]+rest) 

नोट इस समारोह कुछ बेमानी काम करता है कि , क्योंकि यह नहीं पता कि इसे पहले कहा जा रहा है, या यदि यह खुद को बार-बार कॉल कर रहा है।इसके अलावा, + एक नई सूची बनाता है, इसलिए यह कोड आकार एन की सूची के लिए ओ (एन^2) समय लेगा।

Answer 2

मैं कई तरीकों से सोच सकता हूं। धीमी बात यह है कि दी गई सूची का सबसे बड़ा मूल्य ढूंढना है, और फिर बाकी सूची में पुनरावृत्ति करना है। जब सूची की लंबाई 2 होती है, तो रिकर्सिव कॉल न करें।

सबसे तेज़ तत्व ढूंढना एक तेज़ है, सूची के शेष भाग पर दोहराएं, केवल दो बार पुनरावृत्ति करें। n इस तरह से सबसे छोटा तत्व खोजने के लिए एक दिनचर्या लिखें, और उसके बाद इसे नियमित रूप से लपेटें जो इसे n = 2 के साथ कॉल करता है।

क्या यह पर्याप्त शुरुआत है?

Answer 3

एक संभावित तरीका 3 पैरामीटर लेने के लिए एक फ़ंक्शन बनाना है: list, और वैकल्पिक smallest_value और second_smallest। फ़ंक्शन pop में पहला तत्व इसे सबसे छोटे और दूसरे सबसे छोटे से तुलना करता है और यदि आवश्यक हो तो मानों को बदलें। फिर नए list, smallest और second_smallest के साथ फ़ंक्शन को दोबारा कॉल करें। सूची खाली होने पर और दूसरा सबसे छोटा लौटने पर रिकर्सन समाप्त हो जाना चाहिए।

कुछ मुश्किल राज्य हैं (जब एक/दोनों मान अभी तक सेट नहीं हैं)। लेकिन मुझे लगता है कि यह कार्यान्वयन विवरण है और यदि आप इसे कोड करने में कोई समस्या है तो आप फिर से पूछ सकते हैं।

Answer 4

आप शास्त्रीय विभाजन और जीत का उपयोग कर सकते हैं। f(x) एक ऐसा फ़ंक्शन बनें जो एक tuple (a,b) देता है जिसमें x सूची में सबसे छोटे और अगले सबसे छोटे तत्व होते हैं।

मूल मामले तब होते हैं जब x में 0 या 1 तत्व होते हैं। आधार मामले के अलावा, 2 में सूची विभाजित है, प्रत्येक आधा से कम दो तत्वों को खोजने के लिए पुनरावृत्ति होना है, तो परिणाम के रूप में इन 4 की कम से कम 2 लेने:

def min2(x): 
    if len(x) == 0: return sys.maxsize, sys.maxsize 
    if len(x) == 1: return x[0], sys.maxsize 
    m = int(len(x)/2) 
    a1, b1 = min2(x[:m]) 
    a2, b2 = min2(x[m:]) 
    return (a1, min(b1, a2, b2)) if a1 < a2 else (a2, min(b2, a1, b1)) 

def secondSmallest(x) 
    return min2(x)[1] 

यहाँ मैं "अनंत के रूप में उपयोग कर रहा हूँ sys.maxsize । "

Answer 5

आप ट्रैक रखने के लिए ध्वज का उपयोग कर सकते हैं कि आप कॉल के सबसे बाहरी स्तर में हैं या नहीं।

def second_smallest(numbers, top_level=True): 
    # Do your stuff and call `second_smallest(numbers[1:], False)` for any recursions. 
    # When it comes to returning a value from the function, use the following. 

    if top_level: 
     return result[0] # what your function ultimately returns 
    return result   # [second, first] since you're still in recursive calls 

Answer 6

क्या मैं सवाल से समझते हैं: - 2. कोई भीतरी समारोह तरह का हैक 3. यह दूसरा सबसे छोटा लौटना चाहिए और पैरामीटर के रूप में सूची को स्वीकार इस हल करने के लिए मेरे कोड 1. समाधान पुनरावर्ती होना चाहिए -

from inspect import getouterframes, currentframe 
def second_smallest(ls): 
    level = len(getouterframes(currentframe(1))) 

    if len(ls)<2: 
     return None 
    if len(ls) == 2: 
       if level == 1: 
        return max(ls) 
       else: 
        return min(ls), max(ls) 
    else: 
     m,n = second_smallest(ls[1:]) 
     if ls[0]<=m: 
      n = m 
      m = ls[0] 
     elif ls[0] < n: 
      n = ls[0] 
     if level == 1: 
      return n 
     return m,n 

टिप्पणी - यह कोड काम करता है अगर तुम अजगर प्रोग्राम फ़ाइल के रूप में चलाने

Answer 7

आप इन पंक्तियों के साथ कुछ कर सकते हैं:

+०१२३५१६४१०

def rmin(li, n=2): 
    def _rmin(li): 
     if len(li) == 1: 
      return li[0] 
     else: 
      m = _rmin(li[1:]) 
      return m if m < li[0] else li[0] 

    a=[]   
    for i in range(n): 
     x=_rmin([e for e in set(li) if e not in a]) 
     a.append(x) 
    return x