求和式的表示
x*sum(S)==sum(x*y for y in S)
sum(f(i) for i in range(m,n+1))
两种赛制:循环赛和淘汰赛
循环赛
相当于求一个完全图到底有多少条边
- 握手问题:
n个人之间相互握手,总共会有多少次握手
tips:每个人都会和剩下的n-1个人握手,都重复了两次
答案:一共是
相当于等差级数
理解:对于第一个人握手次数是n-1,第二个人就是n-2 , 一次类推直到0
淘汰赛(完全平衡二叉树结构)
每个骑士进行配对, 胜利的人继续配对,直至剩下最后的冠军jishu
总次数=n/2+n/4+···+1
也就是 ,h为树的高度
龟兔赛跑问题
非常形象的表示,兔子:n, 乌龟,h
,
组合问题
也叫做二项式系数和选择问题,从n个里面选择k个,不考虑排序,那么就用总的排序数除以k个以及剩下(n-k)个人的排序数
递归与递归式
def S(seq,i=0):
if i== len(seq):return 0
return S(seq,i+1)+seq[i]
def T(seq,i=0):#上式的开销
if i==len(seq):return 1
return T(seq,i+1)+1
侏儒排序法
def gnomesort(seq):
i=0
while i < len(seq):
if i ==0 or seq[i-1]<=seq[i]:
i+=1
else:
seq[i],seq[i-1]=seq[i-1],seq[i]
i-=1
归并排序法
def mergesort(seq):
mid=len(seq)//2
lft,rgt=seq[:mid],seq[mid:]
if len(lft) >1 : lft =mergesort(lft)
if len(rgt)>1 : rgt =mergesort(rgt)
res = []
while lft and rgt:
if lft[-1] >= rgt[-1]:
res.append(lft.pop())
else:
res.append(rgt.pop())
res.reverse()
print res
return (lft or rgt) +res
seq=[6,5,4,3,2,1]
mergesort(seq)
[5]
[6]
[2]
[3]
[4, 5, 6]
[1, 2, 3, 4, 5, 6]
网友评论