201703考试批次《算法与数据分析》(结课作业).doc

201703考试批次
《算法与数据分析》结课作业

学生姓名 徐前峰 学习中心 济宁奥鹏
学号 201209338664
专 业 计算机科学与技术 年级层次 转升本

北京语言大学网络教育学院
《算法与数据分析》结课作业
注意：
本学期所布置的结课作业，请同学一律按照以下要求执行：
1) 结课作业提交起止时间：2017年1月21日--3月20日。（届时平台自动关闭，逾期不予接收。）
2) 结课作业课程均需通过“离线作业”栏目提交电子版，学院不收取纸介的结课作业，以纸介回寄的作业一律视为无效；
3）截止日期前可多次提交，平台只保留最后一次提交的文档，阅卷时以最后一次提交的结课作业为准，截止日期过后将关闭平台，逾期不交或科目提交错误者，按0分处理；
4) 提交文档要求：提交的文档格式为doc、rar，大小10M以内；
5) 必须严格按照每门课程的答题要求完成作业，没有按照学院要求来做的结课作业，将酌情扣分。

一. 论述题(本大题共5小题,请任选其中两道题作答,每小题25分，总分50分)
1. 分治法所能解决的问题一般具有哪些特征。
分治法所能解决的问题一般具有的几个特征是：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

2. 分支限界法设计算法有哪些步骤。
用分支限界法设计算法的步骤是：
(1)针对所给问题，定义问题的解空间（对解进行编码）；
(2)确定易于搜索的解空间结构（按树或图组织解） ；
(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

3. 常见的两种分支限界法的算法框架是什么？
常见的两种分支限界法的算法框架
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

4．回溯法中常见哪两类典型的解空间树？分析各自的使用场合及时间复杂度？
回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。 9
这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。

5．分支限界法的搜索策略是什么？
分支限界法的搜索策略是：
在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

二. 算法设计题(本大题5小题,请任选其中两道题作答,每小题25分，总分50分)
1． 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。
template<class Type>
int BinarySearch(Type a[], const Type& x, int n) {//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1
Int left=0; int right=n-1; While (left<=right)
{int middle=(left+right)/2; if (x==a[middle]) return middle;
if(x>a[middle])left=m；elseright=middle-1;；Return-1;；时间复杂性为O(logn)；
2． 利用分治算法写出合并排序的算法，并分析其时间复杂度。
void MergeSort(Type a[], int left, int right)
{
if (left<right) {//至少有2个元素
int i=(left+right)/2; //取中点
mergeSort(a, left, i);
mergeSort(a, i+1, right);
merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a }
}
算法在最坏情况下的时间复杂度为O(nlogn)。

3． N皇后回溯法。
bool Queen::Place(int k)
{ //检查x[k]位置是否合法
for (int j=1;j<k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
return true;
}
void Queen::Backtrack(int t)
{
if (t>n) sum++;
else for (int i=1;i<=n;i++)
{x[t]=i;
if ( 约束函数 ) Backtrack(t+1);
}
}

4． 最大团问题
void Clique::Backtrack(int i) // 计算最大团
{ if (i > n) { // 到达叶结点
for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; return;}
// 检查顶点 i 与当前团的连接
int OK = 1;
for (int j = 1; j < i; j++)
if (x[j] && a[i][j] == 0) // i与j不相连 {OK = 0; break;}
if (OK ) { // 进入左子树
x[i] = 1; cn++;
Backtrack(i+1);
x[i] = 0; cn--; }
if (cn+n-i>bestn) { // 进入右子树
x[i] = 0;
Backtrack(i+1); }
}

5． 统计数字问题：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n(1≤n≤109)，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。输入数据、输出结果示例

输入数据、输出结果示例
输入数据：11
输出结果：数 字: 0 1 2 3 4 5 6 7 8 9
用到次数: 1 4 1 1 1 1 1 1 1 1
void count(int n,int a[10])
{int i,x,y;
for (i=0;i<=9;i++) a[i]=0;
for (i=1;i<=n;i++)
{x=i;
while (x)
{y=x%10; a[y]++; x/=10; }
}
}