程序设计方法学实验

动态规划解0-1背包：

#include<iostream>

using namespace std

//显然定义为全局变量不好

const int item=3//物品数量

const int max_wgt=10//背包最大容量

int c[item+1][max_wgt+1]//从1…i…item物品中,背包剩余空间为0<=j<=max_wgt的最大价值

int w[item+1]={0,3,4,5}//物品质量

int vl[item+1]={0,4,5,6}//物品价值

int knapbag()

{

for (int i=0i<=itemi++)//初始化

{

for (int j=0j<=max_wgtj++)

{

c[i][j]=0

}

}

//c(i,j)=max{c(i-1,j), c(i-1,j-w[i])+vl(i)}

for (int i=1i<=itemi++)

{

　蚂凳　for (int j=1j<=max_wgtj++)

{

if (w[i]<=j)

{

if (vl[i]+c[i-1][j-w[i]]>c[i-1][j])

{

c[i][j]=vl[i]+c[i-1][j-w[i]]//选择第i物品

}

else

c[i][j]=c[i-1][j]//不选择第i个物品

　闷虚旅　}

else

c[i][j]=c[i-1][j]//剩余容量不够

}//endfor

}//endfor

return c[item][max_wgt]//返回最大值

}

int main()

{

cout<<knapbag()<<endl

return 0

}

void trackback()//算出是由哪几个物品组成

{

int temp_wei=max_wgt

int x[item+1]={0,0,0,0}

for (int i=itemi>0i--)

{

if (c[i][temp_wei]==c[i-1][temp_wei])//最后一个肯定是最大价值的

{

x[i]=0

}

else

{

x[i]=1

temp_wei-=w[i]

}

}

for (int i=0i<=itemi++)

{

if (x[i])

{

std::cout<<i<<","

}

}

std::cout<<std::endl

}

最长公共子序列：

最长公誉芦共子序列的定义是，一个数列z分别是已知数列的子序列（子序列不一定是连续序列，是在该序列中删去若干元素后得到的序列），且是所有符合此条件序列中最长的，则z成为最长公共子序列lcs(Longest Common Subsequences)。有些地方则说公共子串就是要求连续的子序列，有些地方则不是，这里要注意区分。下面是完整实现代码。

#include <iostream>

using namespace std

void LCS_Length(char *x,char *y,int **b,int m,int n)

{

//c[i][j]表示x[i-1],y[j-1]之前公共子序列的长度,i表示x数组前进，j表示y数组前进

//不用c[i][j]表示x[i],y[j]之前公共子序列的长度是因为需要使用c[0][0]来表示没有公共子序列，

//即c[0][0]恒等于0，因此c数组最大下标为c[m+1][n+1]

int **c

c=new int*[m+1]

for( int i=0i<m+1i++)

c[i]=new int[n+1]

for(int i=0i<m+1i++)

c[i][0]=0

for(int i=0i<n+1i++)

c[0][i]=0

for(int i=1i<=mi++)

{

for(int j=1j<=nj++)

{

if(x[i-1]==y[j-1])//找到一个公共“字符”

{

c[i][j]=c[i-1][j-1]+1//公共子序列的长度在原来的基础上加1

b[i][j]=0//做一个辅助标志，表示要达到目前的长度，x，y数组均需“前进”一步

//即x[i-1]，y[j-1]都要作出贡献

}

//当前字符不相同，且x数组后退一步（即c[i-1][j]）比y数组后退一步（即c[i][j-1]）

//所得到的公共子序列的长度要长，隐含的意思是当前最长公共子序列可以不需要x[i-1]

else if(c[i-1][j]>=c[i][j-1])

{

c[i][j]=c[i-1][j]//当前最长公共子序列可以不需要x[i-1]

b[i][j]=-1

}

//和上面分析类似

else

{

c[i][j]=c[i][j-1]//当前最长公共子序列可以不需要y[j-1]

b[i][j]=1

}

}

}

for(int i=0i<m+1i++)

{

delete c[i]

c[i]=NULL

}

delete []c

c=NULL

}

//打印结果

void Print_LCS(int **b,char *x,int i,int j)

{

if(i==0||j==0)

return

if(b[i][j]==0)

{

Print_LCS(b,x,i-1,j-1)

cout<<x[i-1]

}

else if(b[i][j]==-1)

Print_LCS(b,x,i-1,j)

else

Print_LCS(b,x,i,j-1)

}

int _tmain(int argc, _TCHAR* argv[])

{

char x[]="ADAB"

char y[]="ADCA"

int m=strlen(x)

int n=strlen(y)

int **b

b=new int*[m+1]

for( int i=0i<m+1i++)

b[i]=new int[n+1]

LCS_Length(x,y,b,m,n)

Print_LCS(b,x,m,n)

for(int i=0i<m+1i++)

{

delete b[i]

b[i]=NULL

}

delete []b

b=NULL

return 0

}

A*算法

1.启发式搜索

广度优先搜索和双向广度优先搜索都属于盲目搜索，这在状态空间不大的情况下是很合适的算法，可是当状态空间十分庞大时，它们的效率实在太低，往往都是在搜索了大量无关的状态结点后才碰到解答，甚至更本不能碰到解答。

搜索是一种试探性的查寻过程，为了减少搜索的盲目性引，增加试探的准确性，就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估，从中选择最好、可能容易到达目标的位置，再从这个位置向前进行搜索，这样就可以在搜索中省略大量无关的结点，提高了效率。

2.A*算法

A*算法是一种常用的启发式搜索算法。

在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为：

f'(n) = g'(n) + h'(n)

这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：

f(n) = g(n) + h(n)

其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。

3.A*算法的步骤

A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。

A*算法的步骤如下：

1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。

2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。

3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。

4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。

5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。

4.八数码问题的A*算法的估价函数

估价函数中，主要是计算h，对于不同的问题，h有不同的含义。那么在八数码问题中，h的含意是各什么？八数码问题的一个状态实际上是数字0~8的一个排列，用一个数组p[9]来存储它，数组中每个元素的下标，就是该数在排列中的位置。例如，在一个状态中，p[3]=7，则数字7的位置是3。如果目标状态数字3的位置是8，那么数字7对目标状态的偏移距离就是3，因为它要移动3步才可以回到目标状态的位置。

八数码问题中，每个数字可以有9个不同的位置，因此，在任意状态中的每个数字和目标状态中同一数字的相对距离就有9*9种，可以先将这些相对距离算出来，用一个矩阵存储，这样只要知道两个状态中同一个数字的位置，就可查出它们的相对距离，也就是该数字的偏移距离：

0 1 2 3 4 5 6 7 8

0 0 1 2 1 2 3 2 3 4

1 1 0 1 2 1 2 3 2 3

2 2 1 0 3 2 1 4 3 2

3 1 2 3 0 1 2 1 2 3

4 2 1 2 1 0 1 2 1 2

5 3 2 1 2 1 0 3 2 1

6 2 3 4 1 2 3 0 1 2

7 3 2 3 2 1 2 1 0 1

8 4 3 2 3 2 1 2 1 0

例如在一个状态中，数字8的位置是3，在另一状态中位置是7，那么从矩阵的3行7列可找到2，它就是8在两个状态中的偏移距离。

估价函数中的h就是全体数字偏移距离之和。

显然，要计算两个不同状态中同一数字的偏移距离，需要知道该数字在每个状态中的位置，这就要对数组p[9]进行扫描。由于状态发生变化，个数字的位置也要变化，所以每次计算h都沿线扫描数组，以确定每个数字在数组中的位置。为了简化计算，这里用一个数组存储状态中各个数字的位置，并让它在状态改变时随着变化，这样就不必在每次计算h时，再去扫描状态数组。

例如，某个状态中，数字5的位置是8，如果用数组r[9]存储位置，那么就有r[5]=8。

现在用数组r[9]存储当前状态的数字位置，而用s[9]存储目标状态的数字位置，那么当前状态数字i对目标状态的偏移距离就是矩阵中r[i]行s[i]列对应的值。

5.A*算法的类结构

A*算法的类声明如下：

class TAstar:public TEight

{

public:

TAstar(){} //构造函数

TAstar(char *fname)//带参数构造函数

virtual void Search()//A*搜索法

private:

int f,g,h //估价函数

int r[Num]//存储状态中各个数字位置的辅助数组

static int s[Num] //存储目标状态中各个数字位置的辅助数组

static int e[]；//存储各个数字相对距离的辅助数组

void Printl(TList<TAstar>L) //成员函数，输出搜索路径

int Expend(int i) //成员函数，A*算法的状态扩展函数

int Calcuf() //成员函数，计算估价函数

void Sort(TList<TAstar>&L,int k) //成员函数，将新扩展结点按f从小到大

//顺序插入待扩展结点队列

int Repeat(TList<TAstar>&L)//成员函数，检查结点是否重复

}

int TAstar::s[Num],TAstar::e[Num*Num]

TAstar::TAstar(char *fname):TEight(fname)

{

for(int i=0i<Num)

{

r[p[i]]=i //存储初始状态个个数字的位置

s[q[i]]=i++ //存储目标状态个个数字的位置

}

ifstream fin

fin.open(".\Eightd.txt",ios::in | ios::nocreate)//打开数据文件

if(!fin)

{

cout<<"不能打开数据文件!"<<endl

return

}

for(i=0i<Num*Numi++)//读入各个数字相对距离值

fin>>e[i]

fin.close()

f=g=h=0 //估价函数初始值

}

void TAstar::Printl(TList<TAstar>L)

{

TAstar T=*this

if(T.last==-1)

return

else

{

T=L.GetData(T.last)

T.Printl(L)

T.Printf()

}

}

int TAstar::Expend(int i)

{

if(Extend(i))//结点可扩展

{

int temp=r[p[r[0]]]//改变状态后数字位置变化，存储改变后的位置

r[p[r[0]]]=r[0]

r[0]=temp

return 1

}

return 0

}

int TAstar::Calcuf()

{

h=0

for(int i=0i<Numi++) //计算估价函数的h

h+=e[Num*r[i]+s[i]]

return ++g+h

}

void TAstar::Sort(TList<TAstar>&L,int k)

{

int n=L.Getlen()

for(int i=k+1i<ni++)

{

TAstar T=L.GetData(i)

if(this->f<=T.f)

break

}

L.Insert(*this,i)

}

int TAstar::Repeat(TList<TAstar>&L)

{

int n=L.Getlen()

for(int i=0i<ni++)

if(L.GetData(i)==*this)

break

return i

}

void TAstar::Search()

{

TAstar T=*this //初始结点

T.f=T.Calcuf() //初始结点的估价函数

TList<TAstar>L //建立队列

L.Append(T)//初始结点入队

int head=0,tail=0 //队列头和尾指针

while(head<=tail) //队列不空则循环

{

for(int i=0i<4i++)//空格可能移动方向

{

T=L.GetData(head) //去队列头结点

if(T.h==0) //是目标结点

{

T.Printl(L)//输出搜索路径

T.Print() //输出目标状态

return //结束

}

if(T.Expend(i)) //若结点可扩展

{

int k=T.Repeat(L)//返回与已扩展结点重复的序号 if(k<head) //如果是不能扩展的结点

continue//丢弃

T.last=head //不是不能扩展的结点，记录父结点

T.f=T.Calcuf()//计算f

if(k<=tail) //新结点与可扩展结点重复

{

TAstar Temp=L.GetData(k)

if(Temp.g>T.g) //比较两结点g值

L.SetData(T,k)//保留g值小的

continue

}

T.Sort(L,head)//新结点插入可扩展结点队列 tail++ //队列尾指针后移

}

}

head++//一个结点不能再扩展，队列头指针指向下一结点

}

}

n皇后问题

#include <iostream.h>

#include <math.h>

void Queue(int n)

{

for (i=1i<=ni++)//初始化

x[i]=0

k=1

while (k>=1)

{

x[k]=x[k]+1//在下一列放置第k个皇后

while (x[k]<=n &&!Place(k))

x[k]=x[k]+1//搜索下一列

if (x[k]<=n &&k= =n) { //得到一个解，输出

for (i=1i<=ni++)

cout<<x[i]

return

}

else if (x[k]<=n &&k<n)

k=k+1 //放置下一个皇后

else {

x[k]=0//重置x[k]，回溯

k=k-1

}

}

}

bool Place(int k) //考察皇后k放置在x[k]列是否发生冲突

{

for (i=1i<ki++)

if (x[k]= =x[i] | | abs(k-i)= =abs(x[k]-x[i]))

return false

return true

}

用中断的目的，就是要在A/D转换时段内做其他 *** 作，不让其他可利用资源空等。这就需要你程序里有个类似 *** 作系统作业调度的守护进程。这个守护进程维护的是个全局状态机，守护进程持续监测状态机状态，状态一旦具备进入下一个状态的条件，守护进程就会根据系统占用洞渗情况，决定是否发起到预定状态的新进程，或者送到某个有管理的批处理队列里。实时多任务系统里通常守护进程要比普通进程优先级高；没有实时要求的多任务系统里，支持多进程的，优先级也要比普通进程高；单进程系统通常不设高优先级的守护进程，因为只要有任务在处理就没资源会闲置，不妨等处理完毕再做同级调度。

中断方式的A/D，A/D转换完成后会触发中断，中断处理程序置位“A/D转换好”状态后退出即可。守护进程监测到这个状态改变，结合之前的系统状态，根据状态机下银颤乎一状态发起预定的A/D转换的后处理程锋悉序。A/D后处理程序处理完成后置位“A/D后处理完毕”，守护进程会再根据你设计的状态转移图发起向下一状态进发的新进程.......

中断处理程序代码应极尽简洁，非必要避免在里面做过多的处理，因为它工作时所有进程都停下等，对有实时性要求的低级进程这种影响可能是致命的。

作业调度是程序设计里非常有趣的单元之一。

---