编程思维与数学思维的碰撞-昍爸的财新博客-财新网

周日在学校参加硕士生答辩，中午昍妈发来信息，说昍想出一种编写scratch程序的新方法——把电脑屏幕投影到电视屏上。

其实这个方法并不复杂，但我们之前从未这么做过。昍昍非常喜欢“折腾”，这可能跟他平时有大量的自由支配的时间有关。

晚上我回到家，他迫切地给我演示。

其实他并非想演示编程，只是想秀一下投影而已。

这么好的机会我是不会放过的，正好让他尝试解决一道程序题：

n个人站成1排，从左至右，从1开始报数，报到2的倍数的人坐下；再次报数，报到3的倍数的人如果站着则坐下，如果坐着则站起；如此反复，直到最后一次n的倍数的人切换站立→坐下的状态为止。请问，最后哪些人是站立的？

01 以编程思维求解

编程求解这类题，通常就是顺着题目的意思模拟执行一遍。说穿了，就是利用计算机强大的计算能力，在很短的时间内模拟原本人脑要用很长时间才能模拟执行完的大量步骤。

因此，编程思维的一个假设就是计算机算得足够快。程序大致如下：

#include

int main()

{

int n, i, j;

cin>>n;

int a[n+1]; //0表示站立，1表示坐下

memset(a, 0, sizeof(a));

for(i=2; i<=n; i++)

for(j=1; j<=n; j++)

if(j%i==0)

if(a[j]==1) a[j] = 0;

else a[j] = 1;

for(i=1;i<=n;i++)

if(a[i])

cout<

}

02 以数学思维求解

说到学编程，有些家长颇有顾虑，他们觉得孩子使用计算机之后，就会用枚举暴力求解，这样会导致大脑缺乏思考。

如果人按机器的做法去思考，是无法跟机器竞争的。从数学的角度来看，上面的这种机器的算法是很笨的。

一个人最后的状态是站是坐，取决于他的编号是多少个数的倍数。如果他的编号是除了1之外的偶数个数的倍数，那么他将坐→站→坐→站→…→坐→站，最后仍然是站着；反之，如果编号是除了1之外的奇数个数的倍数，那么他将坐→站→坐→站→…→坐，最后是坐着。

如果加上1，那么，上述结论正好相反，即如果一个数的因数个数是奇数，那么，他最后是站着的，否则他是坐着的。那么，剩下的问题就是：任意一个数k, 它的因数个数是偶数还是奇数呢？答案很显然，只有当这个数是完全平方时，它的因数个数才是奇数，其他时候都是偶数。因此，最后只有完全平方数编号的人是站立的。譬如n=120, 那么，最后站立的人是1，4， 9， 16， 25， 36， 49， 64， 81， 100.

从而，解决该问题的程序便成为：

for(int i=1; i<=sqrt(n); i++)

cout<

如果孩子能在考试中写下这样的程序，我估计90%的老师都会批错，因为它看上去实在背离了题目的原意，但是，这恰恰是数学的魅力，而且，这也是人能胜过机器的根源。

话题：