实用算法与程序设计.ppt

1,3/24/2023,1,计算机算法与程序设计 Computer Algorithms and Programming,2,3/24/2023,2,第1章 课程介绍 Course Overview,3,3/24/2023,3,Outline,内容介绍 Introduction to Course程序设计 C/C+Programming数据结构 Data Structure算法设计 Algorithm Design程序测调试与测试 Program Debug&Test教学参考书 Bibliography,4,算法与程序设计实例,实例1.1 Fibonacci 数列问题这是一个有趣的古典数学问题：有一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假设所有兔子都不死，问每个月的兔子总数为多少？分析这个问题，不满1个月的为小兔子，满1个月不满2个月的为中兔子，满3个月以上的为老兔子，老兔子每个月可以繁殖1对小兔子。可以求得每个月的兔子总数依次为1，l，2，3，5，8，13，21，34，55，89，144，。这就是Fibonacci数列。,5,算法与程序设计,6,Family Tree of Rabbits（数据结构树的处理）,7,例1.1：求解Fibonacci 数列（斐彼那契序列）第20个数。Fibonacci 数列的特点：第1，2个数分别是1，1。从第3个数开始，该数是其前面两个数之和。Fib(n)表示 Fibonacci 数列的第 n 项，n 从 1 开始。由此,Fibonacci 数列可以由如下数学表达式定义给出：Fib(1)=1;Fib(2)=1;Fib(n)=Fib(n-1)+Fib(n-2);(当n2时),8,Fibonacci数列数学模型,无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下：int fibonacci(int n)if(n=1)return 1;return fibonacci(n-1)+fibonacci(n-2);,9,Fibonacci 数列（斐彼那契序列）程序（解1）,#include using namespace std;int main()int previous1=1,previous2=1;double current;int counter;int nthFibonacci;cin nthFibonacci;/输入序列个数 20cout 1 endl;cout 1 endl;counter=3;while(counter=nthFibonacci)current=previous1+previous2;previous1=previous2;previous2=current;counter+;cout current endl;return 0;,10,Fibonacci 数列（斐彼那契序列）程序（解2）,#include using namespace std;void main()/选用数组求解 double fib1002;int n;cin n;/输入序列个数 20fib1=1;fib2=1;cout 1 fib1 endl;cout 2 fib2 endl;for(int i=3;i=n;i+)fibi=fibi-1+fibi-2;cout i fibi endl;,11,Fibonacci 数列（斐彼那契序列）程序（解3）,#include using namespace std;int n;double fib(int n);void main()cin n;/输入序列个数 20double f=fib(n);coutfendl;double fib(int n)/递归函数if(n=1)return 1;/递归条件else if(n=2)return 1;else return fib(n-1)+fib(n-2);/递归函数,12,算法与程序,输 入：有零个或多个外部量作为算法的输入。输 出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。,是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。,是满足下述性质的指令序列。,算法：,程序：,13,微软的面试题,推理游戏:教授选出两个从2到9的数，把它们的和告诉学生甲，把它们的积告诉学生乙，让他们轮流猜这两个数 甲说：“我猜不出”乙说：“我猜不出”甲说：“我猜到了”乙说：“我也猜到了”问这两个数是多少?答案是：3和4(Why?)计算机可以推理计算吗？,14,算法与程序设计实例,例1.2求解N个城市之间铺设通讯光缆的最低经济代价的最小费用问题。最小生成树,15,网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,16,最小生成树(Minimum-cost Spanning Tree),MST概述,1、ST对于有n个顶点的连通图，包括所有的顶点和仅能将这些顶点连通在一起的最少条边（n 1）的子图（又名极小连通子图），即为该连通图的生成树（ST）,2、ST的多样性对图遍历时访问的结点和经由的边就构成了生成树，因遍历的路径和选择的起始点的不同，所经由边也不同，所以一个连通图的ST有多个方案,3、MST,连通图的边带有权值，则连通图又称为网络 在网络中边上权值之和最小的生成树叫MST MST是一个具有应用价值的问题 在已知网络中求MST的方法有Kruscal和Prim两种。,17,算法与程序设计实例,解决问题：1.如何准确描述问题？算法思想；算法设计；2.如何将实际数据存放到计算机中？数据结构的选用“图”结构，“树”结构3.如何选用语句和组织程序的设计与编写？程序编码伪码算法；C/C+程序设计与编码4.如何上机调试程序？程序调试（compile,build,run;input/output）5.是否可以设计更好的程序？算法的时间复杂度分析,18,前言,哥德尔的工作揭示了有些问题是不可通过有限的步骤得以证明的，什么问题是可以通过有限的步骤证明的？沿着这个问题，哥德尔的很多工作，被应用到了可计算性的研究。什么是可以有穷证明的，从可计算性的角度来说对应于，什么是可以计算的。,19,图灵机可计算,哥德尔不完备定理出世后，在剑桥大学的图灵设想：能否有这样一台机器，通过某种一般的机械步骤，能够解决所有可以解决的数学问题。以上机器就是他提出来的图灵机。图灵机可以计算的问题，就称为图灵机可计算。,20,图灵奖的由来,1.人工智能之父与计算机之父1）图灵生平及贡献 阿兰图灵（Alan Turing），19121954，英国伦敦1936年,图灵向伦敦权威的数学杂志投了一篇论文,题为“论可计算数在判定问题中的应用（On Computer numbers with an Application to the Entscheidungs-problem）”。在这篇开创性的论文中,图灵给“可计算性”下了一个严格的数学定义,并提出著名的图灵机“(TuringMachine)的设想,21,图灵奖的由来,。”图灵机“不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能力极强的计算装置,用来计算所有能想像得到的可计算函数。图灵机理论不仅解决了纯数学基础理论问题,一个巨大的意外收获则是,理论上证明了研制通用数字计算机的可行性。”图灵机“与”冯.诺伊曼机“齐名,被永远载入计算机的发展史中。1950年10月,图灵又发表了另一篇题为机器能思考吗的论文,成为划时代之作。也正是这篇文章,为图灵赢得了人工智能之父的桂冠。,22,23,图片1：图灵1951年被选入英国皇家学会时拍摄的照片,图片2：图灵在1946年,图片3：英国曼彻斯特市为图灵塑造的雕像,24,图灵奖的由来,1.人工智能之父与计算机之父2）国际计算机的最高奖项图灵奖“图灵（Turing）奖”是美国计算机协会（ACM，Association for Computer Machinery）干 1966年设立的，专门奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家。图灵奖是世界计算机科学领域的最高奖项，与物理、化学、医学、经济学领域的诺贝尔奖齐名。,25,图灵奖的由来,设立的初衷是因为计算机技术的飞速发展，尤其到20世纪60年代，其已成为一个独立的有影响的学科，信息产业亦逐步形成，但在这一产业中却一直没有一项类似“诺贝尔”、“普利策”等的奖项来促进该学科的进一步发展，为了弥补这一缺陷，于是“图灵”奖便应运而生，它被公认为计算机界的“诺贝尔”奖。,26,图灵奖的由来,图灵机的出现，奠定了计算机科学的理论基础，计算机的出现已经主要是技术实现的问题了。据说，图灵在二战期间主持设计了一台计算机。但资料比较多的，1946年，数学家冯诺依曼主持设计了第一台计算机。但不管如何，图灵被广泛认为是“计算机之父”。现代计算机的计算能力，还是在图灵机的计算能力之内，当然速度是越来越快了。图灵开辟了一条大路，后来的科学家又开辟了一些中路小路，我们则行走在前人铺就的路上。,27,“图灵奖”科学家,1966年，美国计算机协会设立以图灵为名的“图灵奖”，用于表彰在计算机科学领域做出突出贡献的科学家。图灵奖的得主有：Ken Thompson，Dennis M.Ritchie，Minsky，“人工智能之父”McCarthy，Dijkstra，Knuth，Backus，Floyd，Hoare，Codd，Cook，Thompson，Wirth，姚期智，RSA三人，“互联网之父”Cerf和Kahn,28,内容介绍 Introduction to Course,第1部分：CC+程序设计程序设计语言的演变CC+程序简介如何实现CC+程序第2部分：数据结构程序设计的灵魂 数据结构简介数据结构的程序实现第3部分：实用算法计算机算法发展历史“图灵奖”著名科学家实用算法的程序实现,29,“图灵奖”科学家,通过从1966年开始的图灵奖，逐年介绍当年的图灵奖获得者。到目前为止，是图灵奖的第一个40年(19662005)。总共有50位杰出的科学家获得了此荣誉。到现在为止（2008年2月8日）近2年过去了。新的4位图灵奖获得者也产生了（2006年一位，2007年三位）。笔者在修订此书时，也一并将最新的获奖科学家收录于此。两年来，也发生了两位图灵奖获得者科学家一位失踪，一位离开人世的悲痛消息。他们分别是1998年图灵奖获得者、著名的数据库研究领域科学家 James Gray和1977年图灵奖获得者、Fortan程序语言和BNF范式的发明人John Backus。他们的失踪和离世是全人类的损失。,30,1972年图灵奖获得者 Edsger Wybe Dijkstra(7),Edsger Dijkstra是1950年代ALGOL语言的一个主要贡献者。ALGOL高级编程语言已经成为结构清晰，数学基础严谨的一个典范。E.W.Dijkstra是现代编程语言的主要贡献者之一，为我们理解程序语言的结构，表示方法与实现做出了巨大的贡献。E.W.Dijkstra 15年的学术著作覆盖了图论的理论工作，教育手册，解释文章和编程语言领域的哲学思考。E.W.Dijkstra也是著名的 Dijkstra 最短路径算法的作者,31,1974年图灵奖获得者 Donald Knuth（9）,“(授予Donald E.Knuth图灵奖以表彰其在)算法分析和程序语言设计领域的杰出贡献，特别是其著名的“Art of Computer Programming”系列丛书。”,32,1977年图灵奖获得者 John Backus（12）,“(授 予John Backus 图 灵 奖 以表 彰其在)可实用高级编程系统设计，特别是其在FORTRAN语言方面的设计，以及其在编程语言规约的形式化描述方面的，深奥的，杰出影响力的和持续的贡献。”,33,1983年图灵奖获得者 Dennis Ritchie,Ken Thompson(18),(授予Dennis Ritchie和Ken Thompson 图灵奖以表彰其在)通用操作系统理论领域的贡献，特别是Unix操作系统的开发与实现。,34,1984年图灵奖获得者 Niklaus Wirth(19),(授予Niklaus Wirth 图灵奖以表彰其)开发了一系列的计算机程序语言，EULER,ALGOL-W,MODULEA和PASCAL。PASCAL语言被用在计算机程序语言教学上具有重要的意义，并为将来的计算机语言，系统和结构设计提供了一个基础。,35,1986年图灵奖获得者John E.Hopcroft和Robert Tarjan（第21位）,授予John E.Hopcroft和Robert E.Tarjan 图灵奖以表彰其在 数据结构和算法设计与分析领域的重要的基础性的贡献。,36,2000年图灵奖获得者 Andrew Yao(姚期智)（第35位）,(授予姚期智图灵奖以表彰其在)计算理论领域的基础性的卓越贡献，其中包括产生伪随机数的复杂性理论，密码系统和通讯复杂性等。,37,图灵奖获得者 Andrew Yao(姚期智),姚期智先生于1967年获得台湾大学物理学士学位，1972年获得美国哈佛大学物理博士学位，1975年获得美国伊利诺依大学计算机科学博士学位。1975年至1986年曾先后在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授。1986年至2004年在普林斯顿大学计算机科学系担任 Wiliam and Edna Macaleer 工程与应用科学教授。,38,图灵奖获得者 Andrew Yao(姚期智),世界著名计算机科学家、2000年图灵奖得主姚期智先生。姚期智先生成为图灵奖创立以来首位获奖的亚裔学者，也是迄今为止获此殊荣的唯一华裔计算机科学家。姚期智先生曾先后获得哈佛大学物理学博士学位和伊利诺伊大学计算机科学博士学位，他的成功之路即为发展交叉信息科学重要性的有力例证。,39,程序设计语言图灵奖获得者(11),Alan J.Perlis(1966)ALGOLEdsger Wybe Dijkstra(1972)ALGOLJohn W.Backus(1977)FORTRANKenneth Eugene Iverson(1979)APL程序语言Niklaus Wirth(1984)PASCAL*John Cocke(1987)RISC&编译优化Ole-Johan Dahl，Kristen Nygaard(2001)Simula语言和面向对象概念Alan Kay(2003)SmallTalk语言和面向对象程序设计Peter Naur(2005)ALGOL60以及编译设计Frances E Allen(2006)并行编译技术,40,算法设计图灵奖获得者(10),Richard Hamming(1968)汉明码James Hardy Wilkinson(1970)数值分析Donald E.Knuth Art of Computer Programming*John E.Hopcroft，Robert Endre.Tarjan(1986)数据结构和算法设计*William(Velvel)Morton Kahan(1989)浮点运算姚期智(Andrew Chi-Chih Yao)(2000)伪随机数复杂性，密码系统和通讯复杂性Ronald L.Rivest,Adi Shamir,Leonard M.Adleman(2002)公钥密码技术 RSA,41,图灵奖获得者,硬件，体系结构 Maurice V.Wilkes(1967)第一台具有内部存储程序的计算机EDSACJohn Cocke(1987)RISC&编译优化图形技术和交互式系统 Ivan Edward Sutherland(1988)图形技术，CADDouglas Engelbart(1998)交互式系统，鼠标发明人网络通讯 Vinton Gray Cerf(2004)Internet TCP/IP协议Robert Kahn(2004)Internet TCP/IP协议,42,图灵奖获得者,计算理论，自动机，计算复杂性 Dana Stewart Scott(1976)自动机Michael Oser Rabin(1976)自动机Stephen Arthur Cook(1982)NP完全性Richard Manning Karp(1985)证明一个问题是否是属于NP完全Juris Hartmanis，Richard Edwin Stearns(1993)计算复杂性Manuel Blum(1995)计算复杂性，密码系统和程序检查验证,43,图灵奖获得者,人工智能 Marvin Lee Minsky(1969)神经元网络John McCarthy(1971)LISPAllen Newell，Herbert Simon(1975)Logic Theory MachineRaj Reddy，Edward Feigenbaum(1994)专家系统,44,图灵奖获得者,形式语言,程序语言语义 Robert W.Floyd(1978)编程语言语义，自动程序验证C.Antony R.Hoare(1980)Hoare Logic,CSPRobin Milner(1991)LCF，ML，CCS，PI-calculusAmir Pnueli(1996)时序逻辑和系统验证Edmund M.Clarke（2007）时序逻辑模型检查E.Allen Emerson（2007）时序逻辑模型检查Joseph Sifakis（2007）时序逻辑模型检查,45,图灵奖获得者,操作系统 Dennis MacAlistair Ritchie，Ken Thompson(1983)UNIXFernando Jose Corbato(1990)分时系统Frederick P.Brooks(1999)IBM System360 操作系统数据库 Charles W.Bachman(1973)数据库Edgar Frank Codd(1981)关系数据模型James Gray(1998)数据库和事务处理,46,自顶向下“逐步求精”,算法思想；程序建模；数据结构的选用；程序设计与伪码算法；算法求精；程序编码与调试；程序使用说明；算法复杂度分析；,经典实例：国际象棋“n皇后”问题,47,n后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,48,程序分析与建模解向量：(x1,x2,xn)显约束：xi=1,2,n隐约束：1)不同列：xixj 2)不处于同一正、反对角线：|i-j|xi-xj|数据结构：选用数组（一维？二维？）,程序建模与数据结构的选用,49,程序设计与伪码算法,回溯法模型：boolean place(int k)for(int j=1;jn)sum+;else for(int i=1;i=n;i+)xt=i;if(place(t)backtrack(t+1);,50,程序实现（other?）,#include stdio.hint count;int queen 10,column20,left20,right20;void prt1()int j;printf(No.%d,+count);for(j=1;j=8;j+)printf(%3d,queenj);printf(n);void try(int i)int j;for(j=1;j=8;j+)if(columnj,51,自顶向下“逐步求精”,算法求精；程序编码与调试；程序使用说明；算法复杂度分析；。,52,回溯法,有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,53,问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。,54,计算机算法与程序设计,数据结构+算法=程序数据结构和计算机算法是程序设计的灵魂,55,作业：,关于计算机自我情况介绍设计一个C/C+程序并实现对课程讲解的希望,