算法分析与设计习题集

1、序号项目名称任务描述设计要求1C 语言 词法分 析算法 设计与 实现编制一个读单词过程，从输入的源程序中，识别出各个具 有独立意义的单词，即基本保留字、标识符、常数、运算 符、分隔符五大类。输入：一段 C 语言程序输出：每个单词以及每个单词所在行号比如：输入如下一段 C 程序main() int a,b; 输出为： ( mian, ”line=1”); ( ( , ”line=1“); ( ) , ”line=1”）；( , ”line=2” ）;( int, “line=2”)；用 Java 语言，或者 C 语 言，推荐用 Java 语言。 完成所要有的 C 语言词 法分析器。要求：读文件，或者命 令行的形式读取 C 源程 序，输出源程序中每个 单词以及每个单词所在 行号。要求：开发出图形化界 面，读文件，把结果输 出到界面上。2行程编 码的设 计与实 现Run-Length Encoding（RLE）行程长度的原理是将一扫描行 中的颜色值相同的相邻像素用一个计数值和那些像素的颜 色值来代替。例如:aaabccccccddeee，则可用 3a1b6c2d3e 来 代替。对于拥有大面积

2、，相同颜色区域的图像，用 RLE 压 缩方法非常有效。算法输入：图像算法输出：图像行程编码序列利用 C 语言，或者 Java 语言，完成算法对图像 的行程编码.设计一个 GUI 界面，能 够接受图像，输出图像 的形成编码序列3特征权 重排序 信息增 益算法 的设计 与实现在文本分类领域中，信息增益 IG 是一种常用的特征排序算法的标准。要求利用信息增益公式计算每个特征的信息增益值，并根据信息增益值从大到小输出。举例如下：假设文本中包括的特征：outlook sunny, overcast, rainy/ 晴天、多云、下雨temperature hot, mild, cool / 热、温和的、冷humidity high, normal / high 表示潮湿、normal 表示正常windy Strong, weak / TRUE 表示有风、FALSE 表示无风play yes, no yes 表示打网球，no 表示不打网球假设有 14 个样本如下：1 , Sunny , Hot , High , Weak , No 2 , Sunny , Hot , High , Strong ,

3、No 利用 Java 语言实现样本 中特征信息增益的计算， 然后根据信息增益值从 大到小排序。3 , Overcast , Hot , High , Weak , Yes 4 , Rain , Mild , High , Weak , Yes 5 , Rain , Cool , Normal , Weak , Yes 6 , Rain , Cool , Normal , Strong , No 7 , Overcast , Cool , Normal , Strong , Yes 8 , Sunny , Mild , High , Weak , No 9 , Sunny , Cool , Normal , Weak , Yes 10 , Rain , Mild , Normal , Weak , Yes 11 , Sunny , Mild , Normal , Strong , Yes 12 , Overcast , Mild , High , Strong , Yes 13 , Overcast , Hot , Normal , Weak , Yes 14 , Rain , Mild

4、 , High , Strong , No每一个样本中 5 个数据值分别表示上面 5 个特征的取值。 显然样本中有两个类，正例(play=yes)有 9 个，负例 (play=no)有 5 个。用 s 表示样本(Sample)。那么样本熵的 公式Entropy(S) =-(p+)*log(p+)-(p-)*log(p-)其中，p+、p-分别为正例和负例占总记录的比例显然 Entrop（S）= -(9/14)*log2(9/14)-(5/14) *log2(5/14)我们以属性 Weak 为例计算 Weak 的信息增益：样本中属性 Wind 中取值为 Weak 的记录有样本的记录有 8 条，其中正例 6 个，负例 2 个；同样，取值为 Strong 的记 录 6 个，正例负例各 3 个。我们可以计算相应的熵为： Entropy(Weak)=-(6/8)*log(6/8)-(2/8)*log(2/8)=0.811 Entropy(Strong)=-(3/6)*log(3/6)-(3/6)*log(3/6)=1.0 那么 wind 的信息增益为：Gain(Wind)=Entropy(S)-(

5、8/14)*Entropy(Weak)- (6/14)*Entropy(Strong)=0.940-(8/14)*0.811- (6/14)*1.0=0.048 同理方法计算出其他属性的信息增益。最后得到 5 个属性 的信息增益如下：Gain(Wind)=0.048 ；Gain(Humidity) =0.151 ； Gain(Outlook)=0.247 ；Gain(Temperature) =0.029那么根据信息增益大小特征排序的顺序为：Outlook ，Humidity， Wind，Temperature例题的详细请参考： http:/ 130.entry4蛇形矩 阵算法 的设计 与实现生成一个按蛇形方式排列自然数 1，2，3，4，5，N2 的(1N10)阶方阵。 例如当 N 等于 7 时，输出如下;输入：N输出：蛇形方阵实现一个图形化界面， 接收用户的输入 N，输 出蛇形方阵5填自然 数问题 算法设 计与实 现设有如图所示的 3n2 个球互连，将自然数 13n2 分别 为这些球编号，使如图：开发一个 GUI 界面，接 受数据 N,输出所要求的 填号图形6利用分 治思想 设计循

6、环赛日 程表假设有 n=2k 个运动员要进行网球循环赛。设计一个满足一 下要求的比赛日程表：(1). 每个选手必须与其他 n-1 个选手各赛一次(2). 每个选手一天只能赛一次(3). 循环赛一共进行 n-1 天利用 Java 语言开发一个 界面，输入运动员的个 数，输出比赛日程表。对于输入运动员数目不 满足 n=2k时，弹出信息 提示用户。7字符串 之间最 小编辑 距离算 法设计 与实现假设 A 和 B 是两个字符串。用最小的字符操作将字符串 A 转换为字符串 B。字符串操作包括:（1） 删除一个字符（2） 插入一个字符（3） 将一个字符改为另一个字符利用 Java 语言做一个图 形化界面，界面能够接 受两个字符串或者从文 件读取字符串，输出他 们之间的编辑距离8成等差 的素数 的求解寻找 6 个成等差级数且小于 160 的素数。利用 Java 或者 C 实现所 要的功能。9最少个 数运算 符求解 算法的 设计与 实现关于整数的二元运算#定义为(X # Y) = 十进制整数 X 的各位数字之和 * 十进制整数 Y 的最大数字+Y 的最小数字 例如，(9 # 30)=9*3+0=27.

7、对于给定的十进制 X 和 K,由 X 和#运算可以组成各种不 同的表达式.试设计一个算法，计算由 X 和#运算组成的值 为 k 的表达式最少需要用多少个#预算。利用 Java 实现所要 求的算法，开发一个 GUI 界面，接受两个数 据 X 和 K, 然后在界面 上输出需要#的个数。10放行路 线选择 算法的 设计与 实现设有 n 个城市(或者景点),今从某市出发遍历各城市，使之 旅费最少(即找出一条旅费最小的路径)输入：各城市间的旅费表有输入文件提供输出：旅费最少的一条路径及总费用。利用 Java, C 实现所要求 的算法。时间充分，设计一个图 形化界面，读入文件后 把 N 个城市的带权(花费) 显示在界面上，经过求 解后把旅费最小的路径 求出来，并显示在界面上11数组编 码和解 码问题 的求解 设计与 实现设有一个数组 A: array0.N-1;存放的元素为 0-N-1(1N=10)之间的整数，且。例如当jijAiA,N=6 时，有：A=(4,3,0,5,1,2)。此时，数组 A 的编码定义如 下:A0编码为 0；Ai编码为：在 A0,A1,Ai-1中比 Ai的值小的个数 (i=1

8、,2,N-1)上面数组 A 的编码为：B=(0,0,0,3,1,2)要求如下：（1） 给出数组 A, 利 用 Java 或者 C 求解 A 的编码.（2） 给出数组 A 的编 码后，求出 A 中 原数据。如果时间充分，设计 GUI 界面，实现所要求 的功能。12N 个自 然数中 r 个数组 合求解 设计与 实现找出 n 个自然数(1,2,3,n)中 r 个数的组合。输入 n,和 r,输 出所有的组合数。n 个数中 r 的组合，其中每 r 个数中，数不能相同。另外， 任何两组组合的数，所包含的数也不应相同。例如：当 n=5,r=3 时，所有组合为：5 4 3 ； 5 4 2 ； 5 4 15 3 2 ； 4 3 2 ； 4 2 13 2 1； total=10；分别用穷举搜索法、递 归法、回溯法实现所要 求的功能，并比较三者 的时间复杂度13猜比赛 名次问 题的求 解算法 设计与 实现五个学生 A、B、C、D、E 参加某一项比赛。甲、乙两人 在猜测比赛的结果。甲猜的名次顺序为 A、B、C、D、E， 结果没有猜中任何一个学生的名次，也没有猜中任何一对 相邻名次（所谓一对相邻名次，是指其中一

9、对选手在名次 上邻接。例如与，或者与等） 。乙猜的名次顺序为 D、A、E、C、B，结果猜中了两个学生 的名次，并猜对了两对学生名次是相邻的。问比赛结果如 何？利用穷举法，设计算法对以上问题求解。 利用 Java 或者 C 对所 描述任务进行求解。14计算合 数问题 的求解一个整数 n（n=100）可以有多种划分，使其分划得一列 整数之和为 n.例如：输入:n=4输出文件 result.out，格式内容为：43 12 22 1 11 1 1 1要求输入一个整数 n， 把划分序列输出到文件 中。15查找数 字对问 题求解 算法的 设计与 实现输入 N（2=N=100）个数字(在 0 到 9 之间),然后统计出 这组数中相邻两数字组成的链环数字对出现的次数。输入:N=200 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9输出：(7,8)=2 （8,7）=3指(7,8)、(8,7)数字对出现次数 分别是 2 次、3 次设计一个 GUI 界面，能 够接受用户的输入，也 能够从文件中读取数据。 在界面上输出所要求的 结果，并把结果存储到 文件中16无向图 最小代 价生成 树算法 的实现（1） 掌握最小代价生成树算法思想。 （kruskal 算法） ，并 利用贪心的思想改进该算法，降低其时间复杂性。（2） 设计一个有 10 个顶点的无向图，并用随机数产生其 各边的代价。（3）利用最小代价生成树算法思想，对其所产生的无向 图，找出其最小代价生成树。（1） 设计一个界面， 显示产生的无向 图。（2） 实现最小代价生 成树算法。（3）在输出界面，显 示结果。17有向图 单源最 短路径 算法的 实现（1）掌握单源最短路径算法思想。 （Dijkstra 算法）（2）

《算法分析与设计习题集》由会员ji****n分享，可在线阅读，更多相关《算法分析与设计习题集》请在金锄头文库上搜索。