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