资源描述：
《算法分析与设计习题集》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、序号项目名称任务描述设计要求1．C语言词法分析算法设计与实现编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。输入：一段C语言程序输出：每个单词以及每个单词所在行号比如：输入如下一段C程序main() {inta,b;}输出为：(mian,”line=1”);((,”line=1“);(),”line=1”）；({,”line=2”）;(int,“line=2”)；…
2、…………用Java语言，或者C语言，推荐用Java语言。完成所要有的C语言词法分析器。要求：读文件，或者命令行的形式读取C源程序，输出源程序中每个单词以及每个单词所在行号。要求：开发出图形化界面，读文件，把结果输出到界面上。1．行程编码的设计与实现Run-LengthEncoding（RLE）行程长度的原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee，则可用3a1b6c2d3e来代替。对于拥有大面积，相同颜色区域的图像，用RLE压缩方
3、法非常有效。算法输入：图像算法输出：图像行程编码序列利用C语言，或者Java语言，完成算法对图像的行程编码.设计一个GUI界面，能够接受图像，输出图像的形成编码序列2．特征权重排序信息增益算法的设计与实现在文本分类领域中，信息增益IG是一种常用的特征排序算法的标准。要求利用信息增益公式计算每个特征的信息增益值，并根据信息增益值从大到小输出。举例如下：假设文本中包括的特征：outlook{sunny,overcast,rainy}//晴天、多云、下雨temperature{hot,mild,cool}
4、//热、温和的、冷humidity{high,normal}//high表示潮湿、normal表示正常windy{Strong,weak}//TRUE表示有风、FALSE表示无风play{yes,no}yes表示打网球，no表示不打网球假设有14个样本如下：1,Sunny,Hot,High,Weak,No2,Sunny,Hot,High,Strong,No3,Overcast,Hot,High,Weak,Yes利用Java语言实现样本中特征信息增益的计算，然后根据信息增益值从大到小排序。4,Rain
5、,Mild,High,Weak,Yes5,Rain,Cool,Normal,Weak,Yes6,Rain,Cool,Normal,Strong,No7,Overcast,Cool,Normal,Strong,Yes8,Sunny,Mild,High,Weak,No9,Sunny,Cool,Normal,Weak,Yes10,Rain,Mild,Normal,Weak,Yes11,Sunny,Mild,Normal,Strong,Yes12,Overcast,Mild,High,Strong,Yes1
6、3,Overcast,Hot,Normal,Weak,Yes14,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-分别为正例和负例占总记录的比例显然Entrop（S）=-(9/14)*log2(9/14)-(5/14)*log2(5/1
7、4)我们以属性Weak为例计算Weak的信息增益：样本中属性Wind中取值为Weak的记录有样本的记录有8条，其中正例6个，负例2个；同样，取值为Strong的记录6个，正例负例各3个。我们可以计算相应的熵为：Entropy(Weak)=-(6/8)*log(6/8)-(2/8)*log(2/8)=0.811Entropy(Strong)=-(3/6)*log(3/6)-(3/6)*log(3/6)=1.0那么wind的信息增益为：Gain(Wind)=Entropy(S)-(8/14)*Entro
8、py(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例题的
