python之常用算法

• 岳小岳

  2018-11-16 

1. 1.计算二项式系数（动态规划）
3. # coding:utf-8
5. # computing C(n,k)
6. def Binomial_coefficient(n,k):
7. if k == 0 or k == n:
8. result = 1
9. else:
10. result = Binomial_coefficient(n-1,k-1)+Binomial_coefficient(n-1,k)
11. return result
14. print Binomial_coefficient(10,3)
18. 2.Floyd算法
20. # coding:utf-8
23. # floyd
24. _ = float('inf')
25. a = [[0,_,3,_],[2,0,_,_],[_,7,0,1],[6,_,_,0]]
28. for k in range(4):
29. for i in range(4):
30. for j in range(4):
31. if a[i][j] > a[i][k] + a[k][j]:
32. a[i][j] = a[i][k] + a[k][j]
33. else:
34. pass
38. print a
40. 3.背包问题
42. # coding:utf-8
45. # knapsack_problem
46. w = [2,1,3,2]
47. v = [12,10,20,15]
48. matrix = []
49. sub_lst = []
50. for i_i in range(5):
51. for j_j in range(6):
52. sub_lst.append(0)
53. matrix.append(sub_lst)
54. sub_lst = []
57. for i in range(1,5):
58. for j in range(1,6):
59. if j >= w[i-1]:
60. matrix[i][j] = max(matrix[i-1][j],v[i-1]+matrix[i-1][j-w[i-1]])
61. else:
62. matrix[i][j] = matrix[i-1][j]
63. print matrix
65. 4.用于计算最小公约数的Euclid算法
67. # coding:utf-8
70. # Euclid
71. def Euclid(m,n):
72. while n != 0:
73. r = m % n
74. m = n
75. n = r
76. return m
78. print Euclid(60,24)
82. 5.求一个一维数组中大小最接近的两个元素的差
84. # coding:utf-8
87. # minDistance
88. def minDistance(lst):
89. dmin = float('inf')
90. for i in range(len(lst)):
91. for j in range(len(lst)):
92. if i < j and abs(lst[i]-lst[j]) < dmin:
93. dmin = abs(lst[i] - lst[j])
94. else:
95. pass
96. return dmin
99. print minDistance([1,99,5,10,23,80])
103. 6.计算一个十进制数转换为二进制数后的位数
105. # coding:utf-8
108. # calculate count of binary
111. # method1
112. def Binary(n):
113. count = 1
114. while n > 1:
115. count += 1
116. n = n / 2
117. return count
120. print Binary(4)
123. # method2
124. def Binary2(n):
125. if n == 1:
126. return 1
127. else:
128. return Binary2(n/2)+1
129. print Binary2(4)
131. 7. 选择排序
133. # coding:utf-8
136. # selection_sort
137. def swap(a,b):
138. tmp = a
139. a = b
140. b = tmp
141. return a,b
144. def Selection_Sort(lst):
145. for i in range(len(lst)-1):
146. min = i
147. for j in range(1,len(lst)):
148. if lst[j] < lst[min]:
149. min = j
150. lst[i],lst[min] = swap(lst[i],lst[min])
151. return lst
154. print Selection_Sort([3,1,2])
158. 8.冒泡排序
160. # coding:utf-8
163. # BubbleSort
164. def swap(a,b):
165. tmp = a
166. a = b
167. b = tmp
168. return a,b
171. def Bubble_sort(lst):
172. for i in range(len(lst)-1):
173. for j in range(len(lst)-1-i):
174. if lst[j+1] < lst[j]:
175. lst[j],lst[j+1] = swap(lst[j],lst[j+1])
176. return lst
179. print Bubble_sort([3,1,2])