2019 年《实用算法与程序设计》作业 2
1. 目的:了解实用算法与基本数据结构，为算法设计与实现打好基础。 2. 题目:完成下列题目的程序设计 并调试通过。
(1) 在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个 表达式中的括号是否相匹配?利用数据结构的“栈”机制，设计算法并 编写程序，判断表达式中括号匹配问题。 题目描述:输入算术表达式 A，以#键结束。其中包括:整数、四则运 算符，和六种括号“(”, “)”, “[”, “]” , “{”, “}”，请你利 用数据结构的“栈”机制设计算法并编写程序，检查算术表达式 A 的 括号是否匹配，如果匹配输出“括号匹配成功”，否则输出“括号匹配 失败”。
样例 1: 8*(3+3)/5*[9-3]+9# 输出:括号匹配成功
样例 2: 8*(9-6)/5*[3+3*{9-5}]# 输出:括号匹配成功
样例 2: 8*(9-6)/5]*[3+3*{9-5}# 输出:括号匹配失败
(2) 利用队列的性质打印 12 行的杨辉三角。 建立一个循环队列，利用队列的性质打印杨辉三角。
杨辉三角的每行除首末元素都为 1 外，其他每
个元素都是前一行该列的元素与该列左边的元素之和，根据这个关系利用 队列解决问题。front 指队头元素，rear 指向队尾元素的下一个位置，对于 每个要加入队尾的元素(除每行首末均为 1 外)都为 front 所指元素与 front+1 所指元素之和，再对队首元素出队列并输出。判断每行结束的标志
即为 front 与 front+1 所指元素均为 1。
(3) 比较算法优劣。设计与实现“连续子向量的最大和”的高效算法。 问题描述:求解“连续子向量的最大和”。输入:具有 n 个浮点数的向 量 x，输出:求解 x 向量的任何子向量中的最大和。
例如:
输入 x[0..9]:31，- 41, 59, 26，-53, 58, 97，-93，-23, 84; 输出:x[2..6]的总和是 187。 要求:(A)编写正确程序，算法的时间复杂度是 O(n* n)。
(B)编写正确分治算法程序，算法的时间复杂度是 O(n log n)。 (C)分析算法时间复杂度，比较算法优劣。 (D)思考是否有更优的算法，如何设计与编写程序。
[算法思想]
[设计原理与数据结构]
(4) 分析以下程序段的时间复杂度，请说明分析的理由或原因。 (A)
sum1( int n )
{ int p=1, sum=0, m ;
for (m=1; m<=n; m++) { p*=m ; sum+=p ; } return (sum) ;
}
(B) sum2( int n )
{
int sum=0, m, t ;
for (m=1; m<=n; m++) { p=1 ;
for (t=1; t<=m; t++)
sum+=p ; }
return (sum) ; }
(C) 递归函数
fact( int n )
{ if (n<=1) return(1) ;
else return( n*fact(n-1)) ; }
(D)两个 n 阶方阵的乘法 for(i=1，i<=n; ++i)
for(j=1; j<=n; ++j) { c[i][j]=0 ;
p*=t ;
for(k=1; k<=n; ++k) c[i][j]+=a[i][k]*b[k][j] ; }
(5) 设计与实现“8*8 棋盘的骑士周游”的算法与正确程序，并进行算法 复杂度分析。
(6) *选作题:设计与实现“统计细胞”(队列)的算法与正确程序。 题目描述:一矩形阵列由数字 0 到 9 组成,数字 1 到 9 代表细胞,细胞的 定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形 阵列的细胞个数。题目会有多组数据，对于每组数据只需输出一个数 sum，为统计出的每个矩阵中的细胞数。
输入格式:
第一行为一个数 t，表示有 t 组数据。在接下来的 t 组数据中，每组数 据的第一行会有两个整数 n、m，表示这是一个 n*m 的矩阵。从第二 行开始为一个 n 行 m 列的矩阵。其中 1<=n, m<=100，t<=20。
输出格式:
每行输出一个数 sum，为统计到的当前矩阵的中的细胞数。 输入样例:cell.in
1
4 10
0234500067 1034560500 2045600671 0000000089 输出样例:cell.out 4
3. 作业提交:
(1) 附件压缩包:
名字:实用算法 1_班级 X-姓名;
内容:ReadMe( .txt，整体一个;作业包中文件功能);
作业报告( .doc，整体一个，见附一格式要求); 程序源代码( .c/ .cpp 或其他;每个程序单独一个);
(2)提交时间:2019 年 5 月 20 日之前; (3)邮箱:zqruc2012@aliyun.com 主题词:实用算法 2_班级 X-姓名
4. 附一:作业报告书写格式(Word 文档) : 问题的提出
解题思路与算法思想
程序设计伪码算法
源程序编码清单(.cpp)或其他，
程序输入、输出 或程序运行结果截图 时间与空间复杂度分析
程序使用说明
总结与完善