知乎上小米变相约瑟夫环面试题微软解法的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