计数初步

2018-02-21 本文已影响0人雪茸川

求和式的表示

$x\sum_{y\in S}y = \sum_{y\in S} xy$

x*sum(S)==sum(x*y for y in S)

$\sum^n_{i=m}f(i)$

sum(f(i) for i in range(m,n+1))

两种赛制：循环赛和淘汰赛

循环赛

相当于求一个完全图到底有多少条边

握手问题：
n个人之间相互握手，总共会有多少次握手

tips：每个人都会和剩下的n-1个人握手，都重复了两次
答案：一共是 $\frac {n(n-1)} 2$

相当于等差级数 $\sum^{n-1}_{i=0}i=\frac {n(n-1)} 2$
理解：对于第一个人握手次数是n-1，第二个人就是n-2 ，一次类推直到0

淘汰赛（完全平衡二叉树结构）

每个骑士进行配对，胜利的人继续配对，直至剩下最后的冠军jishu
总次数=n/2+n/4+···+1

也就是 $\sum_{i=0}^{h-1}2^i=n-1$ ,h为树的高度 $2^h=n$

龟兔赛跑问题

非常形象的表示，兔子：n，乌龟，h
$n = 2^h$ , $h = logn$

组合问题

也叫做二项式系数和选择问题，从n个里面选择k个，不考虑排序，那么就用总的排序数除以k个以及剩下（n-k）个人的排序数
$c(n,k) = \frac {n!}{k!(n-k)!}$
$\sum_{k=0}^nC(n,k)=2^n$

递归与递归式

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]