程序设计中两个典型问题的关联与启示
作者: 焦华
摘要:各种高级语言程序设计类教程通常都会涉及两类问题的编程——棋盘麦粒计数问题和汉诺塔金片移动问题,但并没有发现、更没有证明两者之间的关联性,也没有深入到启示层面。在文章中不仅给出了答案,而且还具体到课程教学中如何设置提问、如何引导学生思考,达到思维训练和创新能力培养的目的。由此可见对编程类人才培养有参考价值。
关键词:程序设计;教学;思维;认知;大数据
中图分类号: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