知乎上小米變相約瑟夫環面試題微軟解法的py代碼

#coding=utf-8

# py_15243
# """小米java算法題，變相約瑟夫環"""

# """取一個1～n的數組，這裡為了說明取n=5。按照題目中的規則變換，得到數組：[1 3 5 4 2]，将該數組下标與值互換得到[1 5 2 4 3]，即為答案。解釋：[1 3 5 4 2]的意義是，經過變換，原數組中3号位置的數字現在2号槽，原數組中5号位置的數字現在3号槽... 現在已知變換後的槽存放的是1～n，故隻需将下标與值互換即可得到待求數組。"""

"""疑問：可直接通過數學規律計算麼？應該可以！ 但是起頭數規律不穩定，或者我看不出規律
   首先奇數按順序，到結束；
   偶數2起頭+4，到結束； X2
   偶數4起頭+8，到結束； X2
   偶數8起頭+16，到結束； X4
   偶數32起頭+32，到結束； X24
   偶數16起頭+64，到結束； X-16
   偶數48起頭+128，到結束； X32
   偶數112起頭+256，到結束； X64
"""

def make_array(n):
    '''按數字量構成順序數組'''
    r = []
    for i in range(1, n + 1):
        r.append(i)
    return r

def count_mid_array(array):
    '''計算中間數組'''
    new_array = []
    while len(array) > 1: # 監控數組長度執行，最後一個直接加入
        t1 = array[0] # 取得第一個
        t2 = array[1] # 取得第二個
        new_array.append(t1) # 第一個加入中間數組
        array.remove(t1) # 移除第一個
        array.remove(t2) # 先移除第二個
        array.append(t2) # 再将第二個的副本插入本數組末尾
        # print(array) # 監控列印，可以注釋
    new_array.append(array[0]) # 最後一個直接加入中間數組
    print(new_array)
    return new_array

def trans_array(n, new_array):
    '''将中間數組轉換成結果數組'''
    fin_array = []
    for i in range(1, n + 1): # 一個n循環
        for a in enumerate(new_array, 1): # 取中間數組的值和索引
            if i == a[1]: # 下面是對比值
                fin_array.append(a[0]) # 把索引加入結果數組
                break # 找到了就離開這輪内層循環
    return fin_array

def joseph(n):
    '''主體程式'''
    sou = make_array(n)
    temp = count_mid_array(sou)
    fin = trans_array(n, temp)
    return fin


j = joseph(12)
print(j)

           

版權聲明：本文為CSDN部落客「weixin_33849942」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。

原文連結：https://blog.csdn.net/weixin_33849942/article/details/91965165