算法设计与分析实验指导

递归与分治二分查找合并排序快速排序回溯0-1背包问题装载问题堡垒问题（ZOJ1002）*翻硬币问题8皇后问题素数环问题迷宫问题*农场灌溉问题（ZOJ2412）*求图像的周长（ZOJ1047）*骨牌矩阵*字母转换（ZOJ1003）*踩气球（ZOJ1004）搜索Floodfill电子老鼠闯迷宫跳马独轮车皇宫小偷分酒问题*找倍数*8数码难题动态规划最长公共子序列计算矩阵连乘积凸多边形的最优三角剖分电路布线问题防卫导弹石子合并最小代价子母树旅游预算皇宫看守游戏室问题*基因问题*田忌赛马贪心与随机算法活动安排问题搬桌子问题*照亮的山景*用随即算法求解8皇后问题素数测试实验一：递归与分治实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题：二分搜索、合并排序、快速排序。对本实验中的问题，设计出算法并编程实现。试验内容和步骤1．二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。2．合并排序3．快速排序以上算法的一个执行实例如图1所示，其中pivot=L[p]=5：Partition过程的一个执行实例实验总结及思考合并排序的递归程序执行的过程实验二：回溯算法实验目的：熟练掌握回溯算法实验内容：回溯算法的几种形式实验步骤：1.回溯算法的一般模式a)用回溯算法搜索子集树的一般模式voidsearch(intm){if(mn)//递归结束条件output();//相应的处理(输出结果)else{a[m]=0;//设置状态：0表示不要该物品search(m+1);//递归搜索：继续确定下一个物品a[m]=1;//设置状态：1表示不要该物品search(m+1);//递归搜索：继续确定下一个物品}}b)用回溯算法搜索子集树的一般模式voidsearch(intm){if(mn)//递归结束条件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](换回来)}}习题1．0-1背包问题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。程序如下：#includestdio.hvoidreaddata();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;in;i++){if(a[i]==1)//如果选取了该物品{weight=weight+w[i];//累加重量value=value+v[i];//累加价值}}if(weight=c)//若为可行解if(valuemax)//且价值大于maxmax=value;//替换max}voidreaddata(){inti;for(i=0;in;i++)scanf(%d%d,&w[i],&v[i]);//读入第i件物品重量和价值}voidprintresult(){printf(%d,max);}2．装载问题考察了用最大数量的货箱装船的问题。现在对该问题做一些改动。在新问题中，有两艘船，n个集装箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi是集装箱i的重量且所有集装箱的总重量不超过c1+c2。我们希望确定是否有一种可将所有n个货箱全部装船的方法。若有的话，找出该方法。提示：求出不超过c1的最大值max，若总重量－maxc2则能装入到两艘船。3．堡垒问题（ZOJ1002）如图城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。程序主要部分如下：intmain(){readdata();//读入数据search(0);//递归搜索printresult();}voidsearch(intm){introw,col;row=m/n;//求第m个格子的行号col=m%n;//求第m个格子的列号if(m=n*n)checkmax();//检查当前解是否是可行解，若是则把它的价值与max比较else{search(m+1);//该位置不放堡垒递归搜索下一个位置if(canplace(m))//判断第m个格子是否能放堡垒{place(m);//在第m个格子上放置一个堡垒search(m+1);//递归搜索下一个位置takeout(m);//去掉第m个格子上放置的堡垒}}}4．翻硬币问题把硬币摆放成32×9的矩阵，你可以随意翻转矩阵中的某些行和某些列，问正面朝上的硬币最多有多少枚？提示：（1）任意一行或一列，翻两次等于没有翻；（2）对于9列的任何一种翻转的情况，每一行翻与不翻相互独立。5．8皇后问题在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相“冲突”（在每一横列竖列斜列只有一个皇后）。#includestdio.h#includemath.hvoidsearch(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;i8;i++)//对当前行0到7列的每一个位置{if(canplace(m,i))//判断第m个格子是否能放堡垒{place(m,i);//在(m,i)格子上放置一个皇后search(m+1);//递归搜索下一行takeout(m,i);//把(m,i)格子上的皇后去掉}}}}voidprintresult(){inti,j;for(i=0;i8;i++){for(j=0;j8;j++)if(a[i]==j)printf(A);elseprintf(.);printf(\n);}printf(\n);}intcanplace(introw,intcol){inti;for(i=0;irow;i++)if(abs(i-row)==abs(a[i]-col)||a[i]==col)return(0);return(1);}voidplace(introw,intcol){a[row]=col;}voidtakeout(introw,intcol){a[row]=-1;}6．素数环问题把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。程序如下：#includestdio.h#includemath.hvoidsearch(int);voidinit();//初始化voidprintresult();//打印结果intisprime(int);//判断该数是否是素数voidswap(int,int);//交换a[m]和a[i]inta[21];//a数组存放素数环intmain(){init();search(2);//递归搜索}voidsearch(intm){inti;if(m20)//当已经搜索到叶结点时{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]换回来}}}voidprintresult(){inti;for(i=1;i=20;i++)printf(%3d,a[i]);printf(\n);}intisprime(intnum){inti,k;k=sqrt(num);for(i=2;i=k;i++)if(num%i==0)return(0);return(1);}voidswap(intm,inti){intt;t=a[m];a[m]=a[i];a[i]=t;}voidinit(){inti;for(i=0;i21;i++)a[i]=i;}7．迷宫问题给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。程序如下：#includestdio.h#includemath.hvoidsearch(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;i20;i++){for(j=0;j20;j++)printf(%3d,a[i][j]);printf(\n);}}voidreaddata(){inti,j;for(i=0;i20;i++){for(j=0;j20;j++)scanf(%d,&a[i][j]);}}intcanplace(introw,intcol){if(row=0&&row