APP下载

浅析如何让中学生轻松学习算法

2020-03-26王辉

考试周刊 2020年14期
关键词:回文数组皇后

摘 要:数据结构加算法等于程序,算法本身就难于理解,对于初学程序设计的学生,尤其在中学阶段,学生的理解能力有限,如何在难于理解较为繁杂的算法学习中找到一种适合中学生理解的方式,是在中学开展算法课程的关键。

关键词:高精度;排序;递推;递归;搜索回溯;贪心;分治算法;广度优先搜索算法;动态规划

算法有简单的,也有复杂的,我们学习任何一种新知识,都应该从简单的入手,算法在信息学奥赛这门课中,大致分为以下内容:高精度算法、数据排序、递推算法、递归算法、搜索与回溯算法、贪心算法、分治算法、广度优先搜索算法、动态规划。对于每一种类型的算法都应该循序渐进,而不应该一个内容学到底,然后在进入一个新的内容,算法的学习对于中学生来说,利用业余时间学习,需要数年的时间,学习算法前应该对一门语言有所了解,例如应该学习了数据类型、运算符、表达式、顺序结构、分支结构、循环、函数等。

学习一种类型的算法应该设置不同的问题,而这些问题由浅入深,彼此间有联系,最后在抛出一个综合的问题,抽丝剥茧,分析问题,解决问题,很多学生在学习完了一种方法之后发现一讲就懂,做题就无从下手,我们应该分析学生为何出现这种情况,算法本身就比较抽象,每个学生理解的能力都不同,具体问题具体分析,我在平时授课之余,会在学生写算法,调试程序的过程中进行跟踪,发现学生的问题,才能找到学生哪里理解有问题,哪里吸收不到位,然后进行教学反思,重新设计课件,重新设计问题及思路引导,然后再重新讲解,发现效果好了很多。算法描述一般会使用自然语言、流程图、和伪代码。在很多程序设计书籍中都推荐使用流程图,但是我发现很多程序设计老师都是介绍下流程图,最后讲解复杂程序时都用的自然语言或伪代码,我个人也偏向自然语言,算法就是解决生活中实际问题的方法,我们在讲解算法时不应该将任何问题跟程序的代码相关联,很多同学在看到问题后,第一个闪现在脑中的画面就是用循环、还是分支、还是函数、还是递归,而不是想生活中我们如何去解决这些问题的,这就让学生陷入一种先去想我学了哪些程序设计工具,看看哪个工具合适,而不是先想问题求解方法,设计出方法,再考虑这些方法的可行性,可行性没问题,再考虑用程序设计如何解决。那这种问题我们一定要对学生进行糾正,养成良好的思考顺序和习惯,才能在算法中走得更远。

下面我以在教学中的一些实例来进行说明阐述观点。

一、 输入一个数,判断其是否为回文数

其实这个问题并不难,学生已经学习了取余用“%”,也学习了取整用“/”,并且也练习了水仙花数的判断,就是将某一个3位整数的百位数、十位数、个位数取出来,然后判断每位数的3次方的和是否跟原数相等。学习了以上知识,会发现对于判断是否为回文数已经没有新知识了,把这个问题抛给学生,他们很难想出如何解决这个回文数问题。我们从实际问题出发,什么样的数为回文数,正读倒读都一样的整数为回文数,每位同学都知道,那么如何判断呢?如何取出一个整数的各个位数,大家都会,利用对10取余和取商操作即可将每位数拿出来,这个在以前学过的水仙花数中都学习过,那么取出来不是问题,如何判断呢?我们如果把它倒装回去,判断2个数的大小即可。那么看似问题解决了,仔细观察,不难发现,我们是任意输入一个整数,没有确定整数是几位数,前面学过的水仙花是固定的3位数,那么唯一的问题就是如何从一个不确定位数的整数中取出各个数,这个是以前没有讲过的,也是没有做过案例的,对于学生来说这就是一个没有学过的新知识,新知识必须新授课,需要老师引导讲解,不然几乎不可能让学生自己想出来,有效的思考是必要的,无用的思考浪费时间没有任何意义,所以我重新设计了授课方式,先从另一个问题入手,抛出另一个问题,输入一个整数n,输出每位数的和,即输入整数123,输出6。那么这个问题也是从一个不确定位数的整数中取数,然后将其累加,取数依然还是用%和/来取,这个问题相对简单,并且能将以前学过的水仙花和我们要解决的回文数联系起来,这个学生思考了几分钟之后,部分同学得出一个结论,先用整数n对10取余数,累加到s中,然后个位数的数字就可以舍去,例如123%10=3;3累加后就不再需要了,我们把123变成12,即n=n/10,在对10取余数,得到2,再次累加,如此反复,那么做到什么时候截止呢?当n>0时候做,当n为个位数时在对10取商则为0,问题解决。这个问题解决了,那我们在回头看看回文数,发现位数不确定的取数不是问题了,貌似问题解决,学生开始写算法,发现如何将取出来的数倒装呢?例如12321,最后一位取出来放到m中,如何将最后一位变成第一位,需要乘以10000,位数不确定我们不知道乘多少,乘完后还需要累加,所以我们将m初始化为0,并且将输入数n复制一份给num,每次我们都乘以10在累加,这样随着取数的过程,就可以累加出原数的倒装数,这个技巧也是以前没有过的,即while(n>0){m=m×10+n%10;n=n/10},最后我们判断num与m是否相等就可以判断输入数n是否为回文数。最后完成算法书写,程序调试。经典的算法是需要记忆的,这个记忆是打引号的,我们应该记忆的是这些算法的特征,应该记忆的是完成某个特定功能的编程技巧,而不是生硬的代码,在编程学习的过程中,我就发现一些学生在讲授过程中听课很认真,也能跟老师很流畅的做交流,写代码的时候也很流畅,过几天之后同样的问题,重新做的时候发现有些无从下手的感觉,少部分同学仍然能够写出来,这就提示我们老师在教授学生的时候要注意总结,要提醒学生哪些是需要理解的记忆,而不是背代码,学生觉得自己并没有背代码,是因为刚讲完,凭着印象在书写,很容易完成,这道例题我在给学生总结时会提示学生我们需要记忆的是我们用取数倒装累加的方式来进行判断,需要记忆的技巧是乘10累加,整数位会往左依次移动。

二、 高精度算法

在高精度算法中,高精除法的算法模拟以高精除以单精为例的较多,高精除以单精中,还是利用取商符号/来进行,在得出商c数组及下一个除数时利用的技巧在上一个实例是一致的,即c[i]=(x×10+a[i])/b;x=(x×10+a[i])%b;这种经典的编程技巧我们需要记忆,需要熟练掌握,对于以后复杂的程序我们才会想起来如何处理。

三、 递归和回溯

递归算法中同学们最难以理解的是程序进入到哪一层,递归的退出机制是什么?较为简单的递归实例我们通常以阶乘入手,然后我们可以循序渐进的接触集合的全排列,经典的例题还是汉诺塔游戏,这些例题同学们都比较容易理解,当我们进入到回溯算法时,例如素数环问题,我发现同学们很难理解,他们难理解的原因除了回溯上一步以外,仔细研究发现他们难理解的还是递归的退出,由于回溯算法中一般都会嵌套递归,搜索回溯算法中大部分程序都是迭代中加递归,这對于递归的理解更上了一个层次,导致很多同学从一层递归中退出后不知道循环变量执行到了哪里而产生困惑,我发现同学不能深入理解是因为不知道递归执行到了哪一层,回溯的步骤以及循环变量执行到具体的哪一个,找到学生困惑的根源才能给学生解惑,所以我在实际教学中会取循环变量能完成问题效果的情况下尽量小,通过画图的方式结合一步一步演示程序执行的过程中变量值的变化,让学生知道程序每一步是怎么运行的,尤其递归的退出及回溯步骤中各个变量的变化情况,让学生充分了解回溯的过程。学生理解了,程序自然写起了就会非常流畅,学生才可能在实际的问题中写出回溯的步骤。

谈到回溯自然避不开高斯提出的经典的八皇后问题,这是一个典型的回溯问题,我们在回溯问题中总结出了递归回溯的框架,有固定的2种格式,然而我们发现除了这些问题以外,保存当前状态也是一个难点,在这个问题中,八皇后问题关于行列斜线的皇后放置状态我们用了3个数组来表示,这也是一个理解难点,大名鼎鼎的约瑟夫问题,是用1个1维数组来表示人出圈的状态,学习完之后再去学习八皇后会让学生更容易理解,有些状态我们可能会用到二维数组,这也是一个技巧,有些可能用的是布尔类型的数组,在八皇后问题中我们用数组a来表示每一行的皇后,例如a位第一行的皇后,a[5]表示第5行的皇后,a[5]=3,表示第五行的皇后放置到了第3列,我们用b数组表示列是否放置了皇后,c数组和d数组来表示两种方向的斜线皇后的状态。这在后面中国象棋中跳马的遍历问题中也会用到,这些技巧需要理解的记忆。

如何让中学生轻松的学习算法这门课呢?找到学生难于理解的问题根源,将复杂问题通过有联系的实例进行讲解训练,将复杂问题用分治思想抽丝剥茧化为小问题来逐一解决,这些方法运用得当,我们惊喜地发现,很多学生对于算法的理解与掌握都上了很大一个台阶。

参考文献:

[1]黄荣燕.浅析加强中学生议论文写作思辨性的方法[J].高考,2019(3).

[2]陈辉斌.浅析初中生物教学中学生自主学习能力的培养[J].考试周刊,2019(35).

作者简介:王辉,新疆维吾尔自治区乌鲁木齐市,新疆农业大学附属中学。

猜你喜欢

回文数组皇后
变型数独4月挑战赛
JAVA稀疏矩阵算法
JAVA玩转数学之二维数组排序
VB学习天地
遇皇后
为什么皇后镇被称为“冒险之都”?
Excel数组公式在林业多条件求和中的应用
回文的美
被放逐的皇后
有趣的回文数