0

私はpyhtonでカウント反転のプログラムを作成し、同じためにpython27を使用しています。分割統治法（マージソートトリック）を使用してアルゴリズムを実装しました。私のプログラムは、サイズが 100 までの入力配列に対して正常に実行されます (これは、確認できる最大値です)。今、サイズ 50,000 と 1,00,000 の入力配列でプログラムをテストしましたが、正しい答えを得ることができませんでした。以下にコードを貼り付けました。間違いの可能性がある場合はご指摘ください。

    f=open('forum.txt')
    a=[]
    s=1
    for line in f:
        a.append(line)





def CountInversion(IntegerArray):
_count=0
lc=0
rc=0
RightArray=[]
LeftArray=[]
if len(IntegerArray)>1:
        LeftArray,lc=CountInversion(IntegerArray[:len(IntegerArray)/2])
        RightArray,rc=CountInversion(IntegerArray[len(IntegerArray)/2:])
elif len(IntegerArray)==1:
    return IntegerArray,0
ResultArray=IntegerArray
i=0
l=len(ResultArray)
j,k=0,0
for i in range(0,l):
    if j<len(RightArray) and k<len(LeftArray):
        if RightArray[j]<LeftArray[k]:
            ResultArray[i]=RightArray[j]
            j += 1
            a=(len(LeftArray)-k)
            _count = _count + a    
        else:
            ResultArray[i]=LeftArray[k]
            k += 1
elif j<len(RightArray):
    ResultArray[i]=RightArray[j]
        j += 1
elif k<len(LeftArray):
        ResultArray[i]=LeftArray[k]
        k += 1          
return ResultArray,(_count+lc+rc)

arr,b=CountInversion(a)

print ('end of inversions')

print b

この投稿でJF Sebastian によって提供されたコードも実行しましたが、結果は同じです (小さな入力に対しては正しい回答ですが、サイズが 50000 または 1,00,000 の入力配列に対しては正しくありません)。

4

2 に答える 2

0

この問題は、文字列を int に解析して配列に入力することで解決されます

于 2013-10-01T19:57:42.990 に答える
0

最初の問題は、一貫性のないインデントがあることです。数行で、スペースの代わりにタブを使用していますが、これは非常に悪い考えです。Python ではインデントが重要なため、注意しないと簡単にエラーが発生します。

あなたが抱えていると思う2番目の問題は、数値ではなく文字列を比較していることです。Python は文字列を完全にソートできますが、文字列としてエンコードされた整数に適用すると予期しない辞書式の orering を使用します。たとえば、ASCII 文字セット (および Unicode) では最初の文字が前に来るため"11"、文字列は string より前に並べ替えられます。"2"12

コメントで尋ねたように、コードが正しく機能していないと判断する方法が明確ではありません。上記の問題を修正するだけで、発生している問題が解決する場合があります。そうでない場合は、結果が無効であると判断した理由を説明してください。さらに提案を加えてこの投稿を更新しようと思います。

于 2013-02-09T03:48:53.287 に答える