import math def bina_search(list,item): low = 0 hight = len(list)-1 while low<=hight: #每次猜测 mid = math.floor((low + hight)/2) guess = list[mid] if guess == item: return mid if guess > item: hight = mid-1 else: low = mid+1 return None my_list = [1,3,5,7,8] print(bina_search(my_list,7))

def find_small(arry:list)->int: """  找到最小的元素  :param arry:   :return:   """ smallest = arry[0] smallest_index = 0 for i in range(1,len(arry)): if smallest>arry[i]: smallest = arry[i] smallest_index = i return smallest_index def selectionSort(arry:list)->list: """  选择排序  :param arry:   :return:   """ new_array = [] for i in range(len(arry)): smallest = find_small(arry) new_array.append(arry.pop(smallest)) return new_array print(selectionSort([5,3,6,2,10]))

def countdown1(i): print(i) countdown1(i-1) # countdown(1) def countdown2(i): print(i) if i<=1:#基线条件 return else: #递归条件 countdown2(i-1) a=countdown2(3)

def fact(x): if x==1: return 1 else: return x*fact(x-1)#塞入栈中 #fact函数没有结束

def DC(x,y): if x>y: x=x%y if x ==0:#基线条件 return y return DC(x,y) if x<y: y=y%x if y ==0: return x return DC(x,y)

#我写的 a = [1,2,3,4,5] def sum(array): if len(array) ==0 : return 0 if len(array) ==1 : return array[0] else: first = array[0] array.pop(0) #pop 指的是pop的索引 return first + sum(array) print(sum(a))

#标准答案 a = [1,2,3,4,5] def sum(array): if array == []: return 0 else: return array[0] + sum(array[1:]) print(sum(a))

a = [1,2,3,4,5] def count(array): if array == []: return 0 else: return 1+count(array[1:]) print(count(a))

a = [1, 2, 8, 4, 5] def biggest(array): if array == []: return 0 else: return array[0] if\ array[0] > biggest(array[1:])\ else biggest(array[1:]) print(biggest(a))

import math a = [1, 2, 3, 4, 5, 8, 10] def cut(array, item): len_array = len(array) if len_array == 1: return 0 else: mid = math.floor(len_array / 2) if item == array[mid]: return mid if item > array[mid]: return len(array[:mid]) + cut(array[mid:], item) else: return cut(array[:mid], item) print(cut(a, 8))

a = [1,2,6,3,8,5] def qsort(array): if len(array) < 2: return array mid = array[0] low = [array[i] for i in range(1,len(array)) if array[i] <= mid] up = [array[i] for i in range(1,len(array)) if array[i] > mid] return qsort(low)+[mid]+qsort(up) print(qsort(a))

array = [5,7,2,4,3,1,8,6] from random import randint def qsort(array): if len(array)<=1: return array ran=randint(0,len(array)-1) mid = array[ran] array.pop(ran) smaller = [ i for i in array if i<=mid] bigger = [i for i in array if i>mid ] return qsort(smaller) + [mid] +qsort(bigger) print(qsort(array))

from collections import deque graph = {} graph['you'] = ["alice","bob","claire"] graph['bob'] = ["anuj","peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom","jooy"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = [] def person_is_seller(name): return name[-1] == 'm' # deque def find(): search_queue = deque() search_queue += graph["you"] while search_queue: person = search_queue.popleft() if person_is_seller(person): print(person +"is seller") return True else: search_queue +=graph[person] return False find()

from collections import deque def person_is_seller(name): return name[-1] == 'm' graph = {} graph['you'] = ["alice","bob","claire"] graph['bob'] = ["anuj","peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom","jooy"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = [] search_queue = deque() def find2(search_queue): if search_queue: person = search_queue.popleft() if person_is_seller(person): print(person +"is seller") return True else: search_queue +=graph[person] return find2(search_queue) else: return None search_queue += graph["you"] print(find2(search_queue))

graph = {} graph['start'] = {} graph['start']['a'] = 5 graph['start']['b'] = 0 graph['a'] = {} graph['a']['c'] = 15 graph['a']['d'] = 20 graph['b'] = {} graph['b']['c'] = 30 graph['b']['d'] = 25 graph['c'] = {} graph['c']['fin'] = 20 graph['d'] = {} graph['d']['fin'] = 10 graph['fin'] = {} costs = {} costs['a'] = 5 costs['b'] = 0 costs['c'] = float("inf") costs['d'] = float("inf") costs['fin'] = float("inf") parents = {} parents['a'] = 'start' parents['b'] = 'start' parents['c'] = 'start' parents['d'] = 'start' parents['fin'] = None processed = [] def find_lowst(costs): low_cost = float("inf") low_cost_node = None for node in costs: cost = costs[node] if cost < low_cost and node not in processed: low_cost = cost low_cost_node = node return low_cost_node node = find_lowst(costs) while node is not None: cost = costs[node] friends = graph[node] for friend in friends.keys(): new_cost = friends[friend]+cost # if new_cost < if new_cost < costs[friend]: costs[friend] = new_cost parents[friend] = node processed.append(node) node = find_lowst(costs) print(costs)

graph = {} graph['start'] = {} graph['start']['a'] = 5 graph['start']['b'] = 0 graph['a'] = {} graph['a']['c'] = 15 graph['a']['d'] = 20 graph['b'] = {} graph['b']['c'] = 30 graph['b']['d'] = 25 graph['c'] = {} graph['c']['fin'] = 20 graph['d'] = {} graph['d']['fin'] = 10 graph['fin'] = {} def get_costs_parent(graph): costs = {} parents = {} for node in graph.keys(): if node in graph['start'].keys(): costs[node] = graph['start'][node] parents[node] = 'start' else: costs[node] = float('inf') parents[node] = None return costs,parents costs ,parents= get_costs_parent(graph) processed = [] def find_lowst(costs): low_cost = float("inf") low_cost_node = None for node in costs: cost = costs[node] if cost < low_cost and node not in processed: low_cost = cost low_cost_node = node return low_cost_node node = find_lowst(costs) while node is not None: cost = costs[node] friends = graph[node] for friend in friends.keys(): new_cost = friends[friend]+cost # if new_cost < if new_cost < costs[friend]: costs[friend] = new_cost parents[friend] = node processed.append(node) node = find_lowst(costs) print(costs['fin'])

graph = {} graph['start'] = {} graph['start']['a'] = 5 graph['start']['b'] = 0 graph['a'] = {} graph['a']['c'] = 15 graph['a']['d'] = 20 graph['b'] = {} graph['b']['c'] = 30 graph['b']['d'] = 25 graph['c'] = {} graph['c']['fin'] = 20 graph['d'] = {} graph['d']['fin'] = 10 graph['fin'] = {} def get_costs_parent(graph): costs = {} parents = {} for node in graph.keys(): if node in graph['start'].keys(): costs[node] = graph['start'][node] parents[node] = 'start' else: costs[node] = float('inf') parents[node] = None return costs,parents costs ,parents= get_costs_parent(graph) def find_lowst(costs): low_cost = float("inf") low_cost_node = None for node in costs: cost = costs[node] if cost < low_cost and node not in processed: low_cost = cost low_cost_node = node return low_cost_node def find_short_path(costs,processed,parents): node = find_lowst(costs) if node is not None: cost = costs[node] neighbors = graph[node] for n in neighbors.keys(): new_cost = neighbors[n] + cost if new_cost < costs[n]: costs[n] = new_cost parents[n] = node processed.append(node) return find_short_path(costs,processed,parents) else: return costs['fin'] processed = [] fastst = find_short_path(costs,processed,parents)

array = ['mt','wa','or','id','nv','ut','ca','az'] states_needed = set(array) # 转换为集合 stations = {} stations['kone'] = set(['id','nv','ut']) stations['ktwo'] = set(['wa','id','mt']) stations['kthree'] = set(['or','nv','ca']) stations['kfour'] = set(['nv','ut']) stations['kfive'] = set(['ca','az']) stations_array = [] while states_needed: bast_station = None states_covered = set() for station,state_for_station in stations.items(): # print(station,state_for_station) covered = state_for_station & states_needed if len(covered) > len(states_covered): bast_station = station states_covered = covered states_needed = states_needed - states_covered # print(states_needed) stations_array.append(bast_station) #最好的station print(stations_array)

#递归实现 def find_station(states_needed): if states_needed: bast_station = None states_covered = set() for station,state_for_station in stations.items(): # print(station,state_for_station) covered = state_for_station & states_needed if len(covered) > len(states_covered): bast_station = station states_covered = covered states_needed = states_needed - states_covered return [bast_station] +find_station(states_needed) else: return [] print(find_station(states_needed))

graph = {} graph['a'] = {} graph['a']['b'] = 3 graph['a']['c'] = 6 graph['a']['d'] = 1 graph['c'] = {} graph['c']['a'] = 6 graph['c']['b'] = 2 graph['c']['d'] = 7 graph['b'] = {} graph['b']['c'] = 2 graph['b']['d'] = 5 graph['b']['a'] = 3 graph['d'] = {} graph['d']['c'] = 7 graph['d']['a'] = 1 graph['d']['b'] = 5 list_city_array=list(graph.keys()) def find_fast(graph,next_array): if next_array: finded_array = [] city = next_array.pop() list_array = list(graph.keys()) cost = 0 finded_array.append(city) while len(finded_array) < len(list_array): low_cost = float('inf') low_cost_city = None for neibo in graph[city].keys(): if graph[city][neibo]<low_cost and neibo not in finded_array: low_cost = graph[city][neibo] low_cost_city = neibo # print(low_cost) cost += low_cost finded_array.append(low_cost_city) city = low_cost_city mined = min(find_fast(graph,next_array),cost) return mined else: return float("inf") print(find_fast(graph,list_city_array))