阅读:544 输入:2017-10-16

案例:在学期前学生评优中,根据每个班级同学不同的分数段给出评级,而每个班级中不同分段的人数不等的,且有着峰值和低谷。如何实现呢?如不及格1人,及格2人,中等4人,良好2人,优秀1人。

程序1:if(a<60){

b="不及格";

}else if(a<70){

b="及格";

}else if(a<80){

b="中等";

}else if(a<90){

b="良好";

}else {

b="优秀";

}

执行次数:1×1+2×2+4×3+2×4+1×5=30

完全没利用到数据本身特点。  

程序2:if(a<80){

b="中等40";

}else if(a<70){

b="及格20";

}else if(a<90){

b="良好20";

}else if(a<60){

b="不及格10";

}else {

b="优秀10";

}

执行次数:4×1+2×2+2×3+1×4+1×5=23

利用情况一般。

程序3:if(a<80){

if(a<70){

if(a<60){

a="不及格"

}

a="及格";

}

a="中等";

}else{

if(a<90){

a="良好"

}

a="优秀"

}

程序3的设计其实就是数据结构里的赫夫曼树,发明目的是解决远距离通信的数据传输最优化问题,我们写程序的时候多考虑一些执行效率上的问题,自然很多算法和数据结构都有用武之地,算法和数据结构这个东西分开谈没意义,就向上例,数据之间没有一定的树层级关系,你用极差的算法。对了,上例的优化不针对树,如果数据中间峰值两边低谷这个顺序,用二分查找效率也是刚刚的,当然会麻烦一点,而且数据不是这个顺序怎么办,当然这是不同情况下的适应性问题了。

为什么会有这个思路呢?因为数据结构里讲到过四种数据逻辑结构,上例明显是从树形结构出发的,我们学过就会想想用集合和线性结构下的最优解,自然思路就出来了。其他运用如栈的应用,四则运算表达式求值,编译器使用栈实现递归,函数出入栈。