python - वर्ण की स्ट्रिंग में है या नहीं, यह जांचने के लिए रिकर्सिव बाइसेक्शन एल्गोरिथ्म का उपयोग करना




recursion bisection (3)

मैं वर्तमान में एडीएक्स में प्रोग्रामिंग कोर्स कर रहा हूं और मेरे निर्देश इस प्रकार हैं: द्वितरण खोज के विचार का इस्तेमाल करना, एक रिकर्सिव एल्गोरिथम लिखना, जो एक स्ट्रिंग के भीतर एक वर्ण शामिल है, जब तक कि स्ट्रिंग वर्णमाला क्रम में है। मेरा कोड (अजगर 2.7) यहां है:

def isitIn(char, aStr):
   m = aStr[len(aStr) // 2]
   if aStr == '' or len(aStr) == 1 or char == m:
      return False
   else:
      if char < m:
         return isitIn(char, aStr[:-1])
      elif char > m:
         return isitIn(char, aStr[1:])
   return isitIn(char, aStr)

मेरा स्पष्टीकरण: मैं पहली बार स्ट्रिंग के मध्य चरित्र को खोजने के द्वारा शुरू करते हैं। यदि यह चरित्र के बराबर है, तो वह गलत है। यदि यह चरित्र के बराबर नहीं है, तो यह जांचता है कि क्या चरित्र मध्य चरित्र से कम है, और फिर स्टैक्स बनाने के लिए रिकर्सिव फ़ंक्शन का उपयोग करके और अंततः ट्रू के बूलियन मान को वापस लौटाता है। अब मैंने -1 और 1 सूचकांक का इस्तेमाल किया, क्योंकि मैं मध्य चरित्र को शामिल नहीं करना चाहता था।

एक समाधान के बजाय, मुझे संकेत मिलेगा क्योंकि मैं अभी भी इसे समझने की कोशिश कर रहा हूं, लेकिन एक अलग दृष्टिकोण कभी दर्द नहीं होता है। धन्यवाद!

Error message:
Test: isIn('a', '')
Your output:
Traceback (most recent call last):
File "submission.py", line 10, in isIn
m = aStr[len(aStr) // 2]
IndexError: string index out of range
Correct output:
False

कुल मिलाकर, आपका कोड बहुत अच्छा दिखता है। लेकिन मैं अपने पहले अगर बयान पर एक करीब से देखो ले जाएगा विशेष रूप से, आप देख रहे हैं कि क्या चार मध्य के बराबर है। अगर आपका चरित्र मध्य चरित्र के बराबर था, तो आप क्या लौटना चाहते हैं?

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


फ़ंक्शन कभी True नहीं लौट रहा है मुझे लगता है कि इसे True करना चाहिए जब char == m , तो आप if-clause ( False ) से हटा सकते हैं (जो False लौट रहा है) और इसे दूसरे में डाल दिया है if :

if char == m:
   return True
elif aStr == '' or len(aStr) == 1:
    return False
else:
    ...

इसके अलावा, आप isIn विधि बुला रहे हैं जो परिभाषित नहीं है। मुझे लगता है कि आप लगातार isitIn कॉल करना चाहते हैं।

char < m और char > m तुलना करने के बाद, आपको स्ट्रिंग " return isitIn(char, aStr[:-1]) " करना चाहिए, इसलिए return isitIn(char, aStr[:-1]) न करें और न ही return isIn(char, aStr[1:]) , इसके बजाय पास करें ( रिकर्सिव कॉल में) स्ट्रिंग का "आधा"

if char < m:
    return isitIn(char, aStr[:len(aStr) // 2])
elif char > m:
    return isitIn(char, aStr[len(aStr) // 2:])

संपादित करें: बस के मामले में, मैंने कोशिश की है कि कोड है:

def isitIn(char, aStr):
    if aStr == '':  # Check for empty string
        return False
    m = aStr[len(aStr) // 2]
    if char == m:
       return True
    elif len(aStr) == 1:
        return False
    else:
       if char < m:
           return isitIn(char, aStr[:len(aStr) // 2])
       elif char > m:
           return isitIn(char, aStr[len(aStr) // 2:])
    return isitIn(char, aStr)

यह भी काम करता है थोड़ा छोटा भी:

def isIn(char, aStr):
    if len(aStr)==0:
        return False
    elif len(aStr)==1:
        return char == aStr
    elif char == aStr[len(aStr)//2]:
        return True
    else:
        if char < aStr[len(aStr)//2]:
            return isIn(char, aStr[0:len(aStr)//2])
        elif char > aStr[len(aStr)//2]:
            return isIn(char, aStr[len(aStr)//2:]) 
    return isIn(char, aStr)




bisection