算法的流程可以看這個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新聞熱點
疑難解答
