程序設計中兩個典型問題的關聯(lián)與啟示

摘要：各種高級語言程序設計類教程通常都會涉及兩類問題的編程——棋盤麥粒計數(shù)問題和漢諾塔金片移動問題，但并沒有發(fā)現(xiàn)、更沒有證明兩者之間的關聯(lián)性，也沒有深入到啟示層面。在文章中不僅給出了答案，而且還具體到課程教學中如何設置提問、如何引導學生思考，達到思維訓練和創(chuàng)新能力培養(yǎng)的目的。由此可見對編程類人才培養(yǎng)有參考價值。

關鍵詞：程序設計;教學;思維;認知;大數(shù)據(jù)

中圖分類號：TP311? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）10-0104-03

1 引言

當今的世界是處于大數(shù)據(jù)和人工智能的時代，迫切需要掌握算法及編程的技術類人才，高等學校如何面向市場需求、向社會輸送合格學生是一個重要的研究課題。目前這方面的研究文章很多，但大多數(shù)局限于抽象的討論，具體應用于課堂的價值不大。作為直面學生的一線老師，更需要落到實處的解決方案，此文從兩個典型問題出發(fā)，較深入細致地探究課堂教學及人才培養(yǎng)，希望能達到“拋磚引玉”的效果。

2 典型問題之一——棋盤麥粒的計數(shù)

有一個古老的印度傳說：舍罕王要獎賞宰相達依爾——國際象棋的發(fā)明人。國王詢問他想要什么樣的獎賞？他回答說：“陛下在這張棋盤的小格子放一些麥子，第1格放1粒麥子，第2格放2粒，第3格放4粒，總之，后面格子里麥粒數(shù)量總是前面格子里的2倍。這樣擺滿了64個格子的棋盤上所有的麥粒，就是您對仆人的獎賞！”

國王感到這要求實在太簡單了，馬上令人扛來麥子，但很快就不夠用了。于是人們將一袋袋麥子搬來計數(shù)時，大家才發(fā)現(xiàn)：就算將整個印度的麥粒都取來，也達不到宰相的要求。

宰相到底要多少麥粒？若體積 1 立方米的麥粒大約有 [1.42×108]顆，問宰相要求的麥子為多少立方米[1]？

依據(jù)題意，編寫C語言程序（qpmn1.c）如下：

#include "stdio.h"

#include <stdlib.h>

int main（）

{double t;? ? ? ? ? ?//t表示麥粒體積

double s = 0;? ? ? ?//s表示麥粒總數(shù)

double n = 1;? ? ? ?//n表示小格子麥粒顆數(shù)

int j;

for（j=1; j<=64; j++）

{s=s+n;? ? ? ? //各格子麥粒累加

n=n*2;? ? ? ? //小格子麥粒數(shù)

}t=s/（1.42*100000000）;

printf（"s=%.lf顆麥粒＼n"，s）;? ?//麥粒的顆數(shù)

printf（"t=%.lf立方米麥粒＼n"，t）;? ?//麥粒的體積

system（"pause"）;

return 0;

}

運行得到：s=18446744073709552000顆麥粒，t=129906648406立方米麥粒。這是兩個非常龐大的數(shù)量，按當時的生產(chǎn)力估算：用兩千年的時間，全世界也難以生產(chǎn)出宰相要的這么多麥子[1]。

注意到這個問題本質(zhì)是要計算[20+21+22+23+...+262+263]的值，由等比數(shù)列的前n項和公式得：[20+21+22+23+...+262+263=264-1]，下面編程計算[264-1]的值（由新算法產(chǎn)生新程序） ，得到簡化的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;

}

程序運行結(jié)果如下：

運行結(jié)果的64個數(shù)據(jù)是[21-1]，[22-1]，[23-1]，...[263-1]，[264-1]的計算結(jié)果。之所以這樣編程是為了進行數(shù)據(jù)比對，看到數(shù)據(jù)的變化過程，[2i-1（i=1，2...64）]表示的是前面i個棋盤格子的麥粒總數(shù)。在C語言的教學過程中，要引導學生發(fā)現(xiàn)問題和解決問題，培養(yǎng)學生的獨立思考能力和創(chuàng)新能力。在此提問：運行結(jié)果有錯誤嗎？如果有錯，錯在什么地方呢？64個數(shù)據(jù)[2i-1（i=1，2...64）]應該都是奇數(shù)，但最后的11個數(shù)據(jù)卻是偶數(shù)，所以一定是錯的。在程序中用result存儲運算結(jié)果，定義為雙精度實型（double result;） ，而double型數(shù)據(jù)只能保證15位有效數(shù)字，千萬不要認為電腦輸出的數(shù)字都是絕對精確有效的。若修改為無符號雙長整型（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;

}

運行結(jié)果如下：

注意到最后的11個數(shù)據(jù)有10個已修改正確，但最后1個發(fā)生了數(shù)據(jù)溢出錯誤[3]。

驗證一下：用Windows自帶計算器選科學型可得[264-1=]18446744073709551615，而程序運行結(jié)果是18446744073709552000，兩者有誤差。

為什么用C語言計算龐大的數(shù)會產(chǎn)生錯誤？這個問題作為作業(yè)留給學生思考。

梳理一下思路：這個問題的計算或編程都是比較簡單的，國王貿(mào)然答應宰相，是對數(shù)量缺少正確的認知，是對按幾何增長的數(shù)量估算不足。常言道“不算不知道，一算嚇一跳”，宰相戲弄了國王，國王有懲罰的手段嗎？C語言課程教學中作為作業(yè)讓學生思考，可在一個星期之后給出答案……答案是：國王要懲罰宰相必須抓住問題的關鍵點——麥粒數(shù)量龐大。

讓宰相親自到糧倉去數(shù)麥粒，假定1秒鐘能數(shù)2粒麥子，每天數(shù)12小時，需要10年才能數(shù)出20立方米。要數(shù)完那么多麥粒將需要2900億年……宰相能活多少年？再有每天數(shù)麥子的活法誰能承受？如此數(shù)下去人會瘋掉……這類作業(yè)可拓展思維、啟迪智慧[4]。

3 典型問題之二——漢諾塔金片的移動

漢諾塔問題——印度另一個古老的傳說，大梵天開天辟地時做了3根寶石針，其中一根針上穿好了64片金片，金片大小不等，從下到上按由大到小的順序。大梵天下指令讓婆羅門按照以下法則移動金片：一次只能移走一片，無論在哪根針上，小片要在大片的上方。3根寶石針分別用A、B、C做標記，初始狀態(tài)是A針上有64片金片，目標是將A針上的金片借助于B針全部移到C針上，請找出移動金片的步驟。

用C語言編程時要用到函數(shù)的遞歸調(diào)用，幾乎所有的C語言教程都要寫入這個典型實例，給出相關的程序代碼，運行得到金片的移動步驟。下面的程序代碼（hanoi_tower1.c） 有新穎的地方，對傳統(tǒng)程序做出了改進，增加了標識和統(tǒng)計移動步驟的功能[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

29：B-->A? 30：B-->C? 31：A-->C? （程序?qū)嶋H運行得到31行，太占篇幅，這里做了合并）

注意：5片金片的移動步驟前7次恰好就是3片金片的全部移動步驟，這不是偶然的而是必然的。也就是說n片金片的全部移動步驟是n+2片金片最前面的部分移動步驟（“隔代遺傳”） ，為什么有這樣的結(jié)論？在這里要設置課堂互動，讓同學們思考后回答[6]。

若程序中刪去if （js % 10==0） getchar（）;這一行，運行時若輸入35到64之間的較大自然數(shù)時，屏幕不斷向上翻滾顯示移動步驟，一直停不下來，這是為什么呢？仔細思考一下，莫非是電腦已得到結(jié)果，但顯示器的顯示速度跟不上？64片金片至少需要移動多少次才能實現(xiàn)目標呢？這個經(jīng)典問題的答案是至少需要移動18446744073709551615次。假如金片移動1次需要1秒，則共需18446744073709551615秒時間。平年有365天是31536000 秒，閏年有366天等于31622400秒，每年平均下來是31556952秒，計算結(jié)果是移完這些金片需要5845.54億年以上（18446744073709551615秒） ，然而地球至今存在不超過45億年，太陽系預期壽命科學家們預測也不過數(shù)百億年。如若超過5845.54億年，太陽系、銀河系、地球上的生物、廟宇、梵塔等，都早已灰飛煙滅。

為了驗證前面的解決方案是不是因為顯示器的顯示速度跟不上，修改程序不顯示金片的移動步驟、只統(tǒng)計移動次數(shù)的功能（hanoi_tower2.c）? [6]。

#include <stdio.h>

double js;

int main（）

{void hn（int n，char z1，char z2，char z3）;

const t=32;

int m;

for（m=1;m<=t;m++）

{js=0;

hn（m，'A'，'B'，'C'）;

printf（"%.lf? "，js）;

if（m%4==0） printf（"＼n"）;

}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）

{js=js+1;? //printf（"%c-->%c＼n"，x，y）;

}

程序運行結(jié)果如下：

1? 3? 7? 15

31? 63? 127? 255

511? 1023? 2047? 4095

8191? 16383? 32767? 65535

131071? 262143? 524287? 1048575

2097151? 4194303? 8388607? 16777215

33554431? 67108863? 134217727? 268435455

536870911? 1073741823? 2147483647? 4294967295

若將程序中語句const t=32;改成const t=64;運行時結(jié)果將一直出不來（遞歸需要時間） ，這表明電腦是邊計算邊輸出，而不是電腦已得到結(jié)果、只是顯示器的顯示速度跟不上。千萬不要小瞧這個結(jié)論，90%以上的計算機教師教了一輩子程序設計，仍然錯誤認為電腦已有答案，只是需要排隊顯示，數(shù)據(jù)量太大，顯示需要時間等候。

4 兩個典型問題的關聯(lián)與啟示

由前面的分析討論可知：棋盤麥粒計數(shù)問題中，前面i個棋盤格子的麥?？倲?shù)為[2i-1（i=1，2...64）]。而漢諾塔金片的移動問題，從程序運行結(jié)果上看，i片金片至少需要移動的次數(shù)居然也是[2i-1（i=1，2...64）]，多么神奇的巧合？不是巧合是規(guī)律，下面用數(shù)學歸納法證明：

當i=1時，移動1次，[20=21-1]

當i=2時，移動3次，[20+21=22-1]

當i=3時，移動7次，[20+21+22=23-1]

假設當i=k時，移動[20+21+...+2k-1=2k-1]次，那么當i=k+1，即A針上有k+1個盤子時，操作步驟如下：

將A針上面k個盤子借助C針移動到B針上，移動次數(shù)為[2k-1]次，之后將A針上最大盤子直接移動到C針上，移動次數(shù)為1次，最后將B針上面k個盤子借助A針移動到C針上，移動次數(shù)為[2k-1]次，總共移動次數(shù)為：

[（2k-1）+1+（2k-1）=2*2k-1=2k+1-1]

結(jié)論得證[7]。

啟示1：“趨樂避苦”是人性，決定了人類對數(shù)量的認知往往容易犯錯誤。比如初次涉及棋盤麥粒計數(shù)問題的人，不會去計算宰相要求獎勵的麥粒數(shù)量到底是多少（僅憑感覺認為并不多） ？全世界的小麥產(chǎn)量是多少？仔細計算才發(fā)現(xiàn)是非常龐大的數(shù)量。正確的選擇基于正確的認知——對客觀世界的正確認知、對人類社會的正確認知、對自身的正確認知。“認識你自己”點燃了古希臘文明火花，“知人者智，知己者明”凝聚了中國古老的智慧。與世界這個無窮大量（[β→∞]） 相比，個人就是一個無窮小量（[α→0]） 。

啟示2：“知易行難”的新解釋：無論是棋盤麥粒計數(shù)問題或是漢諾塔金片移動問題，計算出總量都不難，困難的是具體的“數(shù)麥?！焙途唧w的“移動金片”，因為具體步驟非常龐大。推廣到個人對數(shù)量的認知，大家都知道世界有75億人，中國14億人，但對這總量的感性認識并不夠，讓個人痛苦地去數(shù)一數(shù)才會有體會。很多位高權(quán)重的人、很多富有的商人容易膨脹，他們對75億分之一、14億分之一有多小缺少正確的認知。從這個角度看，自大的人是多么的愚蠢?！皬姌O則辱、情深不壽、慧極必傷”是古訓，“謙謙君子、溫潤如玉”是處世之道。

啟示3：過分強調(diào)過程考核的教學評估是有很大弊端的，因為這樣會把教師變成“數(shù)麥?！钡娜恕⒆兂伞耙苿咏鹌钡娜?。有些學校機械地、僵化地理解評估指標體系，實則偏離了頂層設計的宗旨。試想這樣為完成繁雜指標體系、收集龐大支撐材料“揮汗如雨”的教師會有多少獨立思考？又怎么能培養(yǎng)出有創(chuàng)新思維的學生？

5 結(jié)束語

課程思政是各門課程課堂教學中非常重要的組成部分，正確的“三觀”培養(yǎng)、正確的認知引導是高校人才培養(yǎng)的基石。這兩個典型的編程案例告訴我們：“千里之行，始于足下”“不忘初心，方得始終”。在“百年未有之大變局”的時代，青年學生必須努力前行，為中華民族實現(xiàn)偉大復興貢獻自己的一份力量！

參考文獻：

[1] 譚浩強.C程序設計[M].5版.北京：清華大學出版社，2017.

[2] 梅創(chuàng)社，李培金.C語言程序設計[M].北京：北京理工大學出版社，2010.

[3] 焦華.基礎編程的思考方法[J].軟件，2018，39（3）：57-62.

[4] 臺海江，許鑫，鄭光.《C語言程序設計》課程教學改革探討[J].現(xiàn)代計算機（專業(yè)版），2018（33）：74-77.

[5] 焦華.C編程教學導入線索分析[J].電腦知識與技術，2017，13（12）：126-129，156.

[6] 焦華.C/C++編程中典型案例分析與思路拓展[J].電腦與信息技術，2017，25（3）：36-39，56.

[7] 安光勇.以數(shù)學算法為基礎的C程序編程技巧[J].電子測試，2017（7）：76-77.

【通聯(lián)編輯：謝媛媛】

收稿日期：2022-01-25

作者簡介：焦華（1964—） ，男（苗族） ，貴州貴陽人，副教授，碩士，研究方向為算法與程序。