第1章算法概述1

计算机算法设计与分析

DesignandAnalysisofComputerAlgorithms

第一章算法概述王红霞理学院2/4/20231理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法学习要点:2提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法3提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法4

在中央电视台幸运52节目中,有一个猜商品价格的环节,竟猜者如在规定的时间内大体猜出某种商品的价格,就可获得该件商品.现有一商品,价格在0-8000元之间,采取怎样的策略才能在短的时间内说出正确(大体上)的答案呢?第一步:报“4000”；第二步:若主持人说高了(说明答案在0~4000之间),就报“2000”,否则(答数在4000~8000之间)报“6000”；第三步:重复第二步的报数方法取中间数,直至得到正确结果.5两个大人和两名儿童一起渡河，渡口只有一条小船，一次只能渡过一个大人或两名儿童，他们四人都会划船，但都不会游泳。请你帮他们设计一个渡河方案。什么是算法呢？第一步：两个小孩同船渡过河去；第二步：一个小孩划船回来；第三步：一个大人独自划船渡过河去；第四步：对岸的小孩划船回来；第五步：两个小孩再同船渡过河去；第六步：一个小孩划船回来；第七步：余下的一个大人独自划船渡过河去；第八步：对岸的小孩划船回来；第九步：两个小孩再同船渡过河去。6什么是算法呢？简单地说，算法就是解决问题的方法或步骤。7你对以下的“算法”如何理解？要把大象装冰箱，分几步？答：分三步：第一步：打开冰箱门第二步：把大象装冰箱第三步：关上冰箱门问：问题38一位商人有9枚金币，其中有一枚略轻的假币，你能用天平（无砝码）将假币找出来吗？写出解决这一问题的算法。第一步：把9枚金币平均分成三组，每组三枚。先将其中的两组放在天平的两边，如果天平不平衡，那么假金币就在轻的那一组；如果天平左右平衡，则假金币就在未称量的那一组里。取出含假币的那一组，从中任取两枚金币放在天平两边进行称量，如果天平不平衡，则假金币在轻的那一边；若平衡，则未称的那一枚就是假币。第二步：第三步：问题491.1算法的概念算法是指解决问题的方法和过程。算法是对特定问题求解步骤的一种描述，包含操作的有限规则和操作的有限序列。通俗一点讲，算法就是一个解决问题的公式（数学手册上的公式都是经典算法）、规则、思路、方法和步骤。算法可以用自然语言描述，也可以用流程图描述，但最终要用计算机语言编程，上机实现。

10从更广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有.如乐谱是乐队演奏的算法,菜谱是做菜肴的算法,珠算口诀是使用算盘的算法.

人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。

11算法的特性算法是若干指令的有穷序列，满足性质：输入：有1个或多个满足给定约束条件的量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令是清晰，无歧义的。有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。算法要求其执行时间是有限的(终止性)。程序的执行时间可能是无限的。(例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。)12以累加10个1的算法为例不正确的算法(无结束)第一步开始第二步N=0第三步N=N+1第四步转第三步第五步结束不正确的算法(指令不清晰

)第一步开始第二步N=0第三步N=N+1第四步根据N值转第三步或第五步第五步结束正确的算法第一步开始第二步N=0第三步N=N+1第四步N>9转第五步否则转第三步第五步结束13程序程序是某个算法或过程的在计算机上的一个具体的实现。程序是依赖于程序设计语言的，甚至依赖于计算机结构的。算法是脱离具体的计算机结构和程序设计语言的。14算法与程序的区别与联系(1).一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。(2).程序中的指令必须是机器可执行的，而算法中的指令则无此限制。(3).算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序.15算法≠程序算法描述：自然语言，流程图，程序设计语言，伪代码用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。本书中采用类C++伪代码语言描述算法16算法的表示自然语言流程图伪代码计算机语言17用自然语言表示算法自然语言就是人们日常使用的语言，可以是英语、汉语或其它语言。用自然语言表示算法通俗易懂，但文字冗长，含义不太严格，容易出现“歧义性”。此外，用自然语言表示包含分支和循环的算法也不方便。18用流程图表示算法流程图是用一些事先规定了具有某种含义的图框和流程线来表示算法中的步骤和各种操作。用流程图表示算法直观形象，逻辑清晰，但是占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便，而且当算法不断改动时，流程图的修改也非常麻烦，因此流程图宜用于表示一个完成的最终算法。流程图有很多种类型：传统流程图，N－S流程图19传统流程图起止框处理框输入输出框判断框连接点流程线NoYesn≤5开始结束p=1n=1p=p*nn=n+1传统流程图中由于对流程线的使用没有严格限制，所有很容易造成流程图的混乱和无规律。这是用传统流程图表示的求1×2×3×4×5的算法：20三种基本程序结构为了提高算法的质量，使算法设计和阅读方便，必须限制流程线的滥用，即不允许无规律的使流程转向，只能顺序的进行下去。但是。算法中难免会包含一些分支和循环而不可能全部由一个一个框顺序组成。为了解决这个问题，人们规定出几种基本结构，然后由这些基本结构按一定规律顺序排列,组成一个算法结构，整个算法的描述是由上而下的将各个基本结构顺序排列起来。A?YesNoabABabAB?YesNoab顺序结构选择结构循环结构21N－S流程图既然用基本结构的顺序组合就可以表示任何复杂的算法结构，那么，基本结构之间的流程线就是多余的了。在Ｎ－Ｓ流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其它从属于它的框，或者说，由一些基本的框组成一个大的框。AB顺序结构选择结构循环结构Ｎ－Ｓ流程图中使用以下的流程图符号：条件?AB成立不成立当条件成立做A做到条件不成立A当条件成立做while,做到条件成立until(条件不成立做,做到条件成立停)

在C语言为了简练,没有until,只有while,条件成立做,条件不成立不做,

所以改”到”型循环为做到条件不成立,与”当”型循环的条件一样22用N-S流程图表示的求1×2×3×4×5的算法：N<=5P=P*NN=N+1N=1P=1输出P

N<=5P=P*NN=N+1N=1P=1输出P条件成立做做到条件不成立23用伪代码表示算法为了设计算法时的方便，常用一种称为“伪代码”的方法。“伪代码”是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章。自上而下地写下来。每一行（或几行）表示一个基本操作。它不用图形符号。因此书写方便。格式紧凑，也比较好懂，便于向计算机语言算法（即程序）过渡。24用计算机语言表示算法在用“流程图”或“伪代码”描述出一个算法后，还要将它转换成计算机语言程序，这样才能执行程序并得到结果。从而最终解决实际问题。用计算机语言表示算法必须严格遵守所用语言的语法规则。下面是用Ｃ语言编写的求1×2×3×4×5的程序：#include<stdio.h>intmain(){intn=1,prod=1;while(n<=5){prod=prod*n;n++;}printf(“prod=%d\n”,prod);return(0);}do{prod=prod*n;n++;}while(n<=5);25对算法的学习包括五个方面的内容：①设计算法。②表示算法。③确认算法。④分析算法。⑤验证算法。26①设计算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明是有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹学等领域；②表示算法。描述算法的方法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点；27③确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机上运行，得到算法运算的结果；④分析算法。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较；⑤验证算法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作由调试和作时空分布图组成。

281.2问题表示设Input和Output是两个集合。一个问题是一个关系RInputOutput，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。一个算法面向一类问题，而不是仅求解问题的一个或几个实例。291.2问题表示例如，排序（SORT）问题定义如下：－Input=<a1,....,an>ai是实数－output=<b1,....,bn>bi是实数,且b1...bn－R=(<a1,...,an>,<b1,...,bn>)<a1,...,an>Input，<b1,...,bn>output,a1,...,an=b1,...,bn}30a0,...,n-1=5,2,4,6,1,3a0,...,n-1=5,2,4,6,1,3a0,...,n-1=2,5,4,6,1,3a0,...,n-1=2,4,5,6,1,3a0,...,n-1=2,4,5,6,1,3a0,...,n-1=1,2,4,5,6,3a0,...,n-1=1,2,3,4,5,6算法的思想：扑克牌游戏1.3算法示例—插入排序算法31算法描述1.从第一个元素开始，该元素可以认为已经被排序2.取出下一个元素，在已经排序的元素序列中从后向前扫描3.如果该元素（已排序）大于新元素，将该元素移到下一位置4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置5.将新元素插入到该位置中6.重复步骤2321.3算法示例插入排序算法

template<classType>voidInsertionSort(Type*a,intn)//数组a中包含了n个待排序的数.{Typekey;for(inti=1;i<n;i++){key=a[i];//Inserta[i]intothesortedsequencea[0..i-1].intj=i-1;while(j>=0&&a[j]>key){ a[j+1]=a[j]; j--; }a[j+1]=key;}}331.4算法的正确性分析正确的算法：对于每一个输入都最终停止,而且产生正确的输出。不正确算法：①不停止(在某个输入上)②对所有输入都停止，但对某输入产生不正确结果近似算法①对所有输入都停止②产生近似正确的解或产生不多的不正确解算法正确性证明证明算法对所有输入都停止证明对每个输入都产生正确结果调试程序程序正确性证明！程序调试只能证明程序有错，不能证明程序无错误!341.4算法的正确性分析算法正确性证明的步骤：初始化算法在循环的第一步迭代开始之前，应该是正确的。保持如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。终止当循环结束时，算法也应该是正确的。分析前面插入排序算法的正确性35如果根据应用领域进行分类的话，算法的种类就更多了。每种应用领域都会有大量的算法。一些典型的算法包括排序算法、搜索算法、图论算法、机器学习、加密算法、数据压缩算法、语法分析算法、数论与代数算法等。36算法设计与分析的基本方法1.递推法

递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。

372.递归

递归指的是一个过程：函数不断引用自身，直到引用的对象已知

3.穷举搜索法

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。

384.贪婪法

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

395.分治法

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

406.动态规划法

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

417.迭代法

迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。42提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法43

算法复杂性分析对于给定的问题，起初只是考虑只要找到一个算法解决该问题就行，而不管该算法花多长时间或者占用多大的存储空间。随着计算机技术的发展，人们发现，求解同一个问题的不同的算法，所需要的运行时间是不同的。例如对排序问题，除了插入排序算法，还有选择排序、合并排序以及快速排序算法。我们自然会问，哪个排序算法好呢？怎么样评价一个算法的好坏呢？这就涉及到算法的时间和空间资源的分析，即算法效率(Efficiency)的分析。44算法复杂性分析算法效率的分析，指的是算法求解一个问题所需要的时间和空间。分析一个算法，意味着预测该算法解一个问题时，需要花费多少时间和空间资源。空间资源一般指解决一个问题，需要多大的内存、硬盘空间等来存储输入输出数据等。时间资源一般指的是解决一个问题需要多长的时间。一般地，对一个问题，存在不同的求解算法，我们可以根据算法所需要的时空资源来确定出其中有效的算法。随着计算机硬件技术的发展，现在计算机的内存和硬盘空间基本上能满足问题的需要，即空间资源已经不是问题，因此，我们分析一个算法，主要考虑算法的计算时间，今后，我们也主要从时间资源方面对算法进行分析，即分析算法有多快。45同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。46二、算法复杂性分析算法复杂性=算法所需要的计算机资源所需资源量越多则复杂性越高，反之所需资源量越少则复杂性越低。其中最为重要的是：时间复杂性T(n)；空间复杂性S(n)。其中n是问题的规模（输入大小）。示例：一维数组问题的输入大小＝数组的长度矩阵问题的输入大小=矩阵的维数图论问题的输入大小=图的边数/结点数47决定算法复杂性的因素算法的复杂性取决于(1)求解问题的规模；(2)具体的输入数据；(3)算法本身的设计。若令N、I、和A分别表示问题的规模、具体的输入和算法本身，则C=F(N,I,A)或C=FA(N,I)=F(N,I)48时间复杂性的计算时间复杂性T(N,I)的计算为：

其中：ti为执行抽象计算机的第i种指令一次所需要的时间，这里假定抽象计算机共有k种指令。ei(N,I)为经过统计后得到的执行抽象计算机的第i种指令的次数。kT(N,I)=tiei(N,I)

i=149二、算法复杂性分析算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者502.1算法时间复杂性最坏情况下的时间复杂性Tmax(n)=max{T(I)|size(I)=n}最好情况下的时间复杂性Tmin(n)=min{T(I)|size(I)=n}平均情况下的时间复杂性Tavg(n)=

其中I是问题的规模为n的实例，p(I)是实例I出现的概率。512.2时间复杂性计算为了能够较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算.522.2时间复杂性计算在一般的计算机系统中，基本的运算和操作有以下四类：

①算术运算：主要包括加、减、乘、除等运算。

②逻辑运算：主要包括“与”、“或”、“非”等运算。

③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。

④数据传输：主要包括赋值、输入、输出等操作。规定其中每条指令所需的时间都为常量。算法的执行时间=原子操作的执行次数×原子操作的执行时间53template<classType>voidInsertionSort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumof(ti-1) }a[j+1]=key;//c7n-1

}}2.2时间复杂性计算54在最好情况下，ti=1,for1

i<n;在最坏情况下，ti＝

i+1,for1

i<n;2.2时间复杂性计算55算法的时间复杂度如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法的时间复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。56复杂性分析的简化令T(N)为表示算法A的复杂性函数，若存在Ť(N)，使得LimN(T(N)–Ť(N))/T(N)=0那么，就可以用Ť(N)来代替T(N)，从而简化复杂性的分析。例如：T(N)=3N2+4NlogN+7，Ť(N)=3N2，则

LimN(T(N)–Ť(N))/T(N)=LimN4NlogN+7/3N2+4NlogN+7=057用阶来表示复杂性在渐进复杂性分析中，只要关心Ť(N)的阶就够了，不必关心Ť(N)中的常数因子，这样我们就只需要用Ť(N)的阶来表示该算法的复杂性。例如，计算一个N维矩阵A的平方的时间复杂性可估算为2N*N2=2N3，即此计算的时间复杂性为3阶。582.3时间复杂性的渐近性态时间复杂性的渐近性态：(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。59几个记号设f(N)、g(N)都是定义在正整数集上的函数。上界记号O：如果存在正的常数C和自然数N0，使得当N≧N0

时有f(N)≦Cg(N)，则f(N)有上界函数g(N)，记为f(N)=O(g(N))。下界记号Ω：如果存在正的常数C和自然数N0，使得当N≧N0

时有f(N)≧Cg(N)，则f(N)有下界函数g(N)，记为f(N)=Ω(g(N))。同阶记号Θ：f(N)=Θ(g(N))表示f(N)和g(N)同阶。低阶记号o：f(N)=o(g(N))表示f(N)比g(N)低阶602.3时间复杂性的渐近性态渐近上界记号OO(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)

cg(n)}例如：3n-10=O(n);n2+2n+3=O(n2);3logn+loglogn=O(logn);常数=O(1)612.3时间复杂性的渐近性态大O的运算性质：O(f)+O(g)=O(max(f,g));O(f)+O(g)=O(f+g);O(f)O(g)=O(fg);如果g(n)=O(f(n)),则O(f)+O(g)=O(f);O(cf(n))=O(f(n)),其中c是一个正的常数；f=O(f);如果f(n)是次数为d的多项式，即f(n)=adnd+…+a1n+a0，则f(n)=O(nd)在大O符号中包含常数因子和低阶项被认为是不好的。应该用大O的最简单形式描述算法的时间复杂性。应该用大O符号尽可能接近地表征一个函数。622.3时间复杂性的渐近性态渐近下界记号

(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0

cg(n)

f(n)}渐近确界记号⊙

当且仅当f(n)=O(g(n))且f(n)=(g(n))，定义f(n)=⊙(g(n))。表示f(n)与g(n)同阶。632.3时间复杂性的渐近性态非紧上界记号o若对于任意正常数c>0，存在常数n0>0，当n>=n0时，满足0f(n)cg(n)，则称f(n)=o(g(n))。非紧下界记号若对于任意正常数c>0，存在常数n0>0，当n>=n0时，满足0cg(n)f(n)，则称f(n)=(g(n))。例如，f(n)=12n2+6n=o(n3)=(n)直观上，o(.)在渐近意义上类似于“小于”，(.)在渐近意义上类似于“大于”。642.4非递归算法分析例1：交换i和j的内容Temp=i；i=j；j=temp；以上三条单个语句的执行次数均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=Ο(1)。652.4非递归算法分析例2：求数组最小值

intArrayMin(inta[],intn){min=a[0];for(i=1;i<n;i++)if(a[i]<min)min=a[i];returnmin;}循环体内计算时间*循环次数。如果循环变量与问题规模n有关，则时间复杂度一般为O(n)。

662.4非递归算法分析例3：嵌套循环情况(1)x=0；y=0；(2)for(k=1；k<=n；k++)(3)x++；(4)for(i=1；i<=n；i++)(5)for(j=1；j<=n；j++)(6)y++；该算法段的时间复杂度为T(n)=Ο(n2)。当有若干个嵌套循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的执行次数决定的。672.4非递归算法分析例4：嵌套循环情况for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=0;k<=n;++k)c[i,j]=c[i,j]+a[i,k]*b[k,j]; }该算法时间复杂度为O(n3

)68非递归算法的基本法则：顺序语句：各语句计算时间相加；for/while循环：循环体内计算时间*循环次数；嵌套循环：最深层循环体内计算时间*所有循环次数；if-else语句：if语句计算时间和else语句计算时间的较大者。2.4非递归算法分析692.5递归算法分析递归算法：建立递归方程;递推（迭代）求解例1：求n!intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}70îíì>+==15)2(217)(2nnnTnnT)(2nO=222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×´+++=+++=++=+=--L2.5递归算法分析例2：71例线性对数阶O(log2n)：

i=1;

①

while(i<=n)

i=i*2;②解：语句1的频度是1,

设语句2的频度是f(n),

则：2^f(n)<=n;f(n)<=log2n

取最大值f(n)=log2n,

T(n)=O(log2n)72Ο(1)称为常数级Ο(logn)称为对数级Ο(n)称为线性级Ο(nc)称为多项式级Ο(cn)称为指数级Ο(n!)称为阶乘级(n为问题的规模,c为一常量)2.6算法复杂性的一般表示形式低高时间复杂性73提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法74用c++描述算法75（1）选择语句：（1.1)if语句：（1.2)？语句：

if(expression)statement;elsestatement;exp1?exp2:exp3y=x>9?100:200;等价于：if(x>9)y=100;elsey=200;76（1.3)switch语句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statement