【py交易】算法竞赛入门经典6.3.1 小球下落 python

题目：

分析：
1.深度为D的开关二叉树共有2^D -1 个开关，从上到下，从做到右排序1,2,3,…,2^D-1
2.最开始，这课开关二叉树上的所有开关都是关闭状态，假设为off状态，当有一个小球经过以后，开关由off状态变为on状态
3.举个例子（不举），假设D=4，则共有15个开关，顺序如图上。
1）第一个小球下落的时候，首先经过开关1，因为开关1是off状态，所以小球往左走，开关1 的状态变为on
2）小球到达2，因为开关2的状态是off，所以小球往左走，开关2的状态变为on
3）小球到达4，因为开关4的状态是off，所以小球往左走，开关4的状态变为on
4）小球到达8，走不了了，则第一个小球的终点就是8号开关
5）第二个小球，首先经过开关1，因为开关1是on状态，所以小球往右走，开关1变为off，
。。。
n）第二个小球抵达12号开关
4.每个小球都要经过开关1，所以遍历的时候需要设一个临时的变量k，记录小球走的开关号
5.若是小球从一个off的开关m经过,则下一步就是王左走，即2m号开关，否则走向2m+1号开关
6.小球最大编号不能超过2^D-1，小球走到某个开关以后，会把开关需要翻倍（2m或者2m+1），所以小球最终所在的开关需要要除以2

code below：

# coding=utf-8
import math
D = 4
I = 2

n = int(round((math.pow(2,D))-1))#2^D-1

s = {}

def reverseRes(num):
    if num == 1:
        return 0
    elif num == 0:
        return 1

"初始化所有开关"

for index in range(1,n,1):
    s[index] = 0 #所有开关都关闭

for index in range(1,I+1,1):#遍历每个小球
    k = 1#需要一个辅助的编号，因为小球每次都是从第一个开关经过的
    while 1:
        s[k] = reverseRes(s[k]) #小球经过的开关改变
        if s[k] == 1:#小球经过以后，开关打开了，说明经过之前是闭合的，所以往左走
            k = 2*k
        else:
             k = 2*k+1
        if k > n:
            break
print k/2

更简便的方法：

更多相关文章

随机推荐