PAGE/NUMPAGES算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
与分析实验指导王歧编HYPERLINK\l"_实验一：递归与分治"实验一：递归与分治二分查找合并排序快速排序HYPERLINK\l"_实验二：回溯算法"实验二：回溯0-1背包问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
装载问题堡垒问题（ZOJ1002）*翻硬币问题8皇后问题素数环问题迷宫问题*农场灌溉问题（ZOJ2412）*求图像的周长（ZOJ1047）*骨牌矩阵*字母转换（ZOJ1003）*踩气球（ZOJ1004）HYPERLINK\l"_实验三：搜索算法"实验三：搜索Floodfill电子老鼠闯迷宫跳马独轮车皇宫小偷分酒问题*找倍数*8数码难题HYPERLINK\l"_实验五：动态规划"实验四：动态规划最长公共子序列计算矩阵连乘积凸多边形的最优三角剖分防卫导弹*石子合并*最小代价子母树*旅游预算*皇宫看守*游戏室问题*基因问题*田忌赛马HYPERLINK\l"_实验五：贪心算法和随机算法"实验五：贪心与随机算法背包问题搬桌子问题*照亮的山景*用随即算法求解8皇后问题素数测试实验一：递归与分治实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题：二分搜索、合并排序、快速排序。对本实验中的问题，设计出算法并编程实现。试验内容和步骤二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。程序略合并排序程序略快速排序程序略实验总结及思考合并排序的递归程序执行的过程实验二：回溯算法实验目的：熟练掌握回溯算法实验内容：回溯算法的几种形式用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)else{a[m]=0;//设置状态：0表示不要该物品search(m+1);//递归搜索：继续确定下一个物品a[m]=1;//设置状态：1表示要该物品search(m+1);//递归搜索：继续确定下一个物品}}用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)elsefor(i=m;i<=n;i++){swap(m,i);//交换a[m]和a[i]if()if(canplace(m))//如果m处可放置search(m+1);//搜索下一层swpa(m,i);//交换a[m]和a[i](换回来)}}习题0-1背包问题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。程序如下：#include
voidreaddata();voidsearch(int);voidcheckmax();voidprintresult();intc=35,n=10;//c：背包容量；n：物品数intw[10],v[10];//w[i]、v[i]：第i件物品的重量和价值inta[10],max;//a数组存放当前解各物品选取情况；max：记录最大价值//a[i]=0表示不选第i件物品，a[i]=1表示选第i件物品intmain(){readdata();//读入数据search(0);//递归搜索printresult();}voidsearch(intm){if(m>=n)checkmax();//检查当前解是否是可行解，若是则把它的价值与max比较else{a[m]=0;//不选第m件物品search(m+1);//递归搜索下一件物品a[m]=1;//不选第m件物品search(m+1);//递归搜索下一件物品}}voidcheckmax(){inti,weight=0,value=0;for(i=0;imax)//且价值大于maxmax=value;//替换max}voidreaddata(){inti;for(i=0;i=n*n)checkmax();//检查当前解是否是可行解，若是则把它的价值与max比较else{search(m+1);//该位置不放堡垒递归搜索下一个位置if(canplace(m))//判断第m个格子是否能放堡垒{place(m);//在第m个格子上放置一个堡垒search(m+1);//递归搜索下一个位置takeout(m);//去掉第m个格子上放置的堡垒}}}翻硬币问题把硬币摆放成32×9的矩阵，你可以随意翻转矩阵中的某些行和某些列，问正面朝上的硬币最多有多少枚？提示：（1）任意一行或一列，翻两次等于没有翻；（2）对于9列的任何一种翻转的情况，每一行翻与不翻相互独立。8皇后问题在一个８×８的棋盘里放置８个皇后，要求这8个皇后两两之间互相都不“冲突”。#include#includevoidsearch(int);voidprintresult();//打印结果intcanplace(int,int);//判断该位置能否放置皇后voidplace(int,int);//在该位置能否放置皇后voidtakeout(int,int);//把该位置放置皇后去掉inta[8];//a[i]存放第i个皇后的位置intmain(){search(0);//递归搜索}voidsearch(intm){inti;if(m>=8)//当已经找出一组解时printresult();//输出当前结果else{for(i=0;i<8;i++)//对当前行0到7列的每一个位置{if(canplace(m,i))//判断第m个格子是否能放堡垒{place(m,i);//在(m,i)格子上放置一个皇后search(m+1);//递归搜索下一行takeout(m,i);//把(m,i)格子上的皇后去掉}}}}intcanplace(introw,intcol){inti;for(i=0;i#includevoidsearch(int);voidinit();//初始化voidprintresult();//打印结果intisprime(int);//判断该数是否是素数voidswap(int,int);//交换a[m]和a[i]inta[21];//a数组存放素数环intmain(){init();search(2);//递归搜索}intisprime(intnum){inti,k;k=sqrt(num);for(i=2;i<=k;i++)if(num%i==0)return(0);return(1);}voidprintresult(){inti;for(i=1;i<=20;i++)printf("%3d",a[i]);printf("\n");}voidsearch(intm){inti;if(m>20)//当已经搜索到叶结点时{if(isprime(a[1]+a[20]))//如果a[1]+a[20]也是素数printresult();//输出当前解return;}else{for(i=m;i<=20;i++)//(排列树){swap(m,i);//交换a[m]和a[i]if(isprime(a[m-1]+a[m]))//判断a[m-1]+a[m]是否是素数search(m+1);//递归搜索下一个位置swap(m,i);//把a[m]和a[i]换回来}}}voidswap(intm,inti){intt;t=a[m];a[m]=a[i];a[i]=t;}voidinit(){inti;for(i=0;i<21;i++)a[i]=i;}迷宫问题给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。输入数据：’.’表示空格；’X’表示墙。程序如下：#include#includevoidsearch(int,int);intcanplace(int,int);voidreaddata();//读入数据voidprintresult();//打印结果inta[20][20];//a数组存放迷宫ints,t;intmain(){introw,col;readdata();row=s/20;col=s%20;search(row,col);//递归搜索printresult();}voidsearch(introw,intcol){intr,c;a[row][col]=1;r=row;//左c=col-1;if(canplace(r,c))//判断(r,c)位置是否已经走过search(r,c);//递归搜索(r,c)r=row+1;//下c=col;if(canplace(r,c))//判断(r,c)位置是否已经走过search(r,c);//递归搜索(r,c)r=row;//右c=col+1;if(canplace(r,c))//判断(r,c)位置是否已经走过search(r,c);//递归搜索(r,c)r=row-1;//上c=col;if(canplace(r,c))//判断(r,c)位置是否已经走过search(r,c);//递归搜索(r,c)}voidprintresult(){inti,j;for(i=0;i<20;i++){for(j=0;j<20;j++)printf("%3d",a[i][j]);printf("\n");}}voidreaddata(){inti,j;for(i=0;i<20;i++){for(j=0;j<20;j++)scanf("%d",&a[i][j]);}}intcanplace(introw,intcol){if(row>=0&&row<20&&col>=0&&col<20&&a[row][col]==0)return1;elsereturn0;}农场灌溉问题（ZOJ2412）一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。给出若干由字母表示的最大不超过50×50具体由(m，n)表示的农场图，编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。SampleInput22DKHF33ADCFJKIHE-1-1SampleOutput23提示：参考迷宫问题，实现时关键要解决好各块的表示问题。求图像的周长（ZOJ1047）给一个用.和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边长。输入：首先给出m、n、x、y四个正整数，下面给出m×n的图形，x、y表示点击的位置，全0表示结束。输出：点击的图形的周长。SampleInput2222XXXX6423.XXX.XXX.XXX...X..X.X...0000Sampleoutput818提示：参考迷宫问题，区别在于它是向8个方向填。骨牌矩阵多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（0~6），现在有28组骨牌，每组两个，各组编号为1~28，每组编号对应的两个骨牌数值如下：00010203040506111213141516222324252633343536444546555666现将这28组骨牌排成一个7×8矩阵，此时只能看到每个骨牌上的数字（0~6），而不能知道每组的组号（如左下图所示）。请编程序将每组骨牌分辨出来（如右下图所示）。7X8骨牌矩阵骨牌组编号矩阵662652412828147171711111320103410101472221231324665484162525132123104321128416151513995136045512122222552626554026032724243318119605342032766202018119voidsearch(intn){查找下一个还没放置骨牌的位置(x,y);若没有，则表示已经找到一个解，输出并且返回；尝试放置骨牌；两次尝试都失败，进行回溯；}尝试放置骨牌把在(x,y)处的骨牌作为当前骨牌组的一个骨牌；把(x+1,y)处的骨牌作为当前骨牌组的另一个骨牌；判断当前骨牌组是够未被使用，如果未被使用则递归放置下一个骨牌组；把(x,y+1)处的骨牌作为当前骨牌组的另一个骨牌；判断当前骨牌组是否未被使用，如果未被使用则递归放置下一个骨牌组；字母转换（ZOJ1003）通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT到TORT:[iiiiooooioiiooio]SampleInputmadamadammbahamabahamalongshortericriceSampleOutput[iiiioooiooiiiiooooioiioioioiooiioioiooio][ioiiiooiioooioiiioooioioioioioiiioooioioioioioio][][iioioioo]踩气球（ZOJ1004）六一儿童节，小朋友们做踩气球游戏，气球的编号是1～100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。输入为两个数字，00表示结束；输出为获胜的数字。SampleInput36624934300SampleOutput6249实验三：搜索算法实验目的：熟练掌握搜索算法实验内容：广度优先搜索搜索算法的一般模式：voidsearch(){closed表初始化为空;open表初始化为空;起点加入到open表;while(open表非空){取open表中的一个结点u;从open表中删除u;u进入closed表;for(对扩展结点u得到的每个新结点vi){if(vi是目标结点)输出结果并返回;ifvi的状态与closed表和open表中的结点的状态都不相同vi进入open表;}}}搜索算法关键要解决好状态判重的问题，这样可省略closed表，一般模式可改为：voidsearch(){open表初始化为空;起点加入到open表;while(open表非空){取open表中的一个结点u;从open表中删除u;for(对扩展结点u得到的每个新结点vi){if(vi是目标结点)输出结果并返回;If(notused(vi))vi进入open表;}}}Floodfill给一个20×20的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格子。提示：参考第2题。电子老鼠闯迷宫如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。 本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下：#includevoidreaddata();//读入数据voidinit();//初始化intsearch();//广搜，并在每一个可到达的每一个空格出填上最小步数intemptyopen();//判栈是否为空：空：1；非空：0。inttakeoutofopen();//从栈中取出一个元素，并把该元素从栈中删除intcanmoveto(int,int,int*,int*,int);//判能否移动到该方向，并带回坐标(r,c)intisaim(introw,intcol);//判断该点是否是目标intused(int,int);//判断该点是否已经走过voidaddtoopen(int,int);//把该点加入到open表inta[12][12];//a存放迷宫，0表示空格，-2表示墙。//广搜时，未找到目标以前到达的空格，填上到达该点的最小步数intn;//n为迷宫边长，注：若大于12，必须修改一些参数，如a的大小intopen[20],head,tail,openlen=20;//open表ints,t;//起点和终点intmain(){intnumber;readdata();//读取数据init();//初始化number=search();//广搜并返回最小步数printf("%d",number);//打印结果}intsearch(){intu,row,col,r,c,i,num;while(!emptyopen())//当栈非空{u=takeoutofopen();//从栈中取出一个元素，并把该元素从栈中删除row=u/n;//计算该点的坐标col=u%n;num=a[row][col];//取得该点的步数for(i=0;i<4;i++){if(canmoveto(row,col,&r,&c,i))//判能否移动到该方向，并带回坐标(r,c){if(isaim(r,c))//如果是目标结点return(num+1);//返回最小步数if(!used(r,c))//如果(r,c)还未到达过{a[r][c]=num+1;//记录该点的最小步数addtoopen(r,c);//把该点加入到open表}}}}}intemptyopen(){if(head==tail)return(1);elsereturn(0);}inttakeoutofopen(){intu;if(head==tail){printf("errer:stackisempty");return(-1);}u=open[head++];head=head%openlen;return(u);}intcanmoveto(introw,intcol,int*p,int*q,intdirection){intr,c;r=row;c=col;switch(direction){case0:c--;//左break;case1:r++;//下break;case2:c++;//右break;case3:r--;//上}*p=r;*q=c;if(r<0||r>=n||c<0||c>=n)//如果越界返回0return(0);if(a[r][c]==0)//如果是空格返回1return(1);return(0);//其余情况返回0}intisaim(introw,intcol){if(row*n+col==t)return(1);elsereturn(0);}intused(introw,intcol){if(a[row][col]==0)//0表示空格return(0);elsereturn(1);}voidaddtoopen(introw,intcol){intu;u=row*n+col;open[tail++]=u;tail=tail%openlen;}voidreaddata(){inti,j,row,col;charstr[20];scanf("%d",&n);scanf("%d%d",&row,&col);//起点坐标s=row*n+col;scanf("%d%d",&row,&col);//终点坐标t=row*n+col;gets(str);for(i=0;ivoidreaddata();//读入数据voidinit();//初始化intsearch();//广度优先搜索intemptyopen();//判栈是否为空：空：1；非空：0。longtakeoutofopen();//从栈中取出一个元素，并把该元素从栈中删除intcanmoveto(int,int,int*,int*,int);//判能否移动到该方向，并带回坐标(r,c)intisaim(introw,intcol);//判断该点是否是目标intused(int,int);//判断该点是否已经走过voidaddtoopen(int,int);//把该点加入到open表inta[200][200],n=200;//a存放棋盘，n为迷宫边长longopen[2000],head,tail,openlen=2000;//open表1367longs,t;//起点和终点intsearch(){longu;introw,col,r,c,i,num;while(!emptyopen())//当栈非空{u=takeoutofopen();//从栈中取出一个元素，并把该元素从栈中删除row=u/n;//计算该点所在的行col=u%n;//计算该点所在的列num=a[row][col];//取得该点的步数for(i=0;i<8;i++){if(canmoveto(row,col,&r,&c,i))//判能否移动到该方向，并带回坐标(r,c){if(isaim(r,c))//如果是目标结点return(num+1);//返回最小步数if(!used(r,c))//如果(r,c)还未到达过{a[r][c]=num+1;//记录该点的最小步数addtoopen(r,c);//把该点加入到open表}}}}return-1;}intmain()//为了让search()显示在一页内和main函数换了以下{//一般的算法程序main函数写在最上面读起来更方便intnumber;readdata();//读取数据init();//初始化number=search();//广搜并返回最小步数printf("%d",number);//打印结果}intemptyopen(){if(head==tail)return(1);elsereturn(0);}longtakeoutofopen(){longu;if(head==tail){printf("errer:stackisempty");return(-1);}u=open[head++];head=head%openlen;return(u);}intused(introw,intcol){if(a[row][col]==0)return(0);elsereturn(1);}voidaddtoopen(introw,intcol){intu;if((head-tail)%openlen==1)printf("opentableoverflow");u=row;u=u*n+col;open[tail++]=u;tail=tail%openlen;}voidreaddata(){longrow,col;scanf("%ld%ld",&row,&col);//起点坐标s=row*n+col;scanf("%ld%ld",&row,&col);//终点坐标t=row*n+col;}voidinit(){head=0;tail=1;open[0]=s;}intisaim(introw,intcol){if(row*n+col==t)return(1);elsereturn(0);}思考：参考第4题，改为用结构体表示状态写此程序。独轮车独轮车的轮子上有5种颜色，每走一格颜色变化一次，独轮车只能往前推，也可以在原地旋转，每走一格，需要一个单位的时间，每转90度需要一个单位的时间，转180度需要两个单位的时间。现给定一个20×20的迷宫、一个起点、一个终点和到达终点的颜色，问独轮车最少需要多少时间到达。状态：独轮车所在的行、列、当前颜色、方向。另外为了方便在结点中加上到达该点的最小步数。程序如下：#includestructcolornode{introw;//该状态的行intcol;//列intcolor;//颜色intdirection;//方向intnum;//最小步数};intsearch();//广搜返回目标结点的最小步数voidreaddata();//读入数据voidinit();//初始化structcolornodemoveahead(structcolornodeu);//返回u向前走一格得到的结点intused(structcolornodev);//判断该结点是否是到达过的结点voidaddtoopen(structcolornodev);//加入到open表intislegal(structcolornodev);//如果该结点是合法的结点(未越界且是空格)intisaim(structcolornodev);//判断该结点是否是目标结点structcolornodetakeoutofopen();//从open表中取出一个结点并把该结点从open表中删除structcolornodeturntoleft(structcolornodeu);//u向左转得到新结点vstructcolornodeturntoright(structcolornodeu);//u向左转得到新结点vstructcolornodes,t;//s:起始结点；t目标结点structcolornodeopen[200];//open表inthead,tail,openlen=200;//open表相关数据intdirect[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//向左、下、右、上四个方向转时，行列的增加值inta[20][20],n=20;//a数组表示迷宫；n为迷宫边长intb[20][20][5][4];//b数组表示搜索时的所有状态(0：未访问；1：已访问)intmain(){intnumber;readdata();init();number=search();printf("%d\n",number);}intsearch()//广搜返回目标结点的最小步数{structcolornodeu,v;while(head!=tail){u=takeoutofopen();v=moveahead(u);//u向前走一格得到新结点vif(islegal(v))//如果该结点是合法的结点(未越界且是空格){if(isaim(v))//判是否是目标结点return(v.num);if(!used(v))//如果是未到达过的结点addtoopen(v);//加入到open表}v=turntoleft(u);//u向左转得到新结点vif(!used(v))addtoopen(v);v=turntoright(u);//u向右转得到新结点vif(!used(v))addtoopen(v);}}intused(structcolornodev)//判断该结点是否是到达过的结点{if(b[v.row][v.col][v.color][v.direction]==0)return(0);elsereturn(1);}voidaddtoopen(structcolornodev)//加入到open表{open[tail++]=v;tail=tail%openlen;b[v.row][v.col][v.color][v.direction]=1;}structcolornodetakeoutofopen()//从open表中取出一个结点并把该结点从open表中删除{structcolornodev;v=open[head++];head=head%openlen;return(v);}voidinit()//初始化{inti,j,k,l;for(i=0;i=n||v.col<0||v.col>=n)//若越界return0;if(a[v.row][v.col]==0)//0：表示空格return1;return0;}structcolornodemoveahead(structcolornodeu)//返回u向前走一格得到的结点{structcolornodev;v.row=u.row+direct[u.direction][0];v.col=u.col+direct[u.direction][1];v.color=(u.color+1)%5;v.direction=u.direction;v.num=u.num+1;return(v);}structcolornodeturntoleft(structcolornodeu)//u向左转得到新结点v{structcolornodev;v=u;v.direction=(v.direction+1)%4;v.num=v.num+1;return(v);}structcolornodeturntoright(structcolornodeu)//u向左转得到新结点v{structcolornodev;v=u;v.direction=(v.direction+3)%4;v.num=v.num+1;return(v);}测试数据：XXXXXXXXXXXXXXXXXXXX.....XXXX......X.XXXX.........X.XX.....XX.XXX.XX..X.XX.XXX.XX.........X.XX.....XX.XXX.XX..X.XX.XXX.X.X.....XX.X.....X..XX....X..X...X.X....X...XXXX.X.XXX...XXXX...........X.......XXXXXXX....XXXXXX..XX...........X.......X.X.....XX.X.....X..XXXXXXX....XXXXXXXX.XX....X..X...X.X....X...XXXX.X.XXX...XXXX...........X.......XXXX.X.XXXXX.XXXX.X.X....X.XX....XXX.....XXXX.....XX.........1111481皇宫小偷有一个小偷要到皇宫里偷取宝物，经过仔细的侦察，他发现皇宫实际上是一个20×20的迷宫，并且有一名卫兵巡逻，卫兵巡逻的路线是固定的，每单位时间移动一格，每4个单位时间循环一次。小偷每单位时间移动一格或在原地不动。任何时刻，小偷和卫兵在同一格，或卫兵能看到小偷，小偷将会被卫兵杀死。现在小偷已经得到了皇宫的地图，卫兵巡逻的起点，卫兵连续四次移动的方向和宝物的位置，请你设计一个程序判断小偷能否偷得宝物。提示：参考第3题、第4题分酒问题有一酒瓶装有8斤酒，没有量器，只有分别装5斤和3斤的空酒瓶。设计一程序将8斤酒分成两个4斤，并以最少的步骤给出答案。*找倍数对于每个输入的数字（如：2），则要求给出一个由1，0构成的十进制整数，且该整数为输入数字的某个倍数（如2对应的10，6的倍数100100100100100100）。*8数码难题由左图变到右图最少需要几步，并演示移动过程。2758416312345678实验四：动态规划实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。习题最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=，则另一序列Z=是X的子序列是指存在一个严格递增的下标序列，使得对于所有j=1,2,…,k有解答如下：a)最长公共子序列的结构若用穷举搜索法，耗时太长，算法需要指数时间。易证最长公共子序列问题也有最优子结构性质设序列X=和Y=的一个最长公共子序列Z=，则：若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。其中Xm-1=，Yn-1=，Zk-1=。最长公共子序列问题具有HYPERLINK"http://algorithm.diy.myrice.com/algorithm/technique/dynamic_programming/chapter3.htm"\l"optimality"最优子结构性质。b)子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有HYPERLINK"http://algorithm.diy.myrice.com/algorithm/technique/dynamic_programming/chapter3.htm"\l"repeate"子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=，Yj=。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下：c)计算最优值由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。程序如下：#include#includeintlcs_length(charx[],chary[]);intmain(){charx[100],y[100];intlen;while(1){scanf("%s%s",x,y);if(x[0]=='0')//约定第一个字符串以‘0’开始表示结束break;len=lcs_length(x,y);printf("%d\n",len);}}intlcs_length(charx[],chary[]){intm,n,i,j,l[100][100];m=strlen(x);n=strlen(y);for(i=0;il[i-1][j])l[i][j]=l[i][j-1];elsel[i][j]=l[i-1][j];returnl[m][n];}由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。思考：空间能节约吗？计算矩阵连乘积在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
计算公式为：现在的问题是，给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An。递归公式：程序如下：#includeintmain(){intp[101],i,j,k,r,t,n;intm[101][101];//为了跟讲解时保持一致数组从1开始ints[101][101];//记录从第i到第j个矩阵连乘的断开位置scanf("%d",&n);for(i=0;i<=n;i++)scanf("%d",&p[i]);//读入p[i]的值(注意：p[0]到p[n]共n+1项)for(i=1;i<=n;i++)//初始化m[i][i]=0m[i][i]=0;for(r=1;r表示具有n条边v0v1，v1v2，…,vn-1vn的一个凸多边形，其中，约定v0=vn。 若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形和。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。如图是一个凸多边形的两个不同的三角剖分。凸多边形最优三角剖分的问题是：给定一个凸多边形P=以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。可以定义三角形上各种各样的权函数W。例如：定义ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。(注意：解决此问题的算法必须适用于任意的权函数)防卫导弹一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：a)它是该次测试中第一个被防卫导弹截击的导弹；b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹的高度。输出数据：截击导弹的最大数目。分析：定义l[i]为选择截击第i个导弹，从这个导弹开始最多能截击的导弹数目。由于选择了第i枚导弹，所以下一个要截击的导弹j的高度要小于等于它的高度，所以l[i]应该等于从i＋1到n的每一个j，满足h[j]<=h[i]的j中l[j]的最大值。程序如下：#includeintmain(){inti,j,n,max,h[100],l[100];scanf("%d",&n);for(i=0;i=0;i--){max=0;for(j=i+1;jh[j]&&max
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
,使得做n－1次合并,得分的总和最小；输入数据：第一行为石子堆数n；第二行为每堆的石子数,每两个数之间用一个空格分隔。输出数据：从第一至第n行为得分最小的合并方案。第n+1行是空行.从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。SampleInput44594SampleOutput－459－4－8－59－13－9224－5－944－14－4－4－1822最小代价子母树设有一排数，共ｎ个，例如：2214713261511。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。输入、输出数据格式与“石子合并”相同。SampleInput4125164SampleOutput－１２－５１６４１
浙公网安备 33021202002483