Python高手如何破解Google的面试题代码

2019-11-08 02:15:02

字体：大中小

来源：转载

供稿：网友

算法的流程可以看这个Python高手如何破解Google的面试题

问题的描述：假设两个桶容量任意，比如X斤和Y斤,目标是Z斤;要求写出算法

python 代码（原创）：

def init(X,Y): return set([(0,0),(0,Y),(X,0)])def change(x,y,X,Y): #fill A,fill B,empty A,empty B,A-B,B-A sets = [(X,y)] sets.append((x,Y)) sets.append((0,y)) sets.append((x,0)) if x+y >= Y: sets.append((x-Y+y,Y)) else: sets.append((0,y+x)) if x+y >= X: sets.append((X,y-X+x)) else: sets.append((y+x,0)) return setsdef main_function(X,Y): state_change = {} state_all = init(X,Y) for temp in state_all: state_change[temp] = (0,0) state_now = init(X,Y) while len(state_now) != 0: state_next = set([]) for i in state_now: state_i = change(i[0],i[1],X,Y) #PRint i for j in state_i: if j not in state_all: state_all.add(j) state_next.add(j) state_change[j] = i state_now = state_next return state_changedef get_target(Target, state_change): target = 0 if (Target,0) in state_change.keys(): target = (Target,0) else: if (0,Target) in state_change.keys(): target = (0,Target) if target == 0: return [] ways = [target] #print ways while target != (0,0): ways.append(state_change[target]) target = state_change[target] return waysX = 4Y = 9Target = 6state_change = main_function(X,Y)ways = get_target(Target, state_change)print ways

上一篇：Python入门（三）：dict和set类型

下一篇：Python学习之[1]——列表