1 #算法:解决问题的方法和步骤 2 3 #排序算法 4 #选择排序 5 def select(items, comp = lambda x,y : x <y): 6 #通过隐藏函数lambda判断两个数的大小 7 items = items[:] 8 for i in range(len(items) - 1): 9 min = i 10 for j in range(i+1, len(items)): 11 if comp(items[j], items[min]): 12 #获得j以后的最小值 13 min = j 14 items[i], items[min] = items[min], items[i] 15 #将判断得到的最小值放在前面 16 return items 17 18 #冒泡排序 19 def maopao(items, tem = lambda x, y : x > y): 20 items = items[:] 21 for i in range(len(items) - 1): 22 exambine = False 23 for j in range(len(items) - 1 - i): 24 #把最大的放在最后 25 if tem(items[j], items[j + 1]): 26 items[j], items[j + 1] = items[j+1], items[j] 27 exambine = True 28 if not exambine: 29 break 30 return items 31 32 #搅拌排序 33 def jban_select(items, stm = lambda x, y : x > y): 34 items = items[:] 35 for i in range(len(items)-1): 36 exim = False 37 for j in range(len(items) - 1 -i): 38 #把最大的放到最后 39 if stm(items[j], items[j+1]): 40 items[j], items[j+1] = items[j+1], items[j] 41 exim = True 42 if exim: 43 exim = False 44 for x in range(len(items)-2-i, 0, -1): 45 #把最小的放在最前面 46 if stm(items[x-1], items[x]): 47 items[x-1], items[x] = items[x],items[x-1] 48 exim = True 49 if not exim: 50 break 51 return items 52 53 #归并排序 54 def collect(items1, items2, comp = lambda x,y : x <y): 55 items = [] 56 #print('items1%s' %items1) 57 #print('items2%s' %items2) 58 index1, index2 = 0, 0 59 while index1 < len(items1) and index2 < len(items2): 60 if comp(items1[index1], items2[index2]): 61 items.append(items1[index1]) 62 index1 += 1 63 else: 64 items.append(items2[index2]) 65 index2 += 1 66 items += items1[index1:] 67 items += items2[index2:] 68 #print('items%s'%items) 69 return items 70 def after(items): 71 return sort(list(items)) 72 73 def sort(items): 74 if len(items) < 2: 75 return items 76 mid = len(items) // 2 77 left = sort(items[:mid]) 78 right = sort(items[mid:]) 79 #print('left:%s' %left) 80 #print('right%s' %right) 81 return collect(left, right) 82 print(after([23,45,2,4,5232,1])) 83 84 #查找算法 85 #顺序查找 86 def function(items, key): 87 for number, value in enumerate(items): 88 if value == key: 89 return number 90 return -1 #若不存在key,安全退出 91 92 #折半查找 93 def half_holt(items, key): 94 #items为从小到大排列 95 start, end = 0, len(items)-1 96 while start < end: 97 mid = (start + end) // 2 98 if key < items[mid]: 99 end = mid -1 100 elif key > items[mid]: 101 start = mid +1 102 else: 103 return mid 104 return -1 105 106 #穷举法(百元百鸡) 107 #公鸡5元一只,母鸡3元一只,小鸡1元3只 108 for i in range(20): 109 for j in range(33): 110 k = 100 - i - j 111 if i*5 + j*3 + k/3 == 100 and k % 3 == 0: 112 print('公鸡%d只,母鸡%d只,小鸡%d只' %(i, j, k)) 113 114 #五人分鱼 115 fish = 6 116 while True: 117 total = fish 118 enough = True 119 for _ in range(5): 120 #保证5次分鱼都是一样的 121 if (total-1) % 5 == 0: 122 total = (total - 1) // 5 *4 123 else: 124 enough = False 125 break 126 if enough: 127 print(fish) 128 break 129 fish += 5 130 131 #贪婪法(不追求最优解,快速找到满意解) 132 class power_weight(): 133 134 def __init__(self, name, price, weight): 135 self.name = name 136 self.weight = weight 137 self.price = price 138 @property 139 def thing_count(self): 140 return self.price / self.weight 141 142 def ip_thing(): 143 name, weight, price = input('拥有的物品及属性:').split() 144 #split() 通过指定分隔符对字符串进行切片 145 return name, int(weight), int(price) 146 147 def main(): 148 max_weight, mun_thing = map(int, input('总重和总的物品件数:').split()) 149 #map(function, iterable, ...),对序列根据方法排序 150 thing_rate = [] 151 for _ in range(mun_thing): 152 thing_rate.append(power_weight(*ip_thing())) 153 thing_rate.sort(key=lambda x : x.thing_count ,reverse = True) 154 #key=lambda x : x.thing_count 不太懂 155 total_weight = 0 156 total_price = 0 157 print('ok') 158 for thing in thing_rate: 159 if total_weight + thing.weight <= max_weight: 160 print(f'小偷带走了{thing.name}') 161 total_weight += thing.weight 162 total_price += thing.price 163 print(f'总价值{total_price}美元') 164 165 if __name__ == '__main__': 166 main() 167 168 #快速排列(选择枢轴对元素进行划分,左边都比枢轴小右边都比枢轴大) 169 def main(items, comp = lambda x, y : x <= y): 170 items = items[:] 171 func1(items, 0, len(items) - 1, comp) 172 return items 173 174 def func1(items, start ,end, comp): 175 if start < end: 176 pol = func2(items, start, end, comp) 177 func1(items, start, pol-1, comp) 178 func1(items, pol +1, end,comp) 179 180 def func2(items, start, end, comp): 181 boss = items[end] 182 i = start -1 183 for j in range(start, end): 184 if comp(items[j], boss): 185 i +=1 186 items[i], items[j] = items[j], items[i] 187 items[i+1], items[end] = items[end], items[i+1] 188 return i+1 189 190 #动态规则 191 items = list(map(int, input('输入数列').split())) 192 overall = part = items[0] 193 for i in range(1, len(items)): 194 part = max(items[i], part+items[i]) 195 overall = max(part, overall) 196 print(overall)