程序设计中两个典型问题的关联与启示
作者： 焦华
摘要：各种高级语言程序设计类教程通常都会涉及两类问题的编程——棋盘麦粒计数问题和汉诺塔金片移动问题，但并没有发现、更没有证明两者之间的关联性，也没有深入到启示层面。在文章中不仅给出了答案，而且还具体到课程教学中如何设置提问、如何引导学生思考，达到思维训练和创新能力培养的目的。由此可见对编程类人才培养有参考价值。
关键词：程序设计;教学;思维;认知;大数据
中图分类号：TP311 文献标识码：A
文章编号：1009-3044（2022）10-0104-03
1 引言
当今的世界是处于大数据和人工智能的时代，迫切需要掌握算法及编程的技术类人才，高等学校如何面向市场需求、向社会输送合格学生是一个重要的研究课题。目前这方面的研究文章很多，但大多数局限于抽象的讨论，具体应用于课堂的价值不大。作为直面学生的一线老师，更需要落到实处的解决方案，此文从两个典型问题出发，较深入细致地探究课堂教学及人才培养，希望能达到“抛砖引玉”的效果。
2 典型问题之一——棋盘麦粒的计数
有一个古老的印度传说：舍罕王要奖赏宰相达依尔——国际象棋的发明人。国王询问他想要什么样的奖赏？他回答说：“陛下在这张棋盘的小格子放一些麦子，第1格放1粒麦子，第2格放2粒，第3格放4粒，总之，后面格子里麦粒数量总是前面格子里的2倍。这样摆满了64个格子的棋盘上所有的麦粒，就是您对仆人的奖赏！”
国王感到这要求实在太简单了，马上令人扛来麦子，但很快就不够用了。于是人们将一袋袋麦子搬来计数时，大家才发现：就算将整个印度的麦粒都取来，也达不到宰相的要求。
宰相到底要多少麦粒？若体积 1 立方米的麦粒大约有 [1.42×108]颗，问宰相要求的麦子为多少立方米[1]？
依据题意，编写C语言程序（qpmn1.c）如下：
#include "stdio.h"
#include <stdlib.h>
int main（）
{double t; //t表示麦粒体积
double s = 0; //s表示麦粒总数
double n = 1; //n表示小格子麦粒颗数
int j;
for（j=1; j<=64; j++）
{s=s+n; //各格子麦粒累加
n=n*2; //小格子麦粒数
}t=s/（1.42*100000000）;
printf（"s=%.lf颗麦粒＼n"，s）; //麦粒的颗数
printf（"t=%.lf立方米麦粒＼n"，t）; //麦粒的体积
system（"pause"）;
return 0;
}
运行得到：s=18446744073709552000颗麦粒，t=129906648406立方米麦粒。这是两个非常庞大的数量，按当时的生产力估算：用两千年的时间，全世界也难以生产出宰相要的这么多麦子[1]。
注意到这个问题本质是要计算[20+21+22+23+...+262+263]的值，由等比数列的前n项和公式得：[20+21+22+23+...+262+263=264-1]，下面编程计算[264-1]的值（由新算法产生新程序） ，得到简化的C程序代码（qpmn2.c）如下[2]：
#include "stdio.h"
#include <math.h>
int main（）
{int x = 2，y，i;
double result;
printf（"input y："）;
scanf（"%d"，&y）;
for（i=1;i<=y;i++）
{result = pow（x， i）;
result=result-1;
printf（"%.lf "，result）;
if（i%4==0） printf（"＼n"）;
}getch（）;
return 0;
}
程序运行结果如下：
运行结果的64个数据是[21-1]，[22-1]，[23-1]，...[263-1]，[264-1]的计算结果。之所以这样编程是为了进行数据比对，看到数据的变化过程，[2i-1（i=1，2...64）]表示的是前面i个棋盘格子的麦粒总数。在C语言的教学过程中，要引导学生发现问题和解决问题，培养学生的独立思考能力和创新能力。在此提问：运行结果有错误吗？如果有错，错在什么地方呢？64个数据[2i-1（i=1，2...64）]应该都是奇数，但最后的11个数据却是偶数，所以一定是错的。在程序中用result存储运算结果，定义为双精度实型（double result;） ，而double型数据只能保证15位有效数字，千万不要认为电脑输出的数字都是绝对精确有效的。若修改为无符号双长整型（unsigned long long result;） 程序代码（qpmn3.c）如下[2]：
#include "stdio.h"
#include <math.h>
int main（）
{int x = 2，y，i;
unsigned long long result;
printf（"input y："）;
scanf（"%d"，&y）;
for（i=1;i<=y;i++）
{result = pow（x， i）;
result=result-1;
printf（"%lld "，result）;
if（i%4==0） printf（"＼n"）;
}
getch（）;
return 0;
}
运行结果如下：
注意到最后的11个数据有10个已修改正确，但最后1个发生了数据溢出错误[3]。
验证一下：用Windows自带计算器选科学型可得[264-1=]18446744073709551615，而程序运行结果是18446744073709552000，两者有误差。
为什么用C语言计算庞大的数会产生错误？这个问题作为作业留给学生思考。
梳理一下思路：这个问题的计算或编程都是比较简单的，国王贸然答应宰相，是对数量缺少正确的认知，是对按几何增长的数量估算不足。常言道“不算不知道，一算吓一跳”，宰相戏弄了国王，国王有惩罚的手段吗？C语言课程教学中作为作业让学生思考，可在一个星期之后给出答案……答案是：国王要惩罚宰相必须抓住问题的关键点——麦粒数量庞大。
让宰相亲自到粮仓去数麦粒，假定1秒钟能数2粒麦子，每天数12小时，需要10年才能数出20立方米。要数完那么多麦粒将需要2900亿年……宰相能活多少年？再有每天数麦子的活法谁能承受？如此数下去人会疯掉……这类作业可拓展思维、启迪智慧[4]。
3 典型问题之二——汉诺塔金片的移动
汉诺塔问题——印度另一个古老的传说，大梵天开天辟地时做了3根宝石针，其中一根针上穿好了64片金片，金片大小不等，从下到上按由大到小的顺序。大梵天下指令让婆罗门按照以下法则移动金片：一次只能移走一片，无论在哪根针上，小片要在大片的上方。3根宝石针分别用A、B、C做标记，初始状态是A针上有64片金片，目标是将A针上的金片借助于B针全部移到C针上，请找出移动金片的步骤。
用C语言编程时要用到函数的递归调用，几乎所有的C语言教程都要写入这个典型实例，给出相关的程序代码，运行得到金片的移动步骤。下面的程序代码（hanoi_tower1.c） 有新颖的地方，对传统程序做出了改进，增加了标识和统计移动步骤的功能[5]。
#include <stdio.h>
int js=1;
int main（）
{void hn（int n，char z1，char z2，char z3）;
int m;
printf（"Please input the num of gold diskes："）;
scanf（"%d"，&m）;
printf（"The moving-step %d gold diskes：＼n"，m）;
hn（m，'A'，'B'，'C'）;
getch（）;
return 0;
}
void hn（int n，char z1，char z2，char z3）
{void mv（char x，char y）;
if（n==1）
mv（z1，z3）;
else
{hn（n-1，z1，z3，z2）;
mv（z1，z3）;
hn（n-1，z2，z1，z3）;
}}
void mv（char x，char y）
{ printf（"%d："，js）;
printf（"%c-->%c＼n"，x，y）;
if（js % 10==0） getchar（）;
js++;
}
程序运行时5片金片的移动步骤如下：
Please input the num of gold diskes：5
The moving-step 5 gold diskes：
1：A-->C 2：A-->B 3：C-->B 4：A-->C 5：B-->A 6：B-->C 7：A-->C
8：A-->B 9：C-->B 10：C-->A 11：B-->A 12：C-->B 13：A-->C 14：A-->B
15：C-->B 16：A-->C 17：B-->A 18：B-->C 19：A-->C 20：B-->A 21：C-->B
22：C-->A 23：B-->A 24：B-->C 25：A-->C 26：A-->B 27：C-->B 28：A-->C