岳小岳
2018-11-16
- 1.计算二项式系数(动态规划)
- # coding:utf-8
- # computing C(n,k)
- def Binomial_coefficient(n,k):
- if k == 0 or k == n:
- result = 1
- else:
- result = Binomial_coefficient(n-1,k-1)+Binomial_coefficient(n-1,k)
- return result
- print Binomial_coefficient(10,3)
- 2.Floyd算法
- # coding:utf-8
- # floyd
- _ = float('inf')
- a = [[0,_,3,_],[2,0,_,_],[_,7,0,1],[6,_,_,0]]
- for k in range(4):
- for i in range(4):
- for j in range(4):
- if a[i][j] > a[i][k] + a[k][j]:
- a[i][j] = a[i][k] + a[k][j]
- else:
- pass
- print a
- 3.背包问题
- # coding:utf-8
- # knapsack_problem
- w = [2,1,3,2]
- v = [12,10,20,15]
- matrix = []
- sub_lst = []
- for i_i in range(5):
- for j_j in range(6):
- sub_lst.append(0)
- matrix.append(sub_lst)
- sub_lst = []
- for i in range(1,5):
- for j in range(1,6):
- if j >= w[i-1]:
- matrix[i][j] = max(matrix[i-1][j],v[i-1]+matrix[i-1][j-w[i-1]])
- else:
- matrix[i][j] = matrix[i-1][j]
- print matrix
- 4.用于计算最小公约数的Euclid算法
- # coding:utf-8
- # Euclid
- def Euclid(m,n):
- while n != 0:
- r = m % n
- m = n
- n = r
- return m
- print Euclid(60,24)
- 5.求一个一维数组中大小最接近的两个元素的差
- # coding:utf-8
- # minDistance
- def minDistance(lst):
- dmin = float('inf')
- for i in range(len(lst)):
- for j in range(len(lst)):
- if i < j and abs(lst[i]-lst[j]) < dmin:
- dmin = abs(lst[i] - lst[j])
- else:
- pass
- return dmin
- print minDistance([1,99,5,10,23,80])
- 6.计算一个十进制数转换为二进制数后的位数
- # coding:utf-8
- # calculate count of binary
- # method1
- def Binary(n):
- count = 1
- while n > 1:
- count += 1
- n = n / 2
- return count
- print Binary(4)
- # method2
- def Binary2(n):
- if n == 1:
- return 1
- else:
- return Binary2(n/2)+1
- print Binary2(4)
- 7. 选择排序
- # coding:utf-8
- # selection_sort
- def swap(a,b):
- tmp = a
- a = b
- b = tmp
- return a,b
- def Selection_Sort(lst):
- for i in range(len(lst)-1):
- min = i
- for j in range(1,len(lst)):
- if lst[j] < lst[min]:
- min = j
- lst[i],lst[min] = swap(lst[i],lst[min])
- return lst
- print Selection_Sort([3,1,2])
- 8.冒泡排序
- # coding:utf-8
- # BubbleSort
- def swap(a,b):
- tmp = a
- a = b
- b = tmp
- return a,b
- def Bubble_sort(lst):
- for i in range(len(lst)-1):
- for j in range(len(lst)-1-i):
- if lst[j+1] < lst[j]:
- lst[j],lst[j+1] = swap(lst[j],lst[j+1])
- return lst
- print Bubble_sort([3,1,2])
联系客服