算法分析實践环节.docVIP

信息工程学院算法分析实践环节习题集（2011年） 序号 项目名称 任务描述 设计要求 指导教师 每组学生人数 C语言词法分析算法设计与实现 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。 输入：一段C语言程序 输出：每个单词以及每个单词所在行号 比如：输入如下一段C程序 main()?????????????????????????????????? { int a,b; } 输出为： ( mian, ”line=1”); ( ( , ”line=1“); ( ) , ”line=1”）； ({ , ”line=2” ）; ( int, “line=2”)； …………… 用Java语言，或者C语言，推荐用Java语言。完成所要有的C语言词法分析器。 要求：读文件，或者命令行的形式读取C源程序，输出源程序中每个单词以及每个单词所在行号。 要求：开发出图形化界面，读文件，把结果输出到界面上。 刘全中 1 行程编码的设计与实现 Run-Length Encoding（RLE）行程长度的原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee，则可用3a1b6c2d3e来代替。对于拥有大面积，相同颜色区域的图像，用RLE压缩方法非常有效outlook {sunny, overcast, rainy}// 晴天、多云、下雨 temperature {hot, mild, cool} // 热、温和的、冷 humidity {high, normal} // high表示潮湿、normal表示正常 windy {Strong, weak} // TRUE表示有风、FALSE表示无风 play {yes, no} yes表示打网球网球1 , Sunny , Hot , High , Weak , No 2 , Sunny , Hot , High , Strong , No 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 , High , Strong , No 每一个样本中5个数据值分别表示上面5个特征的取值。显然样本中有两个类，正例(play=yes)有9个，负例(play=no)有5个。用s表示样本(Sample)。熵的公式Entropy(S) =-(p+)*log(p+)-(p-)*log(p-) 其中，p+、p-分别为正例和负例占总记录的比例） -(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 Gain(Wind)=Entropy(S)-(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.029Outlook ，Humidity， W