0

下に「test」という関数があります。私のプログラムはテスト関数に合格できません。

これは三項検索の私のコードです。三分探索は二分探索に似ていますが、すべての要素を 2 で割るのではなく、3 で割ります。

三項検索を使用するために、アイテムの 1/3 の分割に index2 を使用しました。index1 は、アイテムの 2/3 の分割線です。

「高」と「低」を index1 または index2 に割り当てるだけです。これにより、リストを 3 つの部分に分割できます。ハイとローは、分割されたリストのどの部分を検索するかを見つけるために機能します。次に、高値と低値が互いに近づくまで、このプロセスが繰り返されます。

seq はリスト内の項目です。[1,2,3,4,5...] リストの項目は順番に並んでいます。

キーは私が探している値です

および ternary_search は、キーのインデックスまたはキーに近い数値のインデックスを返します

楽しむ！乾杯！

def ternary_search(seq,key):
    length = len(seq)
    left = 0
    right = length
    index = 0
    x = True
    while x and left <= right:
        #focal = (high + low) //3

        if left == right:
            #check similarity between values and key
            return index
        else:
            if right - left > 0:
                index1 = ((right+2*(left))//3)
                index2 = ((2*(right)+left)//3)
                if left == right:
                    x = False
                    return (index1+index2)
                if seq[index1] == key:
                    x = False
                    return index1
                if seq[index2]== key:
                    x = False
                    return index2
                if key<seq[index1]:
                        right = index1 - 1
                else:
                    if key > seq[index1] and key <seq[index2]:
                        right = index2 - 1
                        left = index1 - 1
                    if key > seq[index2]:
                        left = index2+1

    return index

def test():
    seq = []
    for i in range(1,1001):
        seq.append(i)
    for j in range(1,1001):
        is_pass = (ternary_search(seq,j)==j-1)
        assert is_pass == True, "fail the test when key is %d"%j
    if is_pass == True:
        print("=========== Congratulations! Your have finished exercise 2! ============")
if __name__ == '__main__':
    test()
4

2 に答える 2

0

あなたのエラーは次の行にあります：

if left == right:
#check similarity between values and key
return index

基本的に現在、上下の値 (右と左) が一致すると、変数 index に格納された値が返されますが、関数の本体では index の値を決して変更しないため、常に 0 が返されます。あなたのコードは、左==右を確認して値==キーかどうかを確認し、その場合は左または右のいずれかを返します。両方がその値のインデックスでなければならないためです。私はあなたのコードでこれを行い、テスト関数に合格しました。ところで、ラボ 8 で頑張ってください。

于 2013-03-12T15:30:39.067 に答える
0 
def ternary_search(seq,key):
  length = len(seq)
  left = 0
  right = length
  index = 0
  x = True
  while x and left <= right:
    #focal = (high + low) //3
    if left == right:
        #check similarity between values and key
        return left 

    elif right - left > 0:
        index1 = ((right+2*(left))//3)
        index2 = ((2*(right)+left)//3)
        if seq[index1] == key:
            return index1
        elif seq[index2] == key:
            return index2
        else:
            if key<seq[index1]:
                    right = index1 - 1
            elif key > seq[index1] and key <seq[index2]:
                    right = index2 - 1
                    left = index1 - 1
            elif key > seq[index2]:
                    left = index2+1

return index

ところで、ラボ 8 で頑張ってください。

于 2013-03-12T21:17:58.040 に答える