《算法设计与分析》课程报告
课题名称：_________算法设计与分析__________
课题负责人名（学号）：
同组成员名单（角色）：
指导教师：
评阅成绩：
评阅意见：
提交报告时间：20##年 6月 12日
第二章 递归与分治策略
2-3 改写二分搜索算法
1. 问题描述：设a[0:n-1]是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
2. 分析与证明：设a[0:n-1]是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相等，均为x在数组中的位置。
3. 代码实现：
template<class Type>
int BinarySearch(Type a[ ],const Type& x,int left,int right, int &i, int &j )
{
while (left<=right){
int mid = (left+right)/2;
if (x == a[mid]) { i=j=mid; return 1; }
if (x < a[mid]) right = mid-1;
else left = mid+1;
}
i=right; j=left;//或i=left-1;j=left
return 0;
}
5.问题：改写二分搜索算法，返回小于x的最大元素位置i和大于x的最小元素位置j。当找到与x同的元素时，i和j相同，均为x在数组中的位置
第三章 动态规划
3-5 编辑距离问题
1. 问题描述：设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
1) 删除一个字符；
2) 插入一个字符；
3) 将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称谓字符串A到B的编辑距离，记为d（A,B）。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d（A,B）。
2. 分析与证明：
a. 开一个二维数组d[i][j]来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求
b. 具体算法：
c. 首先给定第一行和第一列，然后，每个值d[i,j]这样计算：d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+(s1[i]==s2[j]?0:1));
d. 最后一行，最后一列的那个值就是最小编辑距离
3. 代码实现：
#include <iostream>
#include <fstream.h>
#include <stdio.h>
#include <string.h>
int i,j;
char* s1 = new char[80];
char* s2 = new char[80];
int md[81][81];
int min(int a, int b, int c);
int editDistance(int len1, int len2); //最短编辑距离
void main()
{
fstream inDst;
inDst.open("E:\\input.txt",ios::in,0);
inDst>>s1;
inDst>>s2;
inDst.close();
fstream outDst;
outDst.open("E:\\output.txt",ios::app,0);
outDst<<editDistance(strlen(s1), strlen(s2));
outDst.close();
}
int min(int a, int b, int c)
{
int temp=(a<b) ? a : b;
return (temp<c) ? temp : c;
}
//最短编辑距离
int editDistance(int len1, int len2)
{
//当某一个字符串为空时，最短编辑距离是另外一个字符串的长度。
for(i=0; i<=len1; i++)
{
md[i][0]=i;
}
for(j=0; j<=len2; j++)
{
md[0][j]=j;
}
for(i=1; i<=len1; i++)
{
for(j=1; j<=len2; j++)
{
int cost=(s1[i-1]==s2[j-1]) ? 0 : 1;
int delet=md[i-1][j]+1;
int insert=md[i][j-1]+1;
int substit=md[i-1][j-1]+cost;
md[i][j]=min(delet, insert, substit);
}
}
return md[len1][len2];
}
4. 测试数据：
Input.txt
fxpimu
xwrs
运行结果：
Output.txt
5
5．复杂度分析：二重for循环复杂度为O(n^2)
第四章 贪心算法
4-9 汽车加油问题
1. 问题描述：一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
2. 证明与分析：
① 解题思路：
先判断是否有解，再对数组从1到k+1计算尽量往前走，直至不能走就+1，计算出最大
② 算法策略：贪心算法
③ 基本变量描述：
data[]和数组a[]都是用来保存k+1个距离值，sum和total均用来记录最少加油次数，total=-1表无解
3. 代码实现：
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include<fstream.h>
int CarInGas(int a[],int n,int k);
int main()
{
int i,k,n,data[100],total;
fstream rData;
rData.open("E:\\input.txt",ios::in,0);
rData>>n>>k;
for(i=1;i<=k+1;i++)
{
rData>>data[i];
}
total = CarInGas(data,n,k);
rData.close();
fstream wData;
wData.open("E:\\output.txt",ios::app,0);
if(!wData)
{
cout<<"False to open file."<<endl;
}
if(total==-1)
{
cout<<"No solution!"<<endl;
wData<<"No solution!"<<endl;
}
else
{
cout<<total<<endl;
wData<<total<<endl;
}
wData.close();
system("pause");
return 0;
}
int CarInGas(int a[100],int n,int k)
{
int i,sum=0,curDistan=0;
for(i=1;i<=k+1;i++)
{
if(a[i]>n)
return -1;
}
for(i=1;i<=k+1;i++)
{
curDistan= a[i]+curDistan;
if(curDistan>n)
{
sum++;
curDistan=a[i];
}
}
return sum;
}
4. 测试数据：
Input.txt
7 7
1 2 3 4 5 1 6 6
运行结果：
Output.txt
4
5. 复杂度分析：
for(i=1;i<=k+1;i++)
rData>>data[i];
复杂度为：O(n)
CarInGas(a,n,k)也为 O(n)
两者互不嵌套，所以为O(n)
第五章 回溯法
5-13 工作分配问题
1. 问题描述：设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法。为每一个人都分配1件不同的工作，并使总费用达到最小。
2. 分析与证明：
由于每个人都必须分配到工作，在这里可以建一个二维数组allot[i][j]，用以表示i号工人完成j号工作所需的费用。给定一个循环，从第1个工人开始循环分配工作，直到所有工人都分配到。为第i个工人分配工作时，再循环检查每个工作是否已被分配，没有则分配给i号工人，否则检查下一个工作。可以用一个一维数组flag[j]来表示第j 号工作是否被分配，未分配则flag[j]=0，否则flag[j]=1。利用回溯思想，在工人循环结束后回到上一工人，取消此次分配的工作，而去分配下一工作直到可以分配为止。这样，一直回溯到第1个工人后，就能得到所有的可行解。在检查工作分配时，其实就是判断取得可行解时的二维数组的一下标都不相同，二下标同样不相同。
这样，得到了所有的可行解。为了得到最少的费用，即可行解中和最小的一个，故需要再定义一个全局变量cost表示最终的总费用，初始cost为allot[i][i]之和，即对角线费用相加。在所有工人分配完工作时，比较sumFare与cost的大小，如果sumFare小于cost,证明在回溯时找到了一个最优解，此时就把sumFare赋给cost。
考虑到算法的复杂度，可以设计一个剪枝函数。就是在每次计算局部费用变量sumFare的值时，如果判断sumFare已经大于cost，就没必要再往下分配了，因为这时得到的解必然不是最优解。
3. 代码实现：
#include<iostream.h>
#include <fstream.h>
//using namespace std;
#include <stdlib.h>
int n;
int cost=0; //现行最小费用
int flag[100]; //工作是否被分配，“1”代表已分配
int allot[100][100]; //表示i号工人完成j号工作的费用
int WorkAllocation(int i,int sumFare);
int main()
{
fstream rData;
rData.open("E:\\input.txt",ios::in,0);
rData>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
rData>>allot[i][j];
flag[j] = 0;
}
cost+=allot[i][i]; //对角线费用相加，用于剪枝
}
rData.close();
fstream wData;
wData.open("E:\\output.txt",ios::app,0);
if (!wData)
{
cout<<"False to open file."<<endl;
}
wData<<WorkAllocation(1,0)<<endl;
wData.close();
system("pause");
return 0;
}
int WorkAllocation(int i,int sumFare)
{
if(i>n && sumFare<cost) //大于cost则必定不是最优解，跳过
{
cost = sumFare;
return 1;
}
if(sumFare<cost)
{
for(int j=1;j<=n;j++)
{
if(flag[j] == 0)
{
flag[j] = 1;
WorkAllocation(i+1,sumFare+allot[i][j]);
flag[j] = 0;
}
}
}
return cost;
}
4. 测试数据：
Input.txt
3
10 2 3
2 3 4
3 4 5
运行结果：
Output.txt
9
5.复杂度分析:从main函数中的for循环中可以看出其算法复杂度为O(n^2)
第六章 分支限界法
6-6 n皇后问题
1. 问题描述：在n x n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题等价于在n x n各的棋盘上放置n个皇后，任何两个皇后不放在同一行或者同一列或者同一斜线上。设计一个解n皇后问题的队列式分支限界法，计算在n x n个方格上放置彼此不受攻击的n个皇后的一个放置方案。
2. 分析与证明：题目要求我们只需要输出摆放皇后的一中解，所以在分支限界法时，每一种皇后的摆放即为一条分支，而遍历解空间相当于广度优先遍历树，因此只要将n个皇后摆放完成，便可以输出解，并不存在最优解的情况。
3. 代码实现：
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
fstream minput("D:\\input.txt");
fstream moutput("D:\\output.txt");
class Node
{
public:
Node(int n)
{
t=0;
this->n=n;
loc = new int[n+1];
for (int i=0;i<=n;++i)
{
loc[i]=0;
}
}
Node(const Node &other)
{
this->t=other.t;
this->n=other.n;
this->loc=new int[n+1];
for (int i=0;i<=n;++i)
{
this->loc[i]=other.loc[i];
}
}
int t;
int *loc;
int n;
bool checkNext(int next);
void printQ();
};
bool Node::checkNext(int next)
{
int i;
for (i=1;i<=t;++i)
{
if (loc[i]==next)
{
return false;
}
if (loc[i]-next==t+1-i)
{
return false;
}
if (loc[i]-next==i-t-1)
{
return false;
}
}
return true;
}
void Node::printQ()
{
for (int i=1;i<=n;++i)
{
moutput<<loc[i]<<" ";
}
moutput<<endl;
}
class Queen
{
public:
int n;
int ansNum;
Queen(int n){
this->n=n;
ansNum=0;
}
void ArrangQueen();
};
void Queen::ArrangQueen()
{
queue<Node> Q;
Node ini(n);
Q.push(ini);
while(!Q.empty())
{
Node father=Q.front();
Q.pop();
if (father.t==n)
{
father.printQ();
++ansNum;
break;
}
for (int i=1;i<=n;++i)
{
if (father.checkNext(i))
{
Node Child(father);
++Child.t;
Child.loc[Child.t]=i;
Q.push(Child);
}
}
}
}
int main(void)
{
int num;
minput>>num;
Queen Q(num);
Q.ArrangQueen();
return 0;
}
4. 测试数据：
Input.txt
5
运行结果：
Output.txt
1 3 5 2 4
5.复杂度分析：递归调用for循环，算法复杂度为O(n!)