程序设计中两个典型问题的关联与启示

作者: 焦华

程序设计中两个典型问题的关联与启示0

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

关键词:程序设计;教学;思维;认知;大数据

中图分类号: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

上一篇 点击页面呼出菜单 下一篇