17

そのため、Python でブロック スワップ アルゴリズムを実装しています。

私がフォローしているアルゴリズムは次のとおりです。

A = arr[0..d-1] および B = arr[d..n-1] を初期化します。 1) A のサイズが B のサイズと等しくなるまで、以下を実行します。

a) A が短い場合、Br が A と同じ長さになるように、B を Bl と Br に分割します。A と Br を入れ替えて、ABlBr を BrBlA に変更します。A は最終的な場所にあるので、B の部分を繰り返します。

b) A が長い場合、Al が B と同じ長さになるように A を Al と Ar に分割し、Al と B を交換して、AlArB を BArAl に変更します。これで B は最終的な場所にあるので、A の部分を繰り返します。

2) 最後に、A と B が同じサイズになったら、それらをブロック交換します。

同じアルゴリズムがこの Web サイトの C で実装されています - Array Rotation

同じための私のpythonコードは

a = [1,2,3,4,5,6,7,8]

x = 2

n = len(a)


def rotate(a,x):
    n = len(a)

    if x == 0 or x == n:
        return a

    if x == n -x:
        print(a)
        for i in range(x):
            a[i], a[(i-x+n) % n] = a[(i-x+n) % n], a[i]
        print(a)
        return a

    if x < n-x:
        print(a)
        for i in range(x):
            a[i], a[(i-x+n) % n] = a[(i-x+n) % n], a[i]
        print(a)
        rotate(a[:n-x],x)
    else:
        print(a)
        for i in range(n-x):
            a[i], a[(i-(n-x) + n) % n] = a[(i-(n-x) + n) % n] , a[i]
        print(a)
        rotate(a[n-x:], n-x)

rotate(a,x)
print(a)

各段階で正しい値を取得していますが、再帰関数呼び出しが期待される結果を返さず、原因を理解できないようです。誰かが私の再帰の何が悪いのか説明できますか? そして可能な代替案は何ですか。

4

11 に答える 11

9

大きな値の k (ここで、k は回転数) に対して右回転と左回転が必要であるという問題が見つかったので、任意のサイズの k に対して次の関数を実装しました。

右円回転(左から右: 1234 -> 4123):

def right_rotation(a, k):
   # if the size of k > len(a), rotate only necessary with
   # module of the division
   rotations = k % len(a)
   return a[-rotations:] + a[:-rotations]

左円回転(右から左: 1234 -> 2341):

def left_rotation(a, k):
   # if the size of k > len(a), rotate only necessary with
   # module of the division
   rotations = k % len(a)
   return a[rotations:] + a[:rotations]

ソース:

于 2018-09-02T16:39:51.423 に答える
1

a のスライスを再帰呼び出しに渡すとき、同じ変数を渡していないことを期待しています。a 全体とスライスの上限/下限を追加の引数として関数に渡してみてください。

たとえば、次の関数を検討してください。

def silly(z):
  z[0] = 2

私はちょうど次のことを試しました：

>>> z = [9,9,9,9,9,9]
>>> silly(z)
>>> z
[2, 9, 9, 9, 9, 9]
>>> silly(z[3:])
>>> z
[2, 9, 9, 9, 9, 9]

スライスへの変更が完全な配列によって保持されていないことがわかる場所

好奇心から、どのような出力が得られ、どのような出力が期待されますか?

于 2013-06-27T18:25:19.077 に答える
0

配列の回転:-

print("Right:1,Left:2")
op=int(input())
par=[1,2]
if op not in par:
   print("Invalid Input!!")
   
else:  
  arr=list(map(int,input().strip().split()))
  shift=int(input())
  if op ==1:
    right=arr[-shift:]+arr[:-shift]
    print(right)
  elif op==2:
    left=arr[shift:]+arr[:shift]  
    print(left)

出力:-`

Right:1,Left:2
1
12 45 78 91 72 64 62 43
2
[62, 43, 12, 45, 78, 91, 72, 64]`
于 2021-08-12T09:42:21.817 に答える
0

deque または slicing を使用しない場合:

def rotate(array: List[int], k: int) -> List[int]:
    # loop through the array from -k to array_size - k
    return [array[i] for i in range(-k, len(array) - k)]
于 2022-01-24T12:01:11.000 に答える