Scratch之高斯算法

什么是高斯算法？“数学王子”高斯小时候非常淘气，一次数学课上，老师为了让小朋友们安静下来，在黑板上列了一道很难的算式，让大家在半小时内算出。1+2+3++99+100的得数，5分钟不到高斯就举起了小手，起初老师并不在意这一举动，心想这个孩子又在捣乱了，但当他发现全班唯一正确的答案属于高斯且计算方法是(1+100)+(2+99)+(3+98)…+(50+51)=101×50=5050时，才大吃一惊！因为这种简便算法是老师从未教过的“等差数列求和”方法，后来人们把这种简便算法称作高斯算法。

那么我们用Scratcha编程的方法来设计一个“从1累加到100求和”的高斯算法程序脚本。

01

编程思路

算法是指用系统的方法描述解决问题的策略机制。涉及到数学问题时用到数学相关的算法。对于这个问题，如果你能像小高斯那样发现其中的规律，那么就可以使用“50×101=5050”这种简便算法快速报出答案了。不过，很多小朋友采用的计算方法很可能是从1累加到100，从而得到结果，这种硬算的方法对人来说比较复杂但却是计算机所擅长的，具体计算过程如下：

第1步：0+1=1；

第2步：1+2=3；

第3步：3+3=6等到第100步：4950+100=5050。

从上述计算过程可以看到，虽然每一步计算的数字都在变化，但它的计算方式却是有规律的，这就很适合使用循环结构来描述。如果用Sn表示从1累加到100的自然数的和，用i表示1到100变化的加数，那么上述计算过程的规律就是：每一步都是用上一步累加的和S加上每一步变化的加数i。这个计算规律可用公式：Sn=Sn+i来表示，注意这里的“=”是赋值的意思。

02

编程过程

1.建立循环变量i和求和变量Sn分别表示从1到100变化的加数与从1累加到100的自然数的和。

2.将变量i和求和变量Sn的初始值分别设为1和0.

3.将求和变量Sn设定为上一次累加的和Sn+本次变化的加数i,每重复执行一次，就将循环变量i增加1，共重复执行100次。

4.添加“说和停止这个脚本”指令积木，并把以上各段脚本按顺序拼接起来，得到“1到100累加求和”程序的完整脚本。

编程思路1参考代码如图1：

03

编程思路

厉害的同学们或许已经发现了小高斯无意中使用了的等差数列求和公式：sn=(a1，+an)n/2，所以他很快求出了问题的答案。

1.建立首项变量；末项变量；项数变量分别赋值为对应的回答。

2.将求和设为首项加末项的和乘以项数的积除以2，得到1累加到100的求和过程。

3.停止这个脚本

编程思路2参考代码如图2：

通过上面的编程内容得知“1+2+3+…+100”。这个程序有两种设计方法：一种是通过循环，让计算机先计算1+2，然后计算+3，接着+4、+5 … 就这样一直到 +100，这样做99次加法就能得到结果了，这是一种思路。

但是还有另外一种思路，这是利用高斯算法，因为1+100 = 2+99 = 3+98，这些结果都等于101，总共有50对101，那么计算机只需要计算50x101就能得到最后的结果（图3）。

04

小节

我们比较一下两者的过程，第一种方法要计算99次，而第二种方法只需要计算1次，你觉得哪个方法更快更好呢？

显然，正常人都选择后者。因此，文章的目的，不是让你计算出结果，而是要你用最优的方法得到结果，这才是编程的精髓。所以说，学编程的核心是算法，是同学们的编程思维。数学是一门重思考与理解、重严格的训练、充满创造性的科学，只有掌握了数学的思想方法和精神实质，才能由不多的几个公式演绎出千变万化的生动结论，显示出无穷无尽的威力。”编程也是一样要用到各种各样的数学知识，在这个过程中，同学们也能接受到很多超前的数学知识，从而慢慢形成一个同龄人不具备的高维解题视角，对数学概念的理解也更加深刻。

编程是编程，数学是数学，二者即相互独立，又有密切相关。二者都需要有一定的逻辑能力，也都能培养逻辑思维能力。学习编程，能够很好地提升逻辑思维能力，也就可以在一定程度上反哺数学的学习；数学好那么在逻辑思维能力比较强，也容易理解编程。

通过上面的编程内容加速同学们了解决数学问题；数学的逻辑思维可以帮助更好地学习和理解编程。