5

私は現在 edx でプログラミング コースを行っています。私の指示は次のとおりです。二分探索のアイデアを使用して、文字列がアルファベット順である限り、文字列内に文字が含まれているかどうかをチェックする再帰アルゴリズムを記述します。私のコード(python 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)

私の説明: まず、文字列の真ん中の文字を見つけることから始めます。文字と等しい場合は False を返します。文字と等しくない場合は、文字が中央の文字よりも低いかどうかを確認し、再帰関数を使用してスタックを作成し、最終的に真のブール値を返します。中間の文字を含めたくないので、-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
4

4 に答える 4

6

関数が返されることTrueはありません。私はそれが返されるべきだと思うTrueので、 （返されている）char == mからそれを削除して、別のに置くことができます：if-clauseFalseif

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

isInまた、定義されていないメソッドを呼び出しています。を再帰的に呼び出したかったと思いますisitIn。

比較後char < m、文字列を「二等分」char > mする必要があるため、 no を実行せず、代わりに (再帰呼び出しで) 文字列の「半分」を渡します。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)
于 2014-01-14T04:44:18.737 に答える
5

全体として、あなたのコードはかなり良さそうです。しかし、私はあなたの最初の if ステートメントを詳しく見ていきます。特に、文字が中央の文字と等しいかどうかを確認しています。あなたのキャラクターが真ん中のキャラクターと同じだったら、何を返したいですか?

また、アルゴリズムがすべてのパスに到達できることを確認する必要があります。関数から True が返されるのはどのような条件ですか?

于 2014-01-14T04:46:28.783 に答える