庖丁解牛 破解算法大题

郑名辉

【背景】根据浙江省信息技术选考试题来看，第14、16、17题为算法题，其中17题往往题目复杂，难度也最大，学生的丢分率非常高。而丢分率高的原因有多方面，其中之一就是根本来不及。此外因为方法不当，虽耗费大量宝贵的时间，导致效果极差。正是处于这种现状，笔者开始深入研究，希望能从中找寻出一套行之有效的解题技巧。

由于本校生源属于淳安县第三批次类学生（经历两道筛选后进入我校的学生），其底子薄，智力水平一般且无特别突出者。而算法大题，却需要很强的逻辑思维，被很多人称之为“聪明人的游戏”，故对于我们这样的学生在历届选考当中，算法第17大题往往不得不先放弃，实数无奈之举。可是根据笔者的研究与探讨发现，选考中的算法大题其实不需要太高深的理论和强大的“智慧大脑”，需要的是：平时加强思维训练，加强算法基础知识的把握，然后引入恰当的方法，“普通人”也可以解这道最难的算法大题。

【准备】

1.PPT课件1份（内含待讲解的算法大题1道及其妙解策略）

2.相关学生讲义一张，并做好课前预习

【教学过程】

一、以课件展示一道很长的算法大题（经典的第17题），引入话题

课件问：这是信息技术选考卷中的第17算法大题，拿到这道题后，你怎么入手？

情形1：先读题再逐句逐句研读代码？

老师：如果用这种方法，我想往往会导致时间不够，吃力不讨好，但结果仍然不知何处！怎么办？

情形2：猜？

老师：如果没有一定的思维推理，没有对程序代码的把握，瞎猜有用？那，又怎么办？

二、以一道题为例，逐步引入解题技巧

老师：同学们，请看题。这第一小题要求求出“-108”的2进制补码。好，这个时候我再去看题目要求，“若n<0，则将n+128转换为对应的7位2进制数，前面的符号位为1”。

引出1：如何读题？这是以例子来理解题目的比较省时且能快速理解题意的方法。

引出2：通过这道题目的解题，把握其“解决问题的方法，即算法”！

老师：对于这道题，相信同学们都可以做出来，因为它接下去就只用到一个知识点……

学生：十进制化二进制。如果没有回答，则老师可直接提出。

老师：好，既然是进制转换，那就简单了。故通过此题老师想告诉同学们两点：第一，如何快速读题;第二，此题解答的过程，其实也帮助我们掌握其算法的核心思想;第三，那就是本堂课的重点——算法的解题技巧，第1法——运用基本知識解答之！

引出老师总结的所有方法：

老师：然后我们继续看第（2）小题这3空，这个如果继续用第1法——运用基本知识解答可行吗？

学生：不可行。

老师：那怎么办？

If学生：逻辑推理，大胆猜！（第2法）

then老师：这方法合适么？如果我们对代码没有做分析，简单推理能得到答案么？

Else if学生：快速读题，把握“解决问题的方法”——算法！（第3法）

then老师：其实第（1）空已经帮我我们掌握了该算法的核心思想。

Else if学生：把握程序结构，庖丁解牛（第4法）

then老师：对。对于它，在把握算法的核心思想后，我们就需要从大结构去把握这道题。

……

老师：同学们，请大家仔细观察，该程序由3段代码构成，分别是SUB和两个自定义函数构成。如果我们搞定了他们的各自功能，则对于解题一定有帮助。

老师：从SUB过程可知，Text2.text的作用是把2进制补码的结果显示出来，故该SUB的功能是输出结果！而①处一句话，是不可能把问题解决的，通过简单逻辑推敲，它必定与下面的代码有关！

该段代码是一个bm自定义函数，其功能根据算法的核心思想，我们也可以快速断定：bm函数是补0或者补1。转化成二进制，这段代码里头显然没有。但是一个d2b（n）引起了我们的注意，它又是什么呢？

学生：下面的d2b函数！

老师：对！我们继续看，我们继续看，这段代码的结构太眼熟了，同学们，老师看出来了，你们呢？

学生：换成二进制！

老师：哪里看出来的？

学生：……

老师：平时我们联系十进制化二进制，用的是除二取余法。那上面的代码里头“p=n mod 2”是什么意思，有什么用？

学生：逻辑推理，大胆猜？

老师：可以。但是如果平时的功课做好了，就不用猜，直接确定：下面一定会出现n=n＼2或类似功能的语句。因为这两句配套使用，就实现了十进制化二进制。所以老师第一眼就把握了这段函数的结果，当然这第③空就非常简单了！答案就是n=n＼2。

现在我们已经对其结构及其各结构的功能的确定，则第②空，根据Sgn（n）>0的情况对比，很容易确定其答案为bm=”1”&d2b（n），其中的n=n+128也佐证了这一点！

老师：到了这里，我想再看第①处，则很容易想到其与bm函数有关，根据bm函数的参数可以确定答案为：bm（dec）。

这就是把握程序结构之后，带来的好处！它有助于我们从整体上把握，而不落入只见树木不见森林的困境，也无法走出算法给我们，出题人给我们事先预设好、安排好的陷阱！

三、方法总结

1.基础知识应用——对于第（1）空的进制转换。

2.逻辑推理，大胆猜！！——对于第②空，我们可以逻辑推理大胆猜，但前提是要通过第（1）空先把握该算法的核心思想！

3.快速读题，把握“解决问题的方法”——算法，在解答第（1）空和第②空时，很明显要用到。

4.把握程序结构，力争“庖丁解牛”。

通过大结构的把握，让我们做一回“庖丁”，顺利解开“算法”这道牛！

5.最后记得验算。

验算，是为了防止特例和特殊值或情况，出题人的陷阱之一，不得不防！

【课堂及课后练习】把剩余的1（课堂练习）+2（课后练习）道17算法题用上述方法去实践、练习。