第4部分计算学科中的核心概念教案.ppt
《第4部分计算学科中的核心概念教案.ppt》由会员分享,可在线阅读,更多相关《第4部分计算学科中的核心概念教案.ppt(76页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第4部分计算学科中的核心概念 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望算法的历史简介算法的历史简介算法的历史简介算法的历史简介 oo公元公元825年,阿拉伯数学家阿科瓦里茨米年,阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)写了著名的波斯教科书写了著名的波斯教科书(Persian Textbook),),书中概括了进行四则算书中概括了进行四则算术运算的法则。术运算的法则。n n“算法算法算法算法”(AlgorithmAlgorithm)一词就来源于这位
2、数学家一词就来源于这位数学家一词就来源于这位数学家一词就来源于这位数学家的名字。的名字。的名字。的名字。oo后来,韦氏新世界词典将其定义为后来,韦氏新世界词典将其定义为“解某解某种问题的任何专门的方法种问题的任何专门的方法”。oo而据考古学家发现,古巴比伦人在而据考古学家发现,古巴比伦人在求解代数方求解代数方程程时,就已经采用了时,就已经采用了“算法算法”的思想。的思想。丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题 oo古希腊数学家丢番图(古希腊数学家丢番图(Diophantus):代数学:代数学之父之父n n在算术(在算术(在算术(在算术(Arit
3、hmeticaArithmetica)一书中提出了有关一书中提出了有关一书中提出了有关一书中提出了有关两两两两个或多个变量整数系数方程个或多个变量整数系数方程个或多个变量整数系数方程个或多个变量整数系数方程的有理数解问题。的有理数解问题。的有理数解问题。的有理数解问题。n n对于具有对于具有对于具有对于具有整数系数的不定方程整数系数的不定方程整数系数的不定方程整数系数的不定方程,如果只考虑其,如果只考虑其,如果只考虑其,如果只考虑其整数整数整数整数解解解解,这类方程就叫做丢番图方程。,这类方程就叫做丢番图方程。,这类方程就叫做丢番图方程。,这类方程就叫做丢番图方程。oo“丢番图方程可解性问题丢
4、番图方程可解性问题”的实质为:能否写的实质为:能否写出一个可以判定出一个可以判定任意丢番图方程是否可解任意丢番图方程是否可解的算的算法?法?一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解ooax=b,只只要要a能能整整除除b,就就可可判判定定其其有有整整数数解解,该整数解即该整数解即b/a。两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解的解的解的解ooax+by=c,先求出先求出a和和b的最大公因子的最大公因子d,若若d能能整除整除c,则该方程有解(整数解)
5、。则该方程有解(整数解)。oo问:方程问:方程13x+26y=52有无整数解?有无整数解?n n答:答:答:答:1313和和和和2626的最大公因子是的最大公因子是的最大公因子是的最大公因子是1313,1313又可整除又可整除又可整除又可整除5252,故,故,故,故该方程有整数解(如该方程有整数解(如该方程有整数解(如该方程有整数解(如x x=2=2,y y=1=1即方程的解)。即方程的解)。即方程的解)。即方程的解)。oo例例4.2问:方程问:方程2x+4y=15有无整数解?有无整数解?n n答:答:答:答:2 2和和和和4 4的最大公因子是的最大公因子是的最大公因子是的最大公因子是2 2,
6、2 2不能整除不能整除不能整除不能整除1515,故该方,故该方,故该方,故该方程无整数解。程无整数解。程无整数解。程无整数解。两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解:的解:的解:的解:欧几里德算法欧几里德算法欧几里德算法欧几里德算法 oo给给定定两两个个正正整整数数m和和n,求求它它们们的的最最大大公公因因子子,即能同时整除即能同时整除m和和n的最大正整数。的最大正整数。oo步骤如下:步骤如下:n n(1 1)以)以)以)以n n除除除除mm,并令所得余数为并令所得余数为并令所得余数为并令所得余数为r r(r r必小于必小
7、于必小于必小于n n););););n n(2 2)若若若若r r=0=0,算算算算法法法法结结结结束束束束,输输输输出出出出结结结结果果果果n n;否否否否则则则则,继继继继续续续续步骤(步骤(步骤(步骤(3 3););););n n(3 3)将将将将n n置置置置换换换换为为为为mm,r r置置置置换换换换为为为为n n,并并并并返返返返回回回回步步步步骤骤骤骤(1 1)继续进行。继续进行。继续进行。继续进行。例例例例4.34.3设设设设mm=56=56,n n=32=32,求求求求mm、n n的最大公因子的最大公因子的最大公因子的最大公因子算法如下算法如下:(1)32除除56余数为余数为
8、24;(2)24除除32余数为余数为8;(3)8除除24余数为余数为0,算法结束,输出结果,算法结束,输出结果8。答:答:m、n的最大公因子为的最大公因子为8。oo欧几里德算法既表述了一个数的求解过程,欧几里德算法既表述了一个数的求解过程,n n又又又又表表表表述述述述了了了了一一一一个个个个判判判判定定定定过过过过程程程程,该该该该过过过过程程程程可可可可以以以以判判判判定定定定“mm和和和和n n是是是是互互互互质质质质的的的的”(即即即即除除除除1 1以以以以外外外外,mm和和和和n n没没没没有有有有公公公公因因因因子子子子)这这这这个个个个命题的真假。命题的真假。命题的真假。命题的真
9、假。算法算法算法的定义和特征算法的定义和特征 1算法的非形式化定义算法的非形式化定义 oo一个算法,就是一个有穷规则的集合,其中之一个算法,就是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型问题的运算规则规定了一个解决某一特定类型问题的运算序列。序列。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo有穷性:一个算法在执行有穷步之后必须结束。有穷性:一个算法在执行有穷步之后必须结束。oo确确定定性性:算算法法的的每每一一个个步步骤骤必必须须要要确确切切地地定定义义。即即算算法法中中所所有有有有待待执执行行的的动动作作必必须须严严格格而而不不含含混地进行规定,不能有歧义
10、性。混地进行规定,不能有歧义性。oo输输入入:算算法法有有零零个个或或多多个个的的输输入入,即即在在算算法法开开始之前,对算法最初给出的量。始之前,对算法最初给出的量。oo输输出出:算算法法有有一一个个或或多多个个的的输输出出,即即与与输输入入有有某某个个特特定定关关系系的的量量,简简单单地地说说就就是是算算法法的的最最终终结果。结果。oo能能行行性性:算算法法中中有有待待执执行行的的运运算算和和操操作作必必须须是是相当基本的,相当基本的,3算法的形式化定义算法的形式化定义 算法是一个四元组,即(算法是一个四元组,即(Q,I,F)。)。其中:其中:(1)Q是是一一个个包包含含子子集集I和和的的
11、集集合合,它它表表示示计计算算的状态;的状态;(2)I表示计算的输入集合;表示计算的输入集合;(3)表示计算的输出集合;表示计算的输出集合;(4)F表表示示计计算算的的规规则则,它它是是一一个个由由Q到到它它自自身身的的函函数数,且且具具有有自自反反性性,即即对对于于任任何何一一个个元元素素qQ,有有F(q)=q。算法算法算法实例算法实例 例例4.4求求1+2+3+100 设设变变量量X表表示示加加数数,Y表表示示被被加加数数,用用自自然然语语言言将将算法描述如下:算法描述如下:(1)将)将1赋值给赋值给X;(2)将将2赋值给赋值给Y;(3)将将X与与Y相加,结果存放在相加,结果存放在X中;中
12、;(4)将)将Y加加1,结果存放在,结果存放在Y中;中;(5)若若Y小小于于或或等等于于100,转转到到步步骤骤(3)继继续续执执行;否则,算法结束,结果为行;否则,算法结束,结果为X。例例4.5求解调和级数求解调和级数设变量设变量X表示累加和,变量表示累加和,变量I表示循环的次数,自表示循环的次数,自然语言描述算法如下:然语言描述算法如下:(1)将)将0赋值给赋值给X;(2)将将1赋值给赋值给I;(3)将将X与与1/I相加,然后把结果存入相加,然后把结果存入X;(4)将将I加加1;(5)若)若I大于等于大于等于N,算法结束,结果为算法结束,结果为X;否否则转到步骤(则转到步骤(3)继续执行。
13、)继续执行。例例例例4.64.6求解斐波那契数求解斐波那契数求解斐波那契数求解斐波那契数 0,1,1,2,3,5,8,13,21,34,(1)oo来来 源源 于于 1202年年 意意 大大 利利 数数 学学 家家 斐斐 波波 那那 契契(L.P.Fibonacci)在在其其珠珠算算之之书书(Liber Abaci)中提出的一个中提出的一个“兔子问题兔子问题”:n n假假假假设设设设一一一一对对对对刚刚刚刚出出出出生生生生的的的的兔兔兔兔子子子子一一一一个个个个月月月月后后后后就就就就能能能能长长长长大大大大,再再再再过过过过一一一一个个个个月月月月就就就就能能能能生生生生下下下下一一一一对对对
14、对兔兔兔兔子子子子,并并并并且且且且此此此此后后后后每每每每个个个个月月月月都都都都能能能能生生生生一一一一对对对对兔兔兔兔子子子子,且且且且新新新新生生生生的的的的兔兔兔兔子子子子在在在在第第第第二二二二个个个个月月月月后后后后也也也也是是是是每每每每个个个个月月月月生生生生一对兔子。一对兔子。一对兔子。一对兔子。n n问:一对兔子一年内可繁殖成多少对兔子?问:一对兔子一年内可繁殖成多少对兔子?问:一对兔子一年内可繁殖成多少对兔子?问:一对兔子一年内可繁殖成多少对兔子?oo在在序序列列(1)中中,每每个个数数都都是是它它的的前前两两个个数数之之和和,Fn表表示示这这个个序序列列的的第第n个个
15、数数,该该序序列列可可以以形式化的定义为:形式化的定义为:n nF F0 0=0=0,F F1 1=1=1,F Fn n+2+2=F Fn n+1+1+F Fn n,n n 0 0oo斐斐波波那那契契数数列列还还是是一一个个关关于于加加法法算算法法的的典典型型实实例。例。oo设变量设变量X表示前一个数的值,即定义中的表示前一个数的值,即定义中的Fn,变量变量Y表示当前数的值,即定义中的表示当前数的值,即定义中的Fn+1,变量变量Z表示后一个数的值,即定义中的表示后一个数的值,即定义中的Fn+2。那么求那么求解问题的自然语言描述如下:解问题的自然语言描述如下:(1 1)如如如如果果果果=0=0,
16、那那那那么么么么将将将将0 0赋赋赋赋值值值值给给给给Y Y,并并并并输输输输出出出出Y Y,转转转转步步步步骤骤骤骤(1111)继续执行;)继续执行;)继续执行;)继续执行;(2 2)将)将)将)将0 0赋给赋给赋给赋给X X,将将将将1 1赋值给赋值给赋值给赋值给Y Y;(3 3)输出输出输出输出X X、Y Y;(4 4)将将将将1 1赋值给赋值给赋值给赋值给I I;(5 5)如果如果如果如果I I大于大于大于大于-1-1,则转到步骤(,则转到步骤(,则转到步骤(,则转到步骤(1111),否则继续执行;),否则继续执行;),否则继续执行;),否则继续执行;(6 6)将)将)将)将X X和和
17、和和Y Y的和赋值给的和赋值给的和赋值给的和赋值给Z Z;(7 7)将将将将Y Y赋值给赋值给赋值给赋值给X X;(8 8)将将将将Z Z赋值给赋值给赋值给赋值给Y Y;(9 9)将将将将Y Y输出;输出;输出;输出;(1010)将)将)将)将I I加加加加1 1,转步骤(,转步骤(,转步骤(,转步骤(5 5)继续执行;)继续执行;)继续执行;)继续执行;(1111)算法结束。)算法结束。)算法结束。)算法结束。算法算法算法的表示方法算法的表示方法原语原语原语原语oo一个算法的表达需要使用一些语言形式一个算法的表达需要使用一些语言形式n n自然语言自然语言自然语言自然语言“Visiting g
18、randchildren can be Visiting grandchildren can be nerve-racking”,nerve-racking”,可能即意味着孙子孙女导致了可能即意味着孙子孙女导致了可能即意味着孙子孙女导致了可能即意味着孙子孙女导致了很多问题,也表示去看他们可能会有问题很多问题,也表示去看他们可能会有问题很多问题,也表示去看他们可能会有问题很多问题,也表示去看他们可能会有问题n n图形语言:很少人能够根据折纸图给出的步骤成功图形语言:很少人能够根据折纸图给出的步骤成功图形语言:很少人能够根据折纸图给出的步骤成功图形语言:很少人能够根据折纸图给出的步骤成功地叠出一只
19、鸟来,但一个专门学习过折纸的学生可地叠出一只鸟来,但一个专门学习过折纸的学生可地叠出一只鸟来,但一个专门学习过折纸的学生可地叠出一只鸟来,但一个专门学习过折纸的学生可以轻松完成以轻松完成以轻松完成以轻松完成oo当用来描述算法的语言并没有被准确定义或者当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候,交流就会产生问题没有给予足够信息的时候,交流就会产生问题原语原语原语原语oo通过建立一个可以描述算法的意义明确的基本通过建立一个可以描述算法的意义明确的基本块(块(原语原语)集合,计算机科学即就可以解决上)集合,计算机科学即就可以解决上述的勾通问题述的勾通问题oo原语描述算法需要建立一
20、个统一的细节描述级原语描述算法需要建立一个统一的细节描述级别,原语连同一组表达了原语如何表达复杂的别,原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言想法的规定组成了一种程序设计语言oo组成组成n n语法:原语的符号表示语法:原语的符号表示语法:原语的符号表示语法:原语的符号表示n n语义:表达了原语的意义语义:表达了原语的意义语义:表达了原语的意义语义:表达了原语的意义1 1自然语言自然语言自然语言自然语言oo缺点缺点n n由由由由于于于于自自自自然然然然语语语语言言言言的的的的歧歧歧歧义义义义性性性性,容容容容易易易易导导导导致致致致算算算算法法法法执执执执行行行行的的
21、的的不不不不确确确确定性;定性;定性;定性;n n自自自自然然然然语语语语言言言言的的的的语语语语句句句句一一一一般般般般太太太太长长长长,从从从从而而而而导导导导致致致致了了了了用用用用自自自自然然然然语语语语言言言言描述的算法太长;描述的算法太长;描述的算法太长;描述的算法太长;n n由由由由于于于于自自自自然然然然语语语语言言言言表表表表示示示示的的的的串串串串行行行行性性性性,因因因因此此此此,当当当当一一一一个个个个算算算算法法法法中中中中循环和分支较多时就很难清晰地表示出来;循环和分支较多时就很难清晰地表示出来;循环和分支较多时就很难清晰地表示出来;循环和分支较多时就很难清晰地表示
22、出来;n n自自自自然然然然语语语语言言言言表表表表示示示示的的的的算算算算法法法法不不不不便便便便翻翻翻翻译译译译成成成成计计计计算算算算机机机机程程程程序序序序设设设设计计计计语语语语言理解的语言。言理解的语言。言理解的语言。言理解的语言。2 2流程图流程图流程图流程图 oo它它采采用用美美国国国国家家标标准准化化协协会会ANSI(AmericanNationalStandardInstitute)规规定定的的一一组组图图形形符号来表示算法。符号来表示算法。n n流流流流程程程程图图图图可可可可以以以以很很很很方方方方便便便便地地地地表表表表示示示示顺顺顺顺序序序序、选选选选择择择择和和和
23、和循循循循环环环环结结结结构构构构,而而而而任任任任何何何何程程程程序序序序的的的的逻逻逻逻辑辑辑辑结结结结构构构构都都都都可可可可以以以以用用用用顺顺顺顺序序序序、选选选选择择择择和和和和循循循循环环环环结构来表示,结构来表示,结构来表示,结构来表示,n n流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。n n用用用用流流流流程程程程图图图图表表表表示示示示的的的的算算算算法法法法不不不不依依依依赖赖赖赖于于于于任任任任何何何何具具具具体体体体的的的的计计计计算算算算机机机机和和和和计算机程序设计语言,计
24、算机程序设计语言,计算机程序设计语言,计算机程序设计语言,(1 1)求解例)求解例)求解例)求解例4.44.4的算法流程图的算法流程图的算法流程图的算法流程图(2 2)求解例)求解例)求解例)求解例4.54.5的算法流程图的算法流程图的算法流程图的算法流程图(3 3)求解例)求解例)求解例)求解例4.64.6的算法流程图的算法流程图的算法流程图的算法流程图 3 3伪代码伪代码伪代码伪代码(1 1)求解例)求解例)求解例)求解例4.44.4的伪代码算法描述:的伪代码算法描述:的伪代码算法描述:的伪代码算法描述:BEGIN(BEGIN(算法开始算法开始算法开始算法开始)1 1 X X 2 2YYw
25、hilewhile(Y=100Y=n)while(I=n)ENDEND(算法结束)算法结束)算法结束)算法结束)(3 3)例)例)例)例4.64.6的伪代码算法描述:的伪代码算法描述:的伪代码算法描述:的伪代码算法描述:BEGINBEGINifn=0ifn=0 0 0YYPrintYPrintY else0X1YPrintX,Yfor(i=1;i=n-1;i+)X+YZYXZYPrintYEND4 4计算机程序设计语言计算机程序设计语言计算机程序设计语言计算机程序设计语言 oo计计算算机机程程序序设设计计语语言言描描述述的的算算法法(程程序序)是是清清晰的、简明的,最终也能由计算机处理的。晰的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 部分 计算 学科 中的 核心 概念 教案
限制150内