如果只考虑其整数解课件

第4章

计算学科中的核心概念4.1算法

第4章

计算学科中的核心概念4.1算法1算法的历史简介

公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的《波斯教科书》（PersianTextbook），书中概括了进行四则算术运算的法则。“算法”（Algorithm）一词就来源于这位数学家的名字。后来，《韦氏新世界词典》将其定义为“解某种问题的任何专门的方法”。而据考古学家发现，古巴比伦人在求解代数方程时，就已经采用了“算法”的思想。

算法的历史简介公元825年，阿拉伯数学家阿科瓦里茨米（Al丢番图方程的可解性问题

古希腊数学家丢番图（Diophantus）：代数学之父在《算术》（Arithmetica）一书中提出了有关两个或多个变量整数系数方程的有理数解问题。对于具有整数系数的不定方程，如果只考虑其整数解，这类方程就叫做丢番图方程。“丢番图方程可解性问题”的实质为：能否写出一个可以判定任意丢番图方程是否可解的算法？

丢番图方程的可解性问题古希腊数学家丢番图（Diophant一个未知数的线性丢番图方程的解ax=b，只要a能整除b，就可判定其有整数解，该整数解即b/a。一个未知数的线性丢番图方程的解ax=b，只要a能整除b，就可两个未知数的线性丢番图方程的解ax+by=c，先求出a和b的最大公因子d，若d能整除c，则该方程有解（整数解）。

问：方程13x+26y=52有无整数解？答：13和26的最大公因子是13，13又可整除52，故该方程有整数解（如x=2，y=1即方程的解）。例4.2问：方程2x+4y=15有无整数解？答：2和4的最大公因子是2，2不能整除15，故该方程无整数解。

两个未知数的线性丢番图方程的解ax+by=c，先求出a和b两个未知数的线性丢番图方程的解：欧几里德算法

给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。步骤如下：（1）以n除m，并令所得余数为r（r必小于n）；（2）若r=0，算法结束，输出结果n；否则，继续步骤（3）；（3）将n置换为m，r置换为n，并返回步骤（1）继续进行。两个未知数的线性丢番图方程的解：欧几里德算法给定两个正整例4.3设m=56，n=32，求m、n的最大公因子算法如下:（1）32除56余数为24；（2）24除32余数为8；（3）8除24余数为0，算法结束，输出结果8。答：m、n的最大公因子为8。欧几里德算法既表述了一个数的求解过程，又表述了一个判定过程，该过程可以判定“m和n是互质的”（即除1以外，m和n没有公因子）这个命题的真假。例4.3设m=56，n=32，求m、n的最大公因子算法如

算法算法的定义和特征

算法算法的定义和特征81．算法的非形式化定义

一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列。

1．算法的非形式化定义一个算法，就是一个有穷规则的集合，其2．算法的重要特性有穷性：一个算法在执行有穷步之后必须结束。确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。输入：算法有零个或多个的输入，即在算法开始之前，对算法最初给出的量。输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。能行性：算法中有待执行的运算和操作必须是相当基本的，2．算法的重要特性有穷性：一个算法在执行有穷步之后必须结束。3．算法的形式化定义

算法是一个四元组，即（Q，I，Ω，F）。其中：（1）Q是一个包含子集I和Ω的集合，它表示计算的状态；（2）I表示计算的输入集合；（3）Ω表示计算的输出集合；（4）F表示计算的规则，它是一个由Q到它自身的函数，且具有自反性，即对于任何一个元素q∈Q，有F(q)=q。3．算法的形式化定义算法是一个四元组，即（Q，I，Ω，F）如果只考虑其整数解课件

算法算法实例

算法算法实例13例4.4求1+2+3+……+100

设变量X表示加数，Y表示被加数，用自然语言将算法描述如下：（1）将1赋值给X；（2）将2赋值给Y；（3）将X与Y相加，结果存放在X中；（4）将Y加1，结果存放在Y中；（5）若Y小于或等于100，转到步骤（3）继续执行；否则，算法结束，结果为X。例4.4求1+2+3+……+100设变量X表示加数，Y例4.5

求解调和级数设变量X表示累加和，变量I表示循环的次数，自然语言描述算法如下：（1）将0赋值给X；（2）将1赋值给I；（3）将X与1/I相加，然后把结果存入X；（4）将I加1；（5）若I大于等于N，算法结束，结果为X；否则转到步骤（3）继续执行。

例4.5求解调和级数设变量X表示累加和，变量I表示循环的例4.6求解斐波那契数

0，1，1，2，3，5，8，13，21，34，…

（1）来源于1202年意大利数学家斐波那契（L.P.Fibonacci）在其《珠算之书》（LiberAbaci）中提出的一个“兔子问题”：假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。问：一对兔子一年内可繁殖成多少对兔子？例4.6求解斐波那契数0，1，1，2，3，5，8，13在序列（1）中，每个数都是它的前两个数之和，Fn表示这个序列的第n个数，该序列可以形式化的定义为：

F0=0，F1=1，Fn+2=Fn+1+Fn，n≥0斐波那契数列还是一个关于加法算法的典型实例。在序列（1）中，每个数都是它的前两个数之和，Fn表示这个序列设变量X表示前一个数的值，即定义中的Fn，变量Y表示当前数的值，即定义中的Fn+1，变量Z表示后一个数的值，即定义中的Fn+2。那么求解问题的自然语言描述如下：

设变量X表示前一个数的值，即定义中的Fn，变量Y表示当前数的（1）如果=0，那么将0赋值给Y，并输出Y，转步骤（11）继续执行；（2）将0赋给X，将1赋值给Y；（3）输出X、Y；（4）将1赋值给I；（5）如果I大于-1，则转到步骤（11），否则继续执行；（6）将X和Y的和赋值给Z；（7）将Y赋值给X；（8）将Z赋值给Y；（9）将Y输出；（10）将I加1，转步骤（5）继续执行；（11）算法结束。（1）如果=0，那么将0赋值给Y，并输出Y，转步骤（11）继

算法算法的表示方法

算法算法的表示方法20原语一个算法的表达需要使用一些语言形式自然语言“Visitinggrandchildrencanbenerve-racking”,可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过折纸的学生可以轻松完成当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候，交流就会产生问题原语一个算法的表达需要使用一些语言形式原语通过建立一个可以描述算法的意义明确的基本块（原语）集合，计算机科学即就可以解决上述的勾通问题原语描述算法需要建立一个统一的细节描述级别，原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言组成语法：原语的符号表示语义：表达了原语的意义原语通过建立一个可以描述算法的意义明确的基本块（原语）集合，1．自然语言缺点由于自然语言的歧义性，容易导致算法执行的不确定性；自然语言的语句一般太长，从而导致了用自然语言描述的算法太长；由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来；自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。

1．自然语言缺点2．流程图

它采用美国国家标准化协会ANSI（AmericanNationalStandardInstitute）规定的一组图形符号来表示算法。流程图可以很方便地表示顺序、选择和循环结构，而任何程序的逻辑结构都可以用顺序、选择和循环结构来表示，流程图可以表示任何程序的逻辑结构。用流程图表示的算法不依赖于任何具体的计算机和计算机程序设计语言，2．流程图它采用美国国家标准化协会ANSI（America（1）求解例4.4的算法流程图（1）求解例4.4的算法流程图（2）求解例4.5的算法流程图

（2）求解例4.5的算法流程图（3）求解例4.6的算法流程图

（3）求解例4.6的算法流程图3．伪代码——（1）求解例4.4的伪代码算法描述：BEGIN(算法开始)

1

X 2

Y while（Y<=100） { X+Y

X Y+1

Y } PrintXEND（算法结束）3．伪代码——（1）求解例4.4的伪代码算法描述：BEGIN（2）求解例4.5的伪代码算法描述：BEGIN（算法开始） 0

X 1

I do { X+1/I

X I+1

I }while(I>=n)END（算法结束）（2）求解例4.5的伪代码算法描述：BEGIN（算法开始）（3）例4.6的伪代码算法描述：

BEGIN ifn==0 { 0

Y PrintY }else {

0

X 1

Y PrintX，Y for(i=1;i<=n-1;i++) { X+YZ YX ZY PrintY } }END（3）例4.6的伪代码算法描述：BEGIN 0X4．计算机程序设计语言

计算机程序设计语言描述的算法（程序）是清晰的、简明的，最终也能由计算机处理的。缺点：算法的基本逻辑流程难于遵循。与自然语言一样，程序设计语言也是基于串行的用特定程序设计语言编写的算法限制了与他人的交流，不利于问题的解决；要花费大量的时间去熟悉和掌握某种特定的程序设计语言；要求描述计算步骤的细节，而忽视算法的本质。4．计算机程序设计语言计算机程序设计语言描述的算法（程序）例4.4的计算机程序设计语言（C语言）的算法描述：

main(){intX,Y;X=1;Y=2;while(Y<=100){X=X+Y;Y=Y+1;};printf("%d",X);}例4.4的计算机程序设计语言（C语言）的算法描述：main例4.5的计算机程序设计语言（C语言）的算法描述

main(){intn;floatX,I;printf("Pleaseinputn:");scanf("%d",&n);X=0;I=1;

do{X=X+1/I;I=I+1;}while(I<=n);printf("\n%f",X);}例4.5的计算机程序设计语言（C语言）的算法描述main(如果只考虑其整数解课件如果只考虑其整数解课件

算法算法分析

算法算法分析36（1）算法的时间复杂度；

用T(n)表示，n表示问题规模的大小。使用一个记号

Order（数量级）的第一个字母，允许使用“=”代替“≈”。如n2+n+1=

(n2)设f(n)是一个关于正整数n的函数，若存在一个正整数n0和一个常数C，当n≥n0时，∣T(n)∣≤∣Cf(n)∣均成立，则称f(n)为T(n)的同数量级的函数。算法时间复杂度T(n)可表示为：

T(n)=

(f(n))（1）算法的时间复杂度；用T(n)表示，n表示问题规模的大常见的大

表示形式有：

(1)称为常数级；

(logn)称为对数级；

(n)称为线性级；

(nc)称为多项式级；

(cn)称为指数级；

(n!)称为阶乘级。常见的大表示形式有：算法的空间复杂度指算法在执行过程中所占存储空间的大小，用S(n)表示，S为英文单词Space的第一个字母。与算法的时间复杂度相同算法的空间复杂度S(n)也可表示为：S(n)=

(g(n))。

算法的空间复杂度指算法在执行过程中所占存储空间的大小，如果只考虑其整数解课件

算法算法的研究

算法算法的研究41算法算法：定义一向工作如何完成的步骤的集合在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描述一个与机器兼容的算法的描述——程序算法的研究开始是作为数学的一个学科目标：找到描述特定类型问题是如何被解决的指令的集合，如Euclidean算法一旦一个完成任务的算法被找到，任务的实现就不再需要对算法原理的理解，任务的实现仅仅是遵循算法的只是过程现有的解决问题需要的智慧被编码进了算法算法算法：定义一向工作如何完成的步骤的集合算法转化为智慧通过使用算法来得到并转化智慧，我们才可以构建起可以表现智慧行为的机器。机器表现的智能等级受到通过算法转化的智慧所限制如果没有解决问题的算法，意味着问题的解决方案超出了机器的能力范围算法的开发就成了计算机领域的一个主要目标如何找到算法——一个十分接近于寻找通用问题解决方案描述这个算法——转变为一个清晰的指令的集合（程序设计语言描述）算法转化为智慧通过使用算法来得到并转化智慧，我们才可以构建起计算机技术别用于复杂问题（大型软件系统）不仅仅包括实现任务的单个算法的开发还要求对组件之间的交互进行设计软件工程：借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域的经验计算机技术别用于复杂问题（大型软件系统）不仅仅包括实现任务的执行算法的机器的设计和实现数据的存储数据的操作体系结构中涵盖了对现今技术的讨论我们的目标不是去熟知类似当今体系结构是如何用电路来实现这样的细节问题，那将会导致过分陷入电子工程学科正如昨天的齿轮驱动的计算机让位于电子设备一样，今天的电子技术也许很快也被其它的技术所取代执行算法的机器的设计和实现数据的存储理想情况下希望计算机的体系结构是我们的有关算法过程知识的延续，并且不应该被技术能力酸限制使我们的算法知识在当代机器体系结构的发展背后起推动作用，而不仅仅是从技术的要求触发来解顶机器的设计构建允许使用多个指令序列来代替算法的机器是可能的这些指令被同时执行或者作为理想情况下希望计算机的体系结构是我们的有关算法过程知识的延续机器于外部世界的接口的设计于计算机的设计紧密相连算法是如何机器中的？机器是如何被告知执行的是哪一个算法？机器于外部世界的接口的设计于计算机的设计紧密相连算法是如何机计算理论对解决越来越复杂问题的算法的研究导致了算法过程的最终限制问题如果没有算法可以解决这个问题，那么算法是不能被机器所解决的，机器仅仅可以解决在算法上可解的问题Godel的不完全定理阐述了在任何传统算术领域的数学理论中，有些是既不能证明有不能被推翻的任何对算术系统的彻底研究都超出了算法的能力对算法的限制的研究欲望似的数学家们设计抽象的机器来执行算法，并在理论上研究这些假想机器的能力。计算理论对解决越来越复杂问题的算法的研究

数据结构：一类定性数学模型

数据结构的基本概念

数据结构：一类定性数学模型数据结构的基本概念49数据结构的基本概念

组成：数据结构是一类定性的数学模型，它由以下3部分组成逻辑结构存储结构（或称物理结构）运算数据逻辑结构的形式化定义

DS=<D，R>其中：D表示数据的集合；R表示数据D上关系的集合。

数据结构的基本概念组成：数据结构是一类定性的数学模型，它由数据的存储结构

数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式。顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系。

链式存储结构：借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。

数据的存储结构数据的存储结构是指在反映数据逻辑关系的原则下数据结构的基本运算内容

建立数据结构；清除数据结构；插入数据元素；删除数据元素；更新数据元素；查找数据元素；按序重新排列；判定某个数据结构是否为空，或是否已达到最大允许的容量；统计数据元素的个数。数据结构的基本运算内容建立数据结构；如果只考虑其整数解课件

数据结构：一类定性数学模型

常用的几种数据结构

数据结构：一类定性数学模型

常用的几种数据结构54线性表线性表是n个数据元素的有限序列，即（X[1]，X[2]，X[3]，…，X[i]，…，X[n]）基本操作——插入、删除和存取数据元素几种特殊的线性表后进先出（LastInFirstOut，简称LIFO）的线性表。先进先出（FirstInFirstOut，简称FIFO）的线性表。

限定所有插入、删除和存取都在表的两端进行的线性表。

线性表线性表是n个数据元素的有限序列，即（X[1]，X[2]数组线性表的推广形式之一。如在一个m

n的二维数组中，每个元素A[i,j]都分别属于两个线性表，即（A[i,1]，A[i,2]，…，A[i,n]）和（A[1,j]，A[2,j]，…，A[m,j]）。

数组线性表的推广形式之一。树（Tree）由n（n≥0）个结点组成的有限集合。若n=0，则称为空树，任何一个非空树均满足以下两个条件：

仅有一个称为根的结点；

当n>0时，其余结点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。

树（Tree）由n（n≥0）个结点组成的有限集合。若n=0，下图的树有12个结点，A是根结点，该树又可再分为若干不相交的子树，如T1={B，E，F，K}，T2={C，G}，T3={D，H，I，J，L}等。图4.4所示的树中有12个结点，A是根结点，该树又可再分为若干不相交的子树，如T1={B，E，F，K}，T2={C，G}，T3={D，H，I，J，L}等。下图的树有12个结点，A是根结点，该树又可再分为若干不相交的二叉树n（n≥0）个结点组成的有限集合，它或者是空集（n

0），或者由一个结点及两棵互不相交的子树组成，且这两个子树有左、右之分，其次序不能任意颠倒。二叉树n（n≥0）个结点组成的有限集合，它或者是空集（n0图由结点和连接这些结点的边所组成的集合。图的形式化定义为：

G=<V，E>

其中：V是一个非空结点的集合；E是连结结点的边的集合。图由结点和连接这些结点的边所组成的集合。例G=<V，E>其中V={A，B，C，D}，E={(A，B)，(A，C)，(B，D)，(B，C)，(D，C)，(A，D)}例G=<V，E>其中V={A，B，C，D}，

4.3程序

算法+数据结构=程序

4.3程序

算法+数据结构=程序62概念从广义上讲可以认为是一种行动方案或工作步骤。某个会议的日程安排一条旅游路线的设计手工小制作的说明书等计算机程序：一种处理事务的时间顺序和处理步骤。组成计算机程序的基本单位是指令计算机程序就是按照工作步骤事先编排好的、具有特殊功能的指令序列。

概念从广义上讲可以认为是一种行动方案或工作步骤。软件在计算机发展的初期，硬件设计和生产是主要问题，那时的软件就是程序。现在计算机软件一般指计算机系统中的程序及其文档，也可以指在研究、开发、维护，以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。软件一般分为3类系统软件支撑软件应用软件软件在计算机发展的初期，硬件设计和生产是主要问题，那时的软件硬件计算机硬件是构成计算机系统的所有物理器件、部件、设备，以及相应的工作原理与设计、制造、检测等技术的总称。计算机系统的物理元器件包括：集成电路、印制电路板，以及其他磁性元件、电子元件等。计算机系统的部件和设备包括：控制器、运算器、存储器、输入输出设备、电源等。硬件工程技术包括：印制电路板制造、高密度组装、抗环境干扰、抗恶劣环境破坏等技术，以及在设计和制造过程中为提高计算机性能所采取的措施等。硬件计算机硬件是构成计算机系统的所有物理器件、部件、设备，以

4.6CC1991报告提取的核心概念

4.6CC1991报告提取的核心概念66核心概念是CC1991报告首次提出的，是具有普遍性、持久性的重要思想、原则和方法。它的基本特征有：

在学科中多处出现；在各分支领域及抽象、理论和设计的各个层面上都有很多示例；在技术上有高度的独立性；一般都在数学、科学和工程中出现。核心概念是CC1991报告首次提出的，是具有普遍性、持久性的1.绑定2.大问题的复杂性绑定指的是通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程。例如：将一个进程与一个处理机，一个变量与其类型或值分别联系起来。这种联系的建立，实际上就是建立了某种约束。大问题的复杂性是指随着问题规模的增长而使问题的复杂性呈非线性增加的效应。这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素。

1.绑定2.大问题的3.概念和形式模型概念和形式模型概念和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法。抽象数据类型、语义数据类型以及指定系统的图形语言，如数据流图和E-R图等都属于概念模型。而逻辑、开关理论和计算理论中的模型大都属于形式模型。概念模型和形式模型以及形式证明是将计算学科各分支统一起来的重要的核心概念。3.概念和形式模型概念和形式模型4.一致性和完备性一致性包括用于形式说明的一组公理的一致性、事实和理论的一致性，以及一种语言或接口设计的内部一致性。完备性包括给出的一组公理，使其能获得预期行为的充分性、软件和硬件系统功能的充分性，以及系统处于出错和非预期情况下保持正常行为的能力等。在计算机系统设计中，正确性、健