《西南林业大学计算机与信息学院.ppt》由会员分享，可在线阅读，更多相关《西南林业大学计算机与信息学院.ppt（43页珍藏版）》请在三一办公上搜索。
1、西南林业大学计算机与信息学院,大学计算机基础与计算思维,第四章 算法与程序设计基础本章作者：赵家刚、林宏,本章主要内容,4.1 可计算问题 4.2 图灵机4.3 解决问题的一般方法4.4 用框图表示解决问题的算法 4.5 常用语言简介4.6 Python程序设计初步附录 Python常用知识,4.1 可计算问题,算法的概念:算法(Algorithm)是求解特定问题的步骤。算法的五个重要特性：(1)有穷性 一个算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成。(2)确定性 算法中每个步骤必须有确切的含义，读者理解不会产生二义性。(3)可行性 一个算法是能行的，即算法中描述的操作都是可以
2、通过已经实现的基本运算执行有限次来实现的。(4)输入 一个算法有0个或多个输入。(5)输出 一个算法有一个或多个输出。,4.1 可计算问题,算法的设计要求:(1)正确性 算法应当满足具体问题的需求。对正确的输入应有正确的输出。(2)可读性 算法应当尽可能设计得易读易懂，以便以进行阅读和修改。(3)键壮性 当输入数据非法时，算法也能适当地作出反应或处理，而不会意外停止或输出错误结果。(4)高效率 设计算法时应考虑使算法的执行时间尽可能短。(5)低存储量 设计算法时应考虑使算法占用的存储空间尽可能少。,4.1 可计算问题,计算的可行性是算法设计与分析的基础，也是计算机科学的理论基础。为了回答什么是
3、计算，什么是可计算性等问题，许多科学家提出了计算模型。K.哥德尔 S.C.克林尼提出了递归函数。A.M.图灵和E.波斯特各自独立地提出了抽象计算机的概念（后人把图灵提出的抽象计算机称为图灵机）。胡海星和宋方敏提出了算盘机。理论上已经证明，递归函数、图灵机、算盘机具有相同的计算能力。,可计算问题：能够在上述任何一种数学模型上编出算法(有限步骤)进行计算的问题称为可计算问题，否则就是不可计算问题。丘奇-图灵论题:能够在抽象计算机上编出算法(有限步骤)进行计算的问题称为可计算问题，否则就是不可计算问题。该论题是一个经验结论，未经证明。已得到计算科学界的公认。,4.1 可计算问题,英国数学家图灵于19
4、36年发表论可计算数及其在判定问题中的应用一文，文中提出了一种十分简单而运算能力极强的理想计算装置图灵机的概念，推进了计算机理论的发展。图灵机的基本思想就是用机器来模拟人们用纸和笔进行数学运算的过程，他把这样的过程看作是两种简单的动作，即在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置。,4.2 图灵机,图灵机在理论上能够模拟现代数字计算机的一切运算，可视为现代数字计算机的数学模型，是一种抽象的计算模型。实际上，一切“可计算”函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。图灵机能表示算法、程序和符号行的变换，因而可作为电子计算器的数学模型。,图灵(T
5、uring),图灵机(Turing Machine)的艺术表示,4.2.1 图灵机的图形表示,图灵机由以下几个部分组成：（1）一条无限长的纸带TAPE。（2）一个读写头HEAD。（3）一套控制规则TABLE。（4）一个状态寄存器。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。,图灵机模型,读写头沿着固定的纸带移动。要进行的指令（q1）存储在读写头内。图中“空白”的纸带全部填入0。有阴影的方格，包括读写头扫描到的空白，标记了1,1,B的那些方格，和读写头符号，构成了整个系统的状态。,一台图灵机是一个七元组(Q,q0,qaccept,qreject)，其中Q，都是有限集合，且满足：（1
6、）Q是状态集合；（2）是输入字母表，其中不包含特殊的空白符；（3）是带字母表，其中 且；（4）：Q-QL,R是转移函数，其中L，R表示读写头是向左移还是向右移；（5）q0Q是起始状态；（6）qacceptQ是接受状态；（7）qrejectQ是拒绝状态，且qaccept qreject。,4.2.2 图灵机的形式化定义,图灵机的计算规则,根据图灵机的形式化定义，图灵机的计算规则如下：aa,x-bb,y,D中aa是当前状态，x是当前格子的值，bb是程序下一步的状态，y是当前格的修改值，D是读写头移动的方向(L为左移，R为右移，空则表示不移动)。具体规则由算法设计者根据计算需要而定义。如:0，0-1
7、，0，R请同学们猜一下该规则的意思。,加法图灵机,根据图灵机的计算规则，人们设计了不同的图灵机来完成不同的计算。如加法图灵机、乘法图灵机、除法图灵机等。加法图灵机的规则如下:(简化版)0,0-1,0,R0,1-0,01,A-10,1,1,1-1,1,R遇到未定义的规则时停机，纸带上的内容就是计算结果。,例 用加法图灵机计算3+2,以1的个数表示数值，在纸带上的数据是111A110，表示3+2。加法图灵机的规则如下：(1)0,1-0,0(2)0,0-1,0,R(3)1,A-10,1(4)1,1-1,1,R(5)遇到无定义规则时停机,10 1 1 A 1 1 0,01 1 1 A 1 1 0,10
8、 1 1 A 1 1 0,100 1 1 1 1 1 0,00 1 1 A 1 1 0,状态10,读到的值为1的规则无定义，从而停机。计算结果为5,10 1 1 A 1 1 0,图灵机就其计算能力而言，它能模拟任何现代的计算机。丘奇-图灵论题也已经得到计算机科学界的公认。图灵机形式简洁且功能强大，但是图灵机形式化表示一个算法非常复杂。比如乘法需要近23条规则。由于计算机已经发明出来，为了充分利用计算机的计算功能，因此通常用框图（流程图）、自然语言来表示算法。,4.3 解决问题的一般方法,用计算机可以解决两类问题：(1)数值计算问题,抽象出数学模型,设计算法,编程,测试,修改,(2)非数值计算问
9、题通常要用到一些复杂的数据结构,4.3 解决问题的一般方法,用计算机解决问题的一般方法：(1)描绘出解决问题的步骤 自然语言、框图 等(2)用程序设计语言实现上述步骤,4.4 用框图表示解决问题的算法,框图又称流程图，是表达程序设计思想和程序设计步骤的一种直观工具。,开始,结束,流程线,4.4 用框图表示解决问题的算法,功能框,例子1：x=1y=3*x例子2:x=0.5y=math.sin(x),输入框,用于向程序输入数据例子：x=input(x=),用于向程序输出数据例子：print s,输出框,4.4 用框图表示解决问题的算法,单分支判断框用于解决单分支问题,例子：if x0:n=n+1,
10、False,4.4 用框图表示解决问题的算法,双分支判断框用于解决双分支问题,例子：if x0:y=1+2*xelse:y=x*2,4.4 用框图表示解决问题的算法,循环框用于解决需要反复进行的问题,例子：n=100i=1s=0while i=n:s=s+ii=i+1print s,【问题4-1】用户输入一个三位自然数，让计算机输出佰位、十位和个位。,【问题4-2】由键盘输入一个整数，如果是偶数则输出“偶数”，如果是奇数是输出“奇数”。,【问题4-3】编程计算1+2+3+n 的值，n由键盘输入。,4.5 常用语言简介,如果需要把用框图、自然语言表示的算法在计算机上执行，还需要用某种计算机语言表
11、示出来。算法是程序的灵魂，语言是灵魂的表示。计算机语言是人与计算机沟通的桥梁。,4.5.1 C语言,C语言于1972年由Dennis Ritchie在贝尔电话实验室实现Unix操作系统时开发。美国国家标准协会（ANSI）于1983年为C语言制定了第一个ANSI标准，称为ANSI C，简称标准C。C+、C#、Java语言这三种语言都是从C语言派生出来的，C语言的知识几乎都适用于这三种语言。C语言是一种通用的、程序结构化、面向过程的计算机程序设计语言。,问题1 用C语言程序实现1+2+100的值。,#includevoid main()int i,sum;sum=0;for(i=1;i=100;i
12、+)sum=sum+i;printf(1+2+100=%d,sum);,4.5.2 VB语言,Visual Basic（以下简称VB）是美国Microsoft(微软)公司旗下的一个主流程序开发工具。1991年，微软公司推出了 Visual Basic 1.0。Visual：“可视的”，一种直观的图形界面(GUI)设计方法。Basic指的是一种传统的编程语言(Beginners All-Purpose Symbolic Instruction Code)。Visual Basic是在原有BASIC语言基础上的进一步发展。,问题2 用VB语言程序实现1+2+100的值。,Private Sub C
13、ommand1_Click()Dim i As IntegerDim sum As Integersum=0For i=1 To 100 Step 1 sum=sum+iNext iPrint 1+2+100=,sumEnd Sub,4.5.3 Python语言,Python由吉多范罗苏姆（Guido van Rossum）于1989年未开发。Python是一种面向对象、直译式计算机程序设计语言。Python可作脚本语言用于处理系统管理任务、进行Web编程等，一些大规模软件开发计划例如Zope、Mnet及BitTorrent，Google也广泛地使用它。注：本书使用Python 2.7,#Qu
14、es4_3pyi,s=1,0n=input(n=)while i=n:s=s+ii+=1print 1+2+3+.+,n,=,s,问题4-3的Python语言程序,1.在Idle中进行计算2.编写并执行Python程序参考大基实验6,4.6 Python程序设计初步,上机安排,完成大基实验3,课 后 作 业,习题4.7 之2，3 画出框图,附录：Python常用知识,1.运算符 算术运算符：+,-,*,/,*加，减，乘，除,乘方/求整商%求余数 关系运算符：,=,=,=,!=大于，小于，大于等于，小于等于，等于，不等 逻辑运算符：and,or,not 与，或，非 成员测试：in,not in,
15、Python的常用知识,2.赋值 y=33.表达式计算 a=3 b=5 s=a*b q=s*(1.0/2)4.输入实数 s=input(s=)5.输入字符串 x=raw_input(x=),Python的常用知识,6.输出数据print 如，print s=,s7.导入模块import 如，import math8.单分支判断语句if 如：if x0:y=-x,Python的常用知识,9.双分支判断语句if-else 如：if x0:y=-x else:y=x,Python的常用知识,10.while循环语句 如：t=1 i=1 n=10 while i=nt=t*ii=i+1 print t=,t,Python的常用知识,11.列表的使用 a=1,2,8,5,9 a2=-4 x=a0+a2 print(x)请同学们猜一下输出结果12.for循环语句 如：a=1,2,8,5,9 s=0 for x in a:s=s+x print s=,s,
