算法 - webdancer's Blog

1.LCS最长公共子序列

字符串的子序列是指从该字符串中删除一些字符（可以不删除），保持字符之间的相对位置不变，而得到的字符串； $A,B$ 之间的最大公共子序列是指求出 $A,B$ 相同的子序列中，长度最长的那个。

输入：两个字符串 $A,B$ ，长度为 $m,n$

输出：字符串 $A,B$ 的最长公共子序列

继续阅读

散列表(hash table)

1.散列表概念

散列表（hash table ,hash map）是一种使用散列函数将“键”映射到“值”的数据结构，这样散列表实现了字典结构。示意图如下：

散列函数(hash function)将“键”转为bucket的索引，正如在上一篇介绍散列函数是说的，一般情况下散列表不是理想散列，会发生“碰撞”（即不同的键映射到了相同的的值）。

使用散列解决的一个核心问题就是查找（search）。散列的思想是是把键的某些内容打乱，使用这种部分的信息作为查找的开始。为了使用散列表，我们需要解决两个问题：寻找散列函数（hash function）和解决“碰撞”。

2.散列函数

一个良好的散列函数要满足两个条件：

容易计算。
最小化“碰撞”。概率的角度看，就是要求散列函数应该让散列值服从一个均匀分布，一个非均匀的分布，在概率大的地方，显然容易发生“碰撞”。设计一个散列函数，让散列值服从均匀分布是困难的。

设计良好的散列函数一直是一个有挑战性的工作。通常有两种：基于除法和基于乘法。

取余法。h(k)=k%M 。M的取值对于散列函数影响较大，通常M取一个素数，使得r^k <> a ,其中r为键字符集合级数，k,a是较小的数。
乘法方法。

其中：w是计算机字数目，A是一个w互素的常数。

3.解决“碰撞”

1.独立拉链。这种解决方法思路很简单，就是将发生“碰撞”的<键,值>对用链表连接起来。如下图：

2.开放寻址。这种方法是确定某种规则，通过它，某个键K来确定一个“探查序列”，即表中的某些位置，每当查找或是插入K时，这些位置就会被探查。最简单的方法是：线性开放寻址散列，即当发生“碰撞”时，把<键,值>对存到下一个可用的bucket中去。如下图：

两种方法比较：

评价准则：负载因子（loading factor）: a= n / b 其中：n为元素数目；b为bucket的数目。

更多的信息，大家可以参考wikipedia或是taop。

参考：wikipedia ,taop

shuffling(洗牌)

Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. —wikipedia

1.如何洗牌？

我们玩扑克牌时洗牌可以使用Riffle方法，可以参考http://www.youtube.com/watch?v=uh8iMZY4Nb4

2.洗牌算法

那么计算机如何洗牌呢？这就涉及到怎么设计一个洗牌算法，其中Fisher–Yates shuffle是常用到的洗牌算法，非常简单。

伪代码如下：

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

python代码实现：

def fyshuffling(a):
    for i in range(len(a)-1,0,-1):
        j=random.randint(0,i)
        a[i],a[j]=a[j],a[i]

注：在python的random模块中提供了shuffle方法,使用的也是Fisher–Yates shuffle算法。

云风在blog里面也讨论过，http://blog.codingnow.com/2007/09/shuffle.html下面的讨论有很多。

3.应用。

在随机梯度下降(stochastic gradient descent)中，因为要多次重复再训练集上进行，所以每次打乱训练集的顺序可以用洗牌算法。当然还有其他。

求中位数

在统计学中,中位数代表一个样本中的一个数值，其可将数值集合划分为相等的上下两部分。

实数 $$x_1,x_2,......,x_n$$ 按大小顺序（升序，降序皆可）排列为 $$x_1^,,x_2^,,......,x_n^,$$ ，实数数列的中位数 $Q_\frac{1}{2}(x)$ 为：

$Q_\frac{1}{2}(x)$ = $\lfloor\frac{(n+1)}{2}\rfloor$

明确了概念后我们可以来解决怎么找中位数了。

算法1：按照定义所说的，首先排序，然后直接返回 $Q_\frac{1}{2}(x)$ 即可。

算法2：在《算法导论》中介绍了如何可以在期望线性时间找到中位数。

思想是：1.按照快排的思想，不断的随机分割。

2.如果随机分割的返回值恰是我们找的，可以返回该位置的数。

3.如果不满足，比较一下返回值与我们找的位置的大小，递归的进行下去，直到满足1.

算法3:

思想是： 1.利用快速排序的思想，不断的的分割。不过没有用递归。

用python实现了一下上面的算法，结果：

algorithm1(ms)	algorithm2(ms)	algorithm3(ms)
0	0	0
9	19	20
140	120	70
2149	1689	780
27480	21479	12480

参考：

1.http://zh.wikipedia.org/wiki/%E4%B8%AD%E4%BD%8D%E6%95%B0

2.算法导论。

2011山大免试研究生机试题

----------------以下仅提供了解体的思路，代码未完善，上机时有些题可以直接算出来的------------------------------

1.求两个正整数的最大公约数.

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

2.令S=s1s2s3...s2n是一个符合规范的括号字符串。可以采用两种方式对S编码：
（1）一个整数序列P=p1p2...pn，其中pi是字符串S中第i个右括号前左括号的个数（记为P序列）；
（2）一个整数序列W=w1w2...wn，其中wi是字符串S中第i个右括号往左数遇到和它相匹配的左括号时经过的左括号个数（记为W序列).
要求：对于一个符合规范的括号字符串，将其P序列转化为W序列.

def translate( a ):
    #stack
    s=[]
    b=[]
    for i in range(len(a)):
        if i==0:
            for j in range(a[i]):
                s.append('(')
                b.append(1)
            s.append(')')
            b.append(1)
        else:
            for j in range(a[i]-a[i-1]):
                s.append('(')
                b.append(1)
            s.append(')')
            b.append(1)
    c=[]
    for m,v in enumerate(s):
        count=0
        if v==')':
            for n in range(m-1,-1,-1):
                if s[n]=='(':
                    count+=1
                if s[n]=='(' and b[n]==1:
                    b[n]=0
                    break;
            c.append(count)
 
    for e in c:
        print e ,
    print '\n-----------'

3.有n个半圆形金属条c1,c2,c3...cn,半圆直径分别为l1,l2,l3...ln.(如图)问可否将这些金属环首尾相接形成一个大环.
要求:输入3组直径数据(组内数据之间已用逗号隔开,每组数据间已用分号隔开),判断这3组金属条各自是否可以首尾相接.针对每组数据，如果可以，输出Y，否则输出N.

def isconnect(a):
    m=max(a)
    s=0
    first=True
    for e in a:
        if e!=m:
            s+=e
        if e==m and first:
            first=False
        elif e==m and not first:
            s+=e
    if m>s:
        return False
    else:
        return True

4.设有一个由0和1组成的字符串b1b2……bn（bi为0或1）.由该字符串可以生成一个旋转矩阵B如下:
b1     b2 … bN−1 bN （第一行为原字符串，以下n-1行均由其前一行的串循环左移一位构成）
b2     b3 … bN      b1
…
bN−1 bN … bN−3 bN−2
bN     b1 … bN−2 bN−1
矩阵B的每一行可视为一个二进制数.对这n个二进制数由小到大排序形成矩阵C.
比如有一个二进制串00110，生成的旋转矩阵为
00110
01100
11000
10001
00011
对其排序得
00011（第一行的00011<第二行的00110<第三行的01100<......）
00110
01100
10001
11000
现在设有一个二进制串r经以上变换及排序后生成矩阵C1.
要求:输入一个二进制串，如果将其视为C1的最后一列,推测并输出C1的第一行数据.
例:输入10010       程序需要输出00011

def bwt(s):
    assert '\0' not in s, "s CAN NOT contains ('\0')"
    s+='\0'
    table=sorted(s[i:]+s[:i] for i in range(len(s)))
    r=[row[-1] for row in table]
    return ''.join(r)
 
def ibwt(r):
    table=['']*len(r)
    for i in range(len(r)):
        table=sorted(r[i]+table[i] for i in range(len(r)))
    s=[row for row in table if row.endswith('\0')][0]
    return s.rstrip('\0')

强连通分支

100

101

102

103

104

105

106

#!/usr/bin/python
class Graph:
    def __init__(self,nv):
        self.v=nv
        self.e=0
        self.adj=[]
        for ele in range(nv):
            self.adj.append([])
            ele+=1
     
    def insert(self,e):
        u=e[0]
        v=e[1]
        self.adj[u].append(v)
        #self.adj[v].append(u) 
        self.e+=1
 
    def dfs(self):
        global p
        global c
        global d
        global f
        global time
        global t
        p=[]
        c=[]
        d=[]
        f=[]
        t=[]
        for ele in range(self.v):
            ele+=1
            p.append(-1)
            c.append(0)
            d.append(0)
            f.append(0)
            t.append(0)
        time=0
        m=0
        for elev in range(self.v):
            if c[elev] == 0:
                self.dfs_visit(elev,m)
     
    def dfs_visit(self,u,m):
        global time
        c[u]=1
        t[u]=m
        time+=1
        d[u]=time
        for v in self.adj[u]:
            if c[v] == 0:
                p[v]=u
                t[v]=m
                self.dfs_visit(v,m)
        c[u]=2
        time+=1
        f[u]=time
 
     
    '''def printpath(self,s,v):
        if s==v:
            print s,
        elif p[v]==-1:
            print 'no path',
        else:
            self.printpath(s,p[v])
            print v,'''
def scc(g):
    g.dfs()
    gt=Graph(g.v)
    for u in range(len(g.adj)):
        for v in g.adj[u]:
            gt.adj[v].append(u)
        u+=1
    f1=[]
    for e in f:
        f1.append(e)
    for i in range(gt.v):
        p[i]=-1
        c[i]=0
        d[i]=0
        f[i]=0
        t[i]=0
    print c
    time=0
    global m
    m=0
    for i in range(gt.v):
        v=max(f1)
        fi=f1.index(v)
        if c[fi] == 0:
            m+=1
            gt.dfs_visit(fi,m)
        f1[fi]=-1
 
if __name__=='__main__':
    g=Graph(8)
    e=[(0,1),(1,2),(1,4),(1,5),(2,3),(2,6),(3,2),(3,7),(4,0),(4,5),(5,6),(6,5),(6,7),(7,7)]
    for each in e:
        g.insert(each)
    scc(g)
    print t
    for i in range(m+1):
        for v in range(g.v):
            if t[v]==i+1:
                print v,
        print '\n'

0/1背包的回溯法

解法：回溯法。

思路：在遍历的子集树的过程中，应该注意筛选出可行的解，同时当有更好的解时，不断地更新最优解。

#include<stdio.h>
#define N 4
 
int x[N];
int p[N];
int w[N];
int c;
int pmax;
int pcur;
int wcur;
 
int bound(int t){
    int i,pr;
    pr=pcur;
    for(i=t;i<N;i++)
        pr+=p[i];
    if(pr>pmax)
        return 1;
    return 0;
}
 
void backtrace(int t){
    int i;
    if(t>=N){
        if(pmax<pcur){
            pmax=pcur;
            for(i=0;i<N;i++)
                printf("%d ",x[i]);
            printf("\n");
        }
    }
    else{
    for(i=1;i>=0;i--){
        x[t]=i;
        if(i){
            if(w[t]+wcur<=c){
            wcur+=w[t];
            pcur+=p[t];
            backtrace(t+1);
            wcur-=w[t];
            pcur-=p[t];
            }
        }
        else if(bound(t))
            backtrace(t+1);
    }
    }
}
 
int main(){
    c=7;
    w[0]=3;
    w[1]=5;
    w[2]=2;
    w[3]=1;
 
    p[0]=9;
    p[1]=10;
    p[2]=7;
    p[3]=4;
 
    backtrace(0);
    printf("the max :%d\n",pmax);
 
    return 0;
}

8皇后问题的回溯解法

问题：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线（2条）上，问有多少种摆法。

解法：采用回溯算法。

#include<stdio.h>
#include<stdlib.h>
 
#define N 9 
int x[N];
void vswap(int *pi,int *pj){
    int tmp=*pi;
    *pi=*pj;
    *pj=tmp;
}
 
void out(int * x,int n){
    int i;
    for(i=1;i<n;i++)
        printf("%d ",x[i]);
    printf("\n");
}
 
void init(int *x,int n){
    int i;
 
    for(i=1;i<n;i++)
        x[i]=i;
}
 
int bound(int t){
   int i;
   for(i=1;i<t;i++)
       if(abs(x[i]-x[t])==abs(i-t)||x[t]==x[i])
           return 0;
   return 1;
 
}
 
void traceback(int t){
    if(t>=N){
        out(x,N);
    }
    else{
        int i;
        for(i=t;i<N;i++){
            vswap(&x[t],&x[i]);
            if(bound(t))
                traceback(t+1);
            vswap(&x[t],&x[i]);
        }
    }
}
 
int main(){
    init(x,N);
    traceback(1);
    return 0;
}

运行：

1	`gcc -o 8q 8q.c`

结果：

1	`./8q\|wc` `-l`

为：92.