小议Scratch在常见算法学习中的应用

代天杰　于方军

编者按：儿童的智能是多元的，同样是Scratch，可以在艺术和工程领域大显身手，也可以在科学和数学领域深度探究，算法思维一直以来是程序教学的难点，使用Scratch语言来讲解复杂而重要的计算机算法，降低了难度，有助于算法思维的落实和拓展应用。

Scratch让编程变得足够简单，降低了编程门槛，也让孩子们体会到了编程的乐趣，那么Scratch是不是只能做一些简易的游戏，而不能进行深入编程知识——算法的学习呢？于是，我们尝试利用Scratch去实现一些算法，发现Scratch真是非常强大，很多问题都可以轻松解决，教师完全可以利用Scratch教授一些算法和数据结构，引导学生利用Scratch和算法知识去创作更加优秀的作品。

为什么要学习算法？因为很多问题，前人已经提出了非常好的解决方案，如果我们不去学习算法，就会浪费大量的时间去思考，甚至很多问题我们无法想出解决方案，从而无法实现自己的想法。学习算法后，我们就可以利用这些知识快速解决问题，实现自己的想法，同时经过算法学习训练，分析问题、解决问题的能力也会有很大的提高。

下面我们来列举几个Scratch算法的实例，希望能够对大家有所帮助。

排序算法的学习

排序应该是程序中最常用的算法，如看到一个利用Scratch统计中文录入中键盘字母键敲击次数的小程序，就可以利用排序排出每个字母的敲击次数顺序。

那么如何利用Scratch实现排序呢？Scratch虽然不支持二维数组，但它对一维数组支持得非常好，并且融合了很多字符串的操作，所以Scratch对一维数组的操作得心应手。利用Scratch实现O（N2）的算法都非常容易，如插入、冒泡、选择都可以，在这里我们以插入排序为例为大家介绍实现方法，为什么要选择插入排序是因为Scratch在链表中提供了插入功能，让插入排序实现起来非常容易。

插入排序就像我们打扑克时的插牌过程，其实插牌就是把自己摸到的牌，进行从小到大的一次排序过程。我们怎么插牌呢？摸到牌之后，首先要找到这张牌的位置，从最后一张开始找，找到比这张牌小的牌，然后把这张牌插在后面就可以了。

我们以对5（一共要摸几张牌）个数排序为例，来描述问题的实现步骤，链表a用来存储数据，i表示已经输入多少个数（我们手中已经摸了几张牌）：①清空链表。②设置i为1。③输入第一个数。④将第一个数插入链表。⑤将后面4个数插入链表。将i值加1、输入第i个数、将位置j的值设置为i-1（也就是从最后一个数开始找）、找到比输入的数小的数位置j或者位置j为0就停止、将输入的数插入到j后面即可。

Scratch实现递归

Scratch虽然不支持函数但是对过程的支持非常好，所以利用Scratch可以非常容易实现递归算法。我们举最常用的递归例子，求N的阶乘，N！=（N-1）！×N这个公式是递归算法的核心，如我们定义了一个过程阶乘（N），那么阶乘（N）就等于阶乘（N-1）乘N。我们用s来表示N的阶乘。如果N等于1，那么很显然s的值就是1，如果N不等于1，那么我们可以先计算（N-1）的阶乘s，然后N的阶乘s等于我们已经计算出的（N-1）的阶乘s乘N，实现代码如图1所示。

这种递归算法和数学中的归纳法非常相似，关键步骤有两步，第一能够求出最简单情况下，如N等于1时的值，第二能够找到由（N-1）到N的变化规律，我们再来看图2。

图2看起来非常漂亮，这是Scratch利用递归画出来的，怎么能够画出这样的图片呢？通过认真观察，我们可以发现图片的规律为：图片是由一个个由小到大的正方形旋转生成。

依据这一规律我们就可以研究绘制图片的算法，首先要研究怎么绘制一个正方形。画正方形时，可以先沿水平方向画一条边，然后向右旋转90度，再画一条边，再旋转，再画，这样就有三条边了，最后旋转一次画一条边，正方形就画好了；也就是说画正方形就是重复执行4次“画一条边，向右旋转90度”的操作。

我们如果要利用绘制正方形的规律来绘制图2的图像，就要改变每次重复的步骤：①改变画笔颜色，这样可以实现变色效果。②画一条边。③旋转91度，这样可以实现正方形的旋转效果。④边长加1，这样可以实现正方形由小变大的效果，代码如图3所示。

Scratch实现回溯

回溯算法也叫试探法，它是一种系统地搜索问题的解答过程的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

由于Scratch目前不支持局部变量，所以比较容易实现双分支问题也就是我们常说的01背包问题，而对于更多的分支问题只能用非递归算法来实现。在讲回溯算法的时候，很多书都会画一个树状的分形图来描述回溯的过程，利用Scratch可以动态展示这样一个回溯的过程（如图4）。

怎么来画这样一幅图呢？我们先来实现画一条边，利用Scratch的移动L步和移动0-L步就可以了，为什么还要移动0-L步呢？目的是为了回到出发点。

我们再实现画一个“丫”，实现步骤如下：①移动L步。②画左边。向左旋转30度，移动L步，移动0-L步。③画右边。向右边旋转60度，移动L步，移动0-L步。④回到起点。向左旋转30度，移动0-L步。

我们用递归来实现以上步骤，为了让分支越来越短，可以逐步减少移动步长L，代码如图5所示。

我们还尝试用Scratch编写经典的编程问题N皇后问题，限于篇幅就不在本文中给大家介绍了，感兴趣的老师可以到以下网址下载。（http：//yunpan.cn/cQTZFLRQucymw，访问密码为7761）

Scratch作为一款图像化编程软件，简约而不简单，不仅能够快速构建程序而且功能十分强大，教师可以利用它来教授算法和数据结构知识，让学生了解更加深奥的编程知识，培养学生的计算思维能力。此外从信息技术实验的角度，教师还可以引导学生比较不同算法的执行效率，以加深其对以上这些初级算法的理解程度。