算法 - 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.散列函数

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

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

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

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

image其中: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^,$$,实数数列$$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)
$$10^3$$ 0 0 0
$$10^4$$ 9 19 20
$$10^5$$ 140 120 70
$$10^6$$ 2149 1689 780
$$10^7$$ 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')

强连通分支

 

#!/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;
}

运行:

 

gcc -o 8q 8q.c 

结果:

 

./8q|wc -l

为:92.




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee