计算之树中的两类典型问题求解思维是啥

计算之树中的两类典型问题求解思维是啥

人类通过思考自身的计算方式，研究是否能由外部机器模拟，代替我们实现计算的过程，从而诞生了计算工具，并且在不断的科技进步和发展中发明了现代电子计算机。在此思想的指引下，还产生了人工智能，用外部机器模仿和实现我们人类的智能活动。随着计算机的日益“强大”，它在很多应用领域中所表现出的智能也日益突出，成为人脑的延伸。与此同时，人类所制造出的计算机在不断强大和普及的过程中，反过来对人类的学习、工作和生活都产生了深远的影响，同时也大大增强了人类的思维能力和认识能力，这一点对于身处当下的人类而言都深有体会。早在1972年，图灵奖得主Edsger Dii.kstra就曾说：“我们所使用的工具影响着我们的思维方式和思维习惯，从而也深刻地影响着我们的思维能力”，这就是著名的“工具影响思维”的论点。计算思维就是相关学者在审视计算机科学所蕴含的思想和方法时被挖掘出来的，成为与理论思维、实验思维并肩的3种科学思维之一。计算思维是计算时代的产物，应当成为这个时代中每个人都具备的一种基本能力。
　　由此可见，在介绍计算机的诞生与发展时，自然地提及计算思维的基本思想，进而再较为详细地介绍计算思维的相关概念和内涵，更容易被学生接受，并且在后续学习中主动而有意识地加强相关能力的培养。
　　3 计算思维要素的自然体现
　　算法和数论中很多内容涉及计算与计算思维，如递归就是一种典型的计算思维。递归的案例很多，可以从德罗斯特效应（Droste effect）说起，用一张图（如图1）就能很好地说明什么是德罗斯特效应，然后解释德罗斯特效应与递归的关系，因为它并非严格意义上的递归，让学生从感性的角度对递归有一个认识。再如电影盗梦空间，从现实走入一层又一层有意构建的梦境，而后又克服重重困难走出层层梦境回归现实，这部电影充斥着典型的递归思想，通过这种学生感兴趣或者采用当前热门的话题来介绍递归概念的方式，可以显著提升学生的学习兴趣，激发其学习的主动性和积极性。
　　下面我们通过与计算相关的案例进一步介绍递归，例如汉诺塔问题（Tower of Hanoi），这是目前在介绍递归的书中用的非常多的一个案例，它不仅是一个递归问题，而且通过计算我们不难发现，移动金片的次数，f（n）与宝石针上的金片个数n之间的关系是为：
　　f（n）=2n-1
　　因此当n=64时，f（n）的值将高达18，446，744，073，709，551，615，按移动一次花费1s计算，需要约5 845亿年才能完成，这样的问题在现实中几乎是无法实现的，但我们可以借用计算机的超高速，在计算机中模拟实现。由此可见，借助现代计算机超强的计算能力，有效地利用计算思维，就能解决之前人类望而却步的很多大规模计算问题。
　　相对于汉诺塔问题，斐波那契数列（Fibonacci Sequence）是更为简单、典型且易于接受的递归问题。斐波那契数列又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21……，即后一个数字是前两个数字之和，在数学上，斐波纳契数列直接被以递归的方法定义：
　　f（0）=0
　　f（1）=1
　　f（n）=f（n-1）+f（n-2）（n>=2，n∈N*） 　　这个级数与大自然植物的关系极为密切，几乎所有花朵的花瓣数都来自这个级数中的一项数字。例如，菠萝表皮方块形鳞苞形成两组旋向相反的螺线，他们的条数必须是这个级数中紧邻的两个数字（如左旋8行，右旋13行），又如向日葵花盘（见图2）。它形成了一种自然规律，现在人们也将其应用于股票、期货技术分析中，在现代物理、准晶体结构、化学等领域也都有直接的应用，为此，美国数学会从1960年代起出版了Fibonacci Sequence季刊，专门刊载这方面的研究成果。有趣的是，随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.618 033 988 7，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用，另外在取石子的博弈游戏中按此规律必能获胜。利用这种规律，我们可以用计算机模拟自然、创建人机对战的博弈游戏，以及对金融走势的分析等。
　　此外，计算机中文件夹的复制也是一个递归问题，因为文件夹是多层次性的，需要读取每一层子文件夹中的文件进行复制。扫雷游戏中也有递归问题，当鼠标单击到四周没有雷的点时往往会打开一片区域，因为在打开没有雷的四周区域时，如果其中打开的某一点其四周也没有雷，那么它的四周也会被打开，以此类推，就能打开一片区域。这些问题用递归方法实现既清晰易懂，还能通过较为简单的程序代码实现。
　　计算思维的要素还有很多，以上我们以递归为例介绍了如何通过学生喜欢并易于接受的案例将递归的概念、思维方法显现出来，并应用于各种现实的应用和问题解决中。根据计算思维的要素构造案例时，最好能够构造出3种不同层次的案例（见图3），驱动学生主动思考并领会计算思维。这3个层次包括简单的计算问题案例、与
　　通过案例的驱动、问题的解析，在强化计算思维要素的同时，也经由3种不同层次案例的递进关系逐步深化对学生计算思维能力的培养。
　　4 程序设计与计算思维
　　计算思维也可以体现在程序设计中，如经典的证比求易算法――“国王的婚姻”。这是一个很有意思的故事：一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚，公主出了这样一道题：求出48，770，428，433，377，171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个数地进行计算，他从早到晚共算了3万多个数，最终还是没有结果。国王向公主求情，公主告知223，092，827是其中的一个真因子，并说，我再给你一次机会，如果还求不出将来，你只好做我的证婚人了。国王立即回国并向时任宰相的大数学家求教，大数学家在仔细地思考后认为，这个数为17位则最小的一个真因子不会超过9位。于是他给国王出了一个主意，按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报赏金万两。最后国王用这个办法求婚成功。实际上这是一个求大数真因子的问题，由于数字很大，国王一个人采用顺序算法求解，其时间消耗非常大。当然，如果国王生活在拥有超高速计算能力的计算机的现在，这个问题就不是什么难题了，而在当时，国王只有通过将可能的数字分发给百姓，才能在有限的时间内求取结果。该方法增加了空间复杂度，但大大降低了时间的消耗，这就是非常典型的分治法，将复杂的问题分而治之，这也是我们面临很多复杂问题时经常会采用的解决方法，这种方法也可作为并行的思想看待，而这种思想在计算机中的应用比比皆是，如现在CPU的发展就是如此。同样，计算机基础教学在介绍各个知识点时，往往也是由简人难、不断深入的，随着问题复杂度的逐步提升，需要让学生掌握如何采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法。这些思想方法和思维能力是一通百通的，也是如今计算机基础教学中真正希望学生能够掌握的。
　　在日常的教学过程中，介绍这些经典的算法后，需要通过一种具体的程序设计语言将算法转换为计算机可以执行的程序，了解如何将具体问题抽象化后由计算机实现的过程，并从程序的执行效率中让学生感性地判断出算法的好坏，从而对各种算法进行评价分析，体现出在时间和空间之间，在计算机处理能力和存储容量之间需要进行折衷的思维方法。当计算机基础教育界在热议计算思维的同时，“Machine Thinking”在管理学界也成为时下最流行的词汇之一，他们认为编程特别是其思想正在成为数字时代的一项基本技能，对新时代的知识工作者而言，编程早已不是程序员的必修课，而是营销人员、业务人员甚至CEO的必修课，一些必要的编程知识成为更好地理解新技术、新服务和新商业模式的第3只眼睛。因此，对于各种专业的学生，无论文理，都应当学习一些基本的算法和程序设计，虽然很多非计算机专业的学生将来可能很少进行程序设计和系统构建这样直接应用计算科学的实践，但是在其接触到的信息技术中，计算科学的应用和计算思维的体现无处不在，而且由于计算机科学技术的发展，可以在不同的逻辑层次进行定制与开发，这也为非计算机专业学生进行计算思维培养相关的实践活动提供了可能性。对于理工科学生可以学习C、Visual Basic、Visual C++、Java、c≠}、Fortran、Python等高级程序设计语言，而对于文科专业学生可以选择学习的程序设计语言也很多，例如可以选择文科专业需要掌握的某项技能软件之上的二次开发，例如在EXCEL、WORD中的宏编程（Visual Basic Application），或者网页开发中的脚本语言VB Script或JavaScript等。而且随着程序语言向自然语言编程方向的不断发展，还可以选用起点很低的完全可视化编程语言，如RAPTOR（the Rapid AlgorithmicPrototyping Tool for Ordered Reasoning）、MIT开发的Scratch、Google开发的Blockly等，这些可视化编程语言和环境可通过简单直观的图谱结构实现编程，通过它们设计的程序和算法亦可直接转换成为c++、c#、Java等高级程序语言，为程序和算法设计的基础课程提供教学实验环境。程序设计课程应当从复杂的语法规则中解放出来，将内容重点转移到问题的抽象，算法的构造，程序的实现和评价等知识上，让学生不仅能掌握一门算法语言，更重要的是可以加深他们对相关软件实现的理解，从而进一步理解计算科学的本质――抽象和自动化。