《C教程第3章程序控制与算法》由会员分享，可在线阅读，更多相关《C教程第3章程序控制与算法（63页珍藏版）》请在金锄头文库上搜索。
1、C#C# C# 程序设计大学教程程序设计大学教程程序控制与算法程序控制与算法程序控制与算法程序控制与算法C#C#C#3.13.1表达式与运算符表达式与运算符3.23.2流程控制流程控制C#C#C#3.13.1表达式与运算符表达式与运算符表达式与运算符表达式与运算符3.1.1表达式3.1.2运算符3.1.3运算符的优先级 C#C#C#3.1.13.1.1表达式表达式表达式表达式 一个表达式就是一个能够返回值的简单结构。最简单的表达式是变量和常量。在C#中也可以通过使用运算符、方法调用以及类型转换等，建立复杂的表达式。 建立表达式没有通用的方法，因为要取决于所用的运算符 。C#C#C#3.1.23
2、.1.2运算符运算符运算符运算符运算符是用来完成一个动作的特定语言的语法记号。1.1.赋值运算符赋值运算符2.2.增减运算符增减运算符3.3.算术运算符算术运算符4.4.关系运算符关系运算符5.5.逻辑运算符逻辑运算符6.6.位运算符位运算符 C#C#C#3.1.33.1.3运算符的优先级运算符的优先级运算符的优先级运算符的优先级运算规则：优先级高的运算符在优先级低的运算符之前求值，优先级相同时自左向右求值。 C#C#C#3.23.2流程控制流程控制流程控制流程控制 Bohm和Jacopini的工作证明，任何程序流程均可以用如下三种控制结构实现： 1顺序结构2选择结构3循环结构C#C#C#3.
3、2.13.2.1顺序结构顺序结构顺序结构顺序结构 通常，程序中的语句是按照编写时写入的顺序一条接一条地执行的，这一过程称为顺序执行（sequential execution）。 顺序执行的C#代码通常以程序块为独立的单位。C#程序块是以一对大括号括起的任意数量的简单语句，程序块可以嵌套使用 。C#C#C#3.2.23.2.2选择结构选择结构选择结构选择结构 C# C#提供的两种选择结构（也可称为条提供的两种选择结构（也可称为条件控制结构）：件控制结构）： 1.if语句2.2.switchswitch语句语句C#C#C#3.2.23.2.2选择结构选择结构选择结构选择结构1.1.ifif语句语句
4、简单if语句C#C#C#3.2.23.2.2选择结构选择结构选择结构选择结构If-else语句C#C#C#3.2.23.2.2选择结构选择结构选择结构选择结构（3）嵌套的if语句 C#C#C#3.2.23.2.2选择结构选择结构选择结构选择结构2.switch语句 C#C#C#3.2.23.2.2选择结构选择结构选择结构选择结构2.switch语句switch语句以关键字switch开始，后跟计算选择值的表达式，然后跟着关键字case开始的各个分支。switch语句被执行时，表达式首先被计算，根据它的值，其中某个case分支可以被执行。 switch语句中的每个分支都以case和一个值开始。这
5、个值必须是常量，而不能是不确定的变量。 switch语句中每个case子句的语句块最后的break不能省略。 可以使用goto跳转至同一个switch的另一个case中。C#C#C#3.2.23.2.2选择结构选择结构选择结构选择结构switch语句与if语句的比较：当需要在多个条件中选择时，简洁的当需要在多个条件中选择时，简洁的switchswitch语句要比语句要比ifif的的嵌套语句更方便。嵌套语句更方便。 switchswitch语句要输入的关键字少；语句要输入的关键字少；switchswitch语句语句“视觉清晰视觉清晰”并且更容易维护；并且更容易维护；不必担心分支的分隔规则，因为不
6、必担心分支的分隔规则，因为switchswitch语句的每一个分支语句的每一个分支都是用分号结束；都是用分号结束；switchswitch语句更容易维护，因为增加一个分支时要做的只是语句更容易维护，因为增加一个分支时要做的只是插入几行；插入几行；通过表达式的选择通过表达式的选择switchswitch语句更易说明哪个值对应哪个要语句更易说明哪个值对应哪个要执行的分支执行的分支 。C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构 循环结构（或称为重复结构、迭代结构）是使用条件表达式来控制一个（一组）动作的重复执行的。C#语言中支持的循环语句包括：1. while循环 2. do-
7、while循环 3. for循环4. foreach循环C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构1. while 循环 while循环是最常用的程序设计结构之一，可以用它去模拟很多其他结构。while循环是最有用的程序设计工具之一，每个程序员都必须掌握它。while 循环的一般语法如下：while (布尔表达式) 语句; C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构2. do-while循环 当至少要执行一次或更多次循环时，使用do-while循环较方便。要记住，如果while循环的起始条件检查为flase，则一次循环也不执行。while循环条件检查
8、是先于循环中其他语句执行的，而do-while循环的条件检查则位于循环体语句序列的尾部。因此，循环体至少执行一次，即使循环条在第一次检查时就为假也是如此。C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构do-while循环的语法如下：do 语句; while (while (布尔表达式布尔表达式);); C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构3. for循环 for循环是计数步进循环，计数变量跟踪通过循环的重复次数，循环的重复是从计数器的开始值到预定的终止值。根据每次通过循环时计数器的变化（增或者减），又可以将For循环分为增量for循环和减量for循
9、环。C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构for循环的一般语法如下：for ( 初值表达式 ; 布尔表达式 ; 步进表达式 ) 语句; C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构4.foreach循环 foreach(类型 标识符 in 表达式) 循环体foreach 循环允许遍历支持 IEnumerable 接口的容器类中的每一项（例如：数组） C#C#C#3.2.33.2.3循环结构循环结构循环结构循环结构public static void Main() int arr1= new int 1,2,3,4,5,6; foreach ( in
10、t i in arr1) Console.WriteLine(Value is 0, i); C#C#C#3.3 3.3 算法算法算法算法 算法的英文单词为“Algorithm”。这个单词一直到1957年之前，在韦氏新世界词典中还未出现，我们只能找到带有它的古代涵义的“Algorism（算术）”，指的是用阿拉伯数字进行算术运算的过程。一本早期的德文数学词典数学大全辞典，给出了另一个单词“Algorithmus”的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。C#C#C#五个重要的特征：确确切切性性（No No ambiguityambiguity） 算
11、法的每一步骤必须有确切的定义。而不应该有二义性，例如，在算法中不能出现诸如“赋值为100或1000”。输入入（InputInput） 有0个或多个输入，用于初始化运算对象。所谓0个输入是指无需输入条件，而算法本身定出了初始条件。输出出（OutputOutput） 没有输出的算法是毫无意义的。一个算法应该有一个或多个输出，以反映对输入数据加工后的结果。C#C#C#可可行行性性（FeasibilityFeasibility） 算法原则上能够精确地运行，而且对于算法中的每种运算，在原理上人们应该能用笔和纸做有限次运算后完成。有有穷性性（FiniteFinite） 算法必须保证执行有限步之后结束。只具
12、有前面四个特征的规则集合，称不上算法。例如，尽管操作系统能完成很多任务，但是它的计算过程并不终止，而是无穷无尽的执行、等待执行，所以操作系统不是算法。C#C#C#算法举例算法举例算法举例算法举例问题一、100位乒乓球选手通过淘汰赛，最后产生一名冠军，问至少需要多少场比赛？C#C#C#算法举例算法举例算法举例算法举例解法1、100位选手分50组比赛，淘汰50位选手，剩下的50位选手分25组比赛，淘汰25位选手 需要50+25+12+6+3+2+1=99C#C#C#算法举例算法举例算法举例算法举例解法2、比赛的场数与每一场淘汰的选手数一一对应。 每比赛一场则淘汰一名选手，100位选手中产生冠军需要
13、淘汰99位选手，所以至少需要进行99场比赛。C#C#C#算法举例算法举例算法举例算法举例问题二、计算n!C#C#C#算法举例算法举例算法举例算法举例解法1：n值较小时，s=n!、n均用整型变量存储 n!=n(n-1)!long s=1;for(int n=1;n=10;n+) s=s*n;C#C#C#算法举例算法举例算法举例算法举例解法2：n值不太大（能用整型变量存储）时，s=n!使用整型数组存储，每个元素表示n!的一个十进制位上的数，n用整型变量存储。C#C#C#算法举例算法举例算法举例算法举例解法3：n很大（不能使用整型变量存储）时，分别使用整型数组存储n!和n，每个元素表示一位十进制数。
14、使用卷积法计算乘积。如123456=（4）（13）（28）（27）（18）=56088C#C#C#算法举例算法举例算法举例算法举例思考题：用C#描述小学学习过的乘法竖式算法。C#C#C#算法举例算法举例算法举例算法举例问题三、多项式乘法用数组存储多项式系数，使用卷积计算多项式乘积。C#C#C#算法举例算法举例算法举例算法举例问题四、多项式除法C#C#C#算法举例算法举例算法举例算法举例问题五、计算组合数C(n,r)。C#C#C#算法举例算法举例算法举例算法举例解法1：n很小时 C(n,r)=n!/r!/(n-r)!C#C#C#算法举例算法举例算法举例算法举例解法2：n很大时C(n,r)=(n-
15、1,r)+(n-1,r-1)C#C#C#算法举例算法举例算法举例算法举例问题六、判断一个整数n是否能被3整除。C#C#C#算法举例算法举例算法举例算法举例解法1：n不太大时n%3=0C#C#C#算法举例算法举例算法举例算法举例解法2：n很大（不能用整型变量存储）时。用整型数组array存储n，每个元素表示一位十进制数。(arrayi)%3=0C#C#C#算法举例算法举例算法举例算法举例问题七、生成指定排列p的下一个排列的算法。C#C#C#算法举例算法举例算法举例算法举例解法：字典序法Step 1 计算满足关系式pj-1pj的j的最大值，设为i，即i=maxj|pj-1pi-1的k的最大值，设为
16、h，即h=maxk|pkpi-1Step 3 将pi-1和ph交换Step 4 将下标i以后的元素逆转C#C#C#算法举例算法举例算法举例算法举例问题八、n个盘子的汉诺塔，需要移动盘子多少次？C#C#C#算法举例算法举例算法举例算法举例解法：设移动n-1个盘子需要h(n-1)次，则移动n个盘子需要2h(n-1)+1次；h(1)=1。所以，h(n)=2n-1C#C#C#算法举例算法举例算法举例算法举例问题九、若有1克的砝码2枚，2克的砝码3枚，3克的砝码2枚，问能称出哪些重量？C#C#C#算法举例算法举例算法举例算法举例解法：母函数法G(x)=(1+x+x2)(1+y2+y4+y6)(1+z3+
17、z6) =(1+y2+y4+y6+x+xy2+xy4+xy6+ x2+x2y2+ x2y4+x2y6)(1+z3+z6) =1+y2+y4+y6+x+xy2+xy4+xy6+x2+x2y2+x2y4+x2y6 +z3+y2z3+y4z3+y6z3+xz3+xy2z3+xy4z3+xy6z3+x2z3+ x2y2z3+x2y4z3+x2y6z3+z6+y2z6+y4z6+y6z6+xz6+ xy2z6+xy4z6+xy6z6+x2z6+x2y2z6+ x2y4z6+x2y6z6C#C#C#算法举例算法举例算法举例算法举例问题十、RSA快速算法背景：RSA算法原理（1）选择大素数p、q，要求为强素
18、数（2）计算n=pq，f(n)=(p-1)(q-1)（3）选择数e，使得(e,f(n)=1（4）计算数d，使得ed mod f(n)=1（5）销毁p、q加密：c=me mod n解密：m=cd mod n模幂计算量很大C#C#C#算法举例算法举例算法举例算法举例解法1：秦九韶算法,b为指数的二进制形式Step 0 c=1,i=L-1Step 1 set c=c*c mod nStep 2 if bi=1 set c=c*m mod n i=i-1Step 3 goto step 1C#C#C#算法举例算法举例算法举例算法举例解法2：最短加法链设的最短加法链为1=e0,e1,en=e，且满足ei
19、=ej+ek，0j,ki-1则计算的计算过程为 如计算计算过程为C#C#C#算法举例算法举例算法举例算法举例问题十一、图像中值滤波算法C#C#C#算法举例算法举例算法举例算法举例解法1：将中心像素某r邻域的所有像素值排序，用中位数代替中心像素的值。C#C#C#算法举例算法举例算法举例算法举例解法2：符号检验法选择中心像素r邻域中一个像素p，用p的值与其他所有像素进行比较，如果大于该值的像素个数与小于该值的像素个数相等或相对误差很小，则用p的值代替中心像素的值。C#C#C#基本算法基本算法基本算法基本算法3.3.3 排序 由于数组中存有同一数据类型的数据，而有时为了更有效地使用数组，就需要对数组
20、中的元素进行排序，使其按一定的顺序排列好，比如按关键字的值从小到大排序。排序算法有很多，如：冒泡排序、选择排序、插入排序、快速排序、合并排序、希尔（Shell）排序、堆排序等.C#C#C#基本算法基本算法基本算法基本算法3.3.4 查找 查找就是从列表（list）或者数组中找出需要的数据项，确定目标所在位置的算法，也叫检索。查找问题的一般提法是：设一数组有n个元素，每个元素由一个称为关键字的数据项和若干相关数据项的值组成，对给定值K，要查找出这n个数组元素中是否存在关键字等于K的某个元素。通常有两种结果，一种是能够检索到，即查找成功，此时查找的结果为给出整个元素的信息，或指出该元素所在的位置；
21、另一种是找不到，即失败，此时查找的结果为不成功的信息。C#C#C#3.3.5 算法复杂性分析 算法的复杂性是指：在执行时，算法所需要计算机资源的量。需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。C#C#C#1. 时间复杂性 时间复杂性描述了算法在计算机上执行时，所占用的计算机时间资源的情况。它是一种抽象的描述方式，并不是指与算法实现效率有关的算法执行时间，而是指理论上与问题规模、算法输入及算法本身相关
22、的某些操作次数的总和，通常记为T(n)。C#C#C# 比较时间复杂性时经常使用这样的表达方式：如果存在一个常数C0，一个算法能够在C*n2 的时间内处理完规模大小为n的输入，则该算法的时间复杂性为 O(n2 )，称为n2级。从计算时间上可以把算法分成两类，凡可用多项式来对其计算时间限界的算法，称为多项式时间算法（Polynomial Time Algorithm）；而计算时间用指数函数限界的算法称为指数时间算法（Exponential Time Algorithm）。C#C#C#C#C#C#2. 递推与递归递推：从前向后递归：从后向前例1：FibonacciF(n)=F(n-1)+F(n-2)例2：HannoiH(n)=2H(n-1)+1例3：n!n!=n(n-1)!C#C#C#习题习题习题习题0、用C#实现本课件中的算法。课后2837题C#C# C# 程序设计大学教程程序设计大学教程
