搜索
第六讲计算思维之问题求解思想•主题一探讨问题求解过程•主题二相关知识的认识与了解•主题三关于算法的理解•主题四算法策略大搜罗•主题五几个经典案例的算法实现主题一探讨问题求解过程•计算思维问题求解综述•问题求解案例•问题求解框架计算思维问题求解综述•随着社会的发展与科技的进步，出于对问题计算时间和复杂度等多方面因素的考量，现实世界中的很多问题需要借助计算机帮我们计算！•可是，我们知道，现代计算机的工作原理是存储程序和程序控制，也就是说，现代计算机只能对可计算性问题进行计算，但是具体怎么计算，计算机却不知道，这需要人来告诉计算机。•人与计算机的对话沟通方式就是通过程序控制指令。计算思维问题求解综述•可是，这程序指令应该怎么写才能让计算机“心领神会”并“游刃有余”地完成预期的计算呢？这其中涉及到程序指令的语法和算法。–简单地说，语法是具体书写程序指令的格式约束规则；–算法是解决问题的具体方法步骤，而算法又是建构在问题求解的数学模型和数据结构等诸多知识之上。–数学模型是指经过分析抽象的建模过程将具体问题转化为形式化、符号化和公式化的数学语言描述；–数据结构是指计算机对数据进行存储、组织和操作运算的方式。计算思维问题求解综述•那么，运用计算思维理念去求解问题和我们日常求解问题的过程有什么不同？运用计算思维进行问题求解过程都涉及到哪些环节和因素？–计算思维=数学建模？–计算思维=算法？–计算思维=数据结构？–计算思维=编程序？计算思维问题求解综述•事实上，单一的划等号都不能全面精确地定位计算机思维。如果一定要用一个公式表述计算思维，那么可以说：–计算思维≈人的思维+数学建模+数据结构+计算算法+程序设计！人的思维数学建模数据结构计算算法程序设计计算思维问题求解综述•我们关注的是从一个在看似平常或看似纷繁的事物或事件中能够洞析和发现问题，并提出问题到抽象归纳出解决问题的算法直至最终解决问题的整个思想过程！而这个过程正是计算思维的问题求解思想的全过程。主题一探讨问题求解过程•计算思维问题求解综述•问题求解案例•问题求解框架问题求解案例•首先，让我们从一个具体的问题出发–了解和认识运用计算思维理念去求解问题相比我们常规下求解问题的思考过程有什么不同？–以及运用计算思维进行问题求解过程都涉及到哪些环节和因素？问题求解案例—案例描述•有三根相邻的柱子，假设标号分别为A、B、C，其中A柱子从下到上按金字塔状依次叠放了N个不同大小的圆盘，现要把A柱子上的所有圆盘一次一个地移动到C柱子上，移动的过程中可以借助B柱子做中转，并且每根柱子上的圆盘必须始终保持上小下大的叠放顺序。–请问至少需要多少次移动步骤才能够全部完成？–并描述每一次圆盘的移动轨迹。问题求解案例—案例分析•首先来考虑一下N个圆盘由一根柱子移动到另一根柱子上并重新摞好需要移动多少次吧。然后再考虑每只圆盘的移动轨迹。问题求解案例—案例分析•按照汉诺塔的移动约束规则：–当只有1个圆盘的时候，当然是移动1次；–2个圆盘的时候是移动3次；–3个圆盘的时候就用了7次。问题求解案例—案例分析•按照汉诺塔的移动约束规则：–当4个圆盘的时候，就相当是一个大圆盘上面叠放了一组圆盘（三个圆盘），只要把这一组圆盘先挪到中转柱子B上，这样最大的圆盘就可以移动到目标柱子C上了，然后，再把那中转柱子B上的一组圆盘移动到目标柱子C上，整个移动过程就结束了。–一组圆盘是3个，需要7步移动到中转柱子B上，最大的圆盘需要1步移动到目标柱子C上，一组圆盘还需要从中转柱子B上再移动到目标柱子C上，这样一组3个圆盘又需要7步。–所以4个圆盘的移动步骤次数为：7+1+7=15步！问题求解案例—案例分析•如果是N个圆盘的情况，就相当是一个大圆盘上面叠放了一组圆盘（N-1个圆盘），只要把这一组圆盘先移动到中转柱子B上，这样最大的圆盘就可以移动到目标柱子上C了，然后，再把那中转柱子B上的一组圆盘移动到目标柱子C上。•这样就可以写出计算N个圆盘的移动次数H(N)的计算公式。一组圆盘是N-1个，需要H(N-1)步移动到中转柱子B上，最大的圆盘需要1步移动到目标柱子C上，一组圆盘还需要从中转柱子B上再移动到目标柱子C上，这样一组N-1个圆盘又需要H(N-1)步。•所以N个圆盘的移动步骤次数为：H(N)=H(N-1)+1+H(N-1)=2*H(N-1)+1问题求解案例—案例总结•现在我们得出：1个圆盘的时候用了1次，2个圆盘的时候用了3次，3个圆盘的时候用了7次，4个圆盘的时候用了15次。•只要把N(N0)的值代入上面的算式，就能递推出对应N的具体次数：–H(1)=1=21-1–H(2)=2*H(1)+1=3=22-1–H(3)=2*H(2)+1=7=23-1–H(4)=2*H(3)+1=15=24-1–H(5)=2*H(4)+1=31=25-1–⁞–H(N)=2*H(N-1)+1=2N-1问题求解案例—案例总结•N个圆盘的移动操作过程：–N个圆盘就相当于一个大圆盘上面叠放了一组圆盘（N-1个圆盘）；–N-1个圆盘就相当于一个大圆盘上面叠放了一组圆盘（N-2个圆盘）；–……–依此类推，直到剩下3个圆盘就相当于一个大圆盘上面叠放了一组圆盘（2个圆盘）；–这样就回归到处理2个圆盘的问题，最后就是1个圆盘的问题。–整个移动过程都在重复着这样的操作过程。问题求解案例—案例引伸思考•可是，现在的问题是，虽然已经掌握了移动的规律，但是每只圆盘的移动轨迹到底应该怎么标记出来呢？难道必须移动一个圆盘，记录一次移动轨迹？虽然移动过程简单，但是当圆盘数量递增时，标记的数量确是巨大的。•就拿N=64来说，圆盘移动次数是：264-1=18,446,744,073,709,551,616，这真是个天文数字呀！显然，这时还依然固执地采用手工标记，那绝对就是一项不可能完成的任务了！问题求解案例—案例引伸思考•那么，能不能求助于计算机来帮忙计算一下呢！？•能与不能，这需要进一步的分析和评估，同时也需要考虑怎样才能把这个问题转换成计算机可计算的描述。•在不了解运用计算思维进行问题求解框架的情况下，确实不知道从何下手！主题一探讨问题求解过程•计算思维问题求解综述•问题求解案例•问题求解框架问题求解框架•通过计算机解决一个具体问题时，大致需要经过下列几个步骤：–首先要从具体问题中抽象出一个适当的数学模型，–然后选择并确定合适的数据结构并设计一个解此数学模型的算法，–最后编出程序、进行测试、调整直至问题得到最终解答。问题求解框架观察问题归纳抽象数学建模数据结构算法描述程序设计实现解决观察问题分析问题收集信息经验知识推理判断找出方法实现解决人类之问题求解过程结合已有知识经验做各种假设性判断推理在假设和尝试中总结方法最后经过计算验证实现计算思维之问题求解过程结合数学的形式化表示考虑计算机的限制和可行性抽象出可计算性算法描述最后提交计算机验证实现问题求解框架•寻求数学模型的实质是分析问题，从中抽象提取操作的对象，并找出这些操作对象之间蕴含的关系，然后用数学的语言加以描述。•计算机算法与数据结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。•运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。问题求解框架•如果将汉诺塔问题转换为用计算机可处理的方法描述首先必须建立数学模型，就是将操作过程符号化和公式化；可是符号和公式的表示必须符合计算机的数据结构规范；另外，操作的过程会涉及到选择判断和循环重复，则又会涉及到了计算机的程序设计控制结构等。问题求解框架•虽然我们在这里并不打算牵扯编程，但是操作步骤的表述需要了解这些结构和控制的可行性，以确定每种处理方法都是在计算机的能力和极限范围之内的。最后再将所有问题求解的操作步骤用规范的算法表示形式描述出来。