第3章 算法与程序设计

算法与程序设计第3章讲课人：***目录01中国古典数学02算法概述03算法策略04经典算法设计05程序设计知识导图本章节主要为同学们介绍算法及程序设计的相关知识。程序员的主要任务是根据用户的需求为计算机设计算法。计算机的工作特点是可以快速地重复，因此，算法多是“重复”，表现为循环和递归。循环是有条件的重复。穷举与迭代最常见。嵌套的循环往往意味着“自顶向下，逐步求精”，多用于处理复杂的问题。递归算法是“规模上”的重复，可完美解决特定的问题。本章最后简要介绍了一些常见的查找与排序算法及程序设计语言。本章内容中国古典数学第3章01作为世界四大文明古国之一，中国从很早开始就发展出了自己的数学体系。商代的甲骨文上出现了完整的十进制，春秋时代严格的筹算已经成型并得到了广泛的应用，战国时代《考工记》中实用的几何知识流传到今天。《张丘建算经》：最小公倍数的应用、等差数列各元素互求、“百鸡术”。《周髀算经》：勾股术。《九章算术》：开平方和开立方的方法、一般一元二次方程(首项系数不是负)的数值解法。《海岛算经》：“割圆术”开创了中国古代圆周率计算方面的重要方法。算法概述第3章023.2.1算法的概念所谓算法，就是指完成某一特定任务所需要的具体方法和步骤的有序集合。“有序”说明算法中的步骤是有顺序关系的。同时，算法所描述的步骤也应该是“明确的”和“可执行的”，这样算法才可以实现。著名的计算机科学家尼古拉斯·沃斯（NiklausWirth）曾提出一个著名的公式：

程序=算法+数据结构3.2.2算法的特征有穷性（Finiteness）确切性（Definiteness）输入项（Input）输出项（Output）可行性（Effectiveness）3.2.3算法的描述1.自然语言表示法2.伪代码表示法3.流程图表示法4.N-S图表示法算法策略第3章033.3.1循环计算机的工作特点是可以高速地重复，因此在设计算法时常用循环（特定条件下的重复）解决问题。1.模拟重复以编程计算1+2+3+…+100的和为例来说明如用循环解决问题。先求1+2+3+4+5的和。1+2+3+4+5=3+3+4+5=6+4+5=10+5=15整个计算过程就是重复算加法。什么数在相加呢？前一次的和与新的加数。用存储单元sum存储和，存储单元i存储加数，计算过程就是把把sum中的数与i中的数相加，结果还存入sum中。这个过程可记为sum=sum+i;。人工计算

1+2+3+4+5=3+3+4+5=6+4+5=10+5=15代码命令sum=1,i=2;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;计算过程的模拟用循环计算sum=1,i=2;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;intsum=1,i=2;while(i<=5){sum=sum+i;i=i+1;}1+2+3+4+5intsum=1,i=2;while(i<=5){sum=sum+i;i=i+1;}1+2+3+…+100intsum=1,i=2;while(i<=100){sum=sum+i;i=i+1;}用循环计算1+2+3+…+1002.穷举与迭代尝试所有可能的选项以找到正确答案的方法又称为穷举法。一百个僧人分一百个馒头，大僧每人分三个，小僧三人分一个，正好分完。问大小僧各几人？尝试所有的可能。大僧1人时，小僧（100-1）人，需要馒头3*1+(100-1)/3个，如果馒头的个数等于100，就找到了答案，输出大小僧的人数；否则，就不输出。大僧2人时，小僧（100-2）人，需要馒头3*2+(100-2)/3个，如果馒头的个数等于100，就找到了答案，输出大小僧的人数；否则，就不输出。……大僧33人时，小僧（100-33）人，需要馒头3*33+(100-33)/3个，如果馒头的个数等于100，就找到了答案，输出大小僧的人数；否则，就不输出。穷举法整个过程可描述为。//大僧1人时当3*1+(100-1)/3==100时，输出大僧:1,小僧:100-1;//大僧2人时当3*2+(100-2)/3==100时，输出大僧:2,小僧:100-2;……//大僧33人时当3*33+(100-33)/3==100时，输出大僧:33,小僧:100-33;显然大僧的人数在重复，从1重复到33。用存储单元i存放大僧的人数，初值设置为1，如i<=33成立，重复下面的两步：当3*i+(100-i)/3==100时，输出大僧:i,小僧:100-i;i=i+1;一百个僧人分一百个馒头inti=1;while(i<=33){if(3*i+(100-i)/3==100)printf("大僧:%d,小僧:%d\n",i,100-i);i=i+1;}迭代法

迭代公式

3.自顶向下，逐步求精“自顶向下，逐步求精”是分析解决复杂问题行之有效的方法。“自顶向下”要求从宏观上分析，不拘泥于细节，理清脉络把握问题的本质；“逐步求精”要求从局部着力，从细节入手，分析问题的独特性，针对具体问题，列举“原始数据”发现“规律”，最终解决问题。用循环输出如下图形图形共5行，输出第1行；输出第2行；输出第3行；输出第4行；输出第5行。这个过程是重复，“行”在重复，重复了5次。这个过程可用图表示第i行什么样子呢？第1行有一个“空格星号*”和一个换行符，第2行有2个“空格星号*”和一个换行符，……，因此第i行有i个“空格星号*”和一个换行符。怎样输出i个“空格星号*”呢？输出第1个“空格星号*”，输出第2个，

输出第3个，……，输出第i个。可见输出第i行的过程是重复，可以用图表示。用循环输出如下图形inti,j;i=1;while(i<=5){j=1;while(j<=i){

printf("*");j=j+1;}printf("\n");i=i+1;}用循环输出如下图形如果忽略细节，则这个图形也有5行，依然是输出第1行；输出第2行；输出第3行；输出第4行；输出第5行。这个过程是重复，“行”在重复，重复了5次。这个过程依然可用图表示。第i行什么样子呢？第1行有4个“空格空格”、一个“空格星号*”和一个换行符，第2行有3个“空格空格”、3个“空格星号*”和一个换行符，……，因此第i行有5-i个“空格空格”、2*i-1个“空格星号*”和一个换行符。可以先输出5-i个“空格空格”，再输出2*i-1个“空格星号*”，最后输出一个换行符。这个过程可用图表示。用循环输出如下图形自顶向下，逐步求精当忽略细节从宏观上看时，两个图形的形状“相同”，都有五行，可以用相同的循环结构输出。重复5次，每次输出一行，即输出第i行。这种把握本质忽略细节的分析方法可称为“自顶向下”。在确定第i行是什么样子时，从第1行的具体形状开始，依次分析每行的具体形状，关注细节，在综合“原始数据”的基础上总结出规律，即第i行的形状。“关注细节”恰恰是进一步（“逐步求精”）分析时所强调的。3.3.2递归分析问题时经常发现，一些难以直接解决的规模较大的问题，往往可以转化为一些规模较小且与原问题性质相同的子问题。问题的难易程度通常与其规模相关，问题的规模越小，问题就越容易解决。以求523的阶乘为例，523！等于523×522！，原问题变成了523乘以522的阶乘。虽然还需计算乘法，但只要知道了522的阶乘，进行一次乘法运算求出523的阶乘应该不难。与原问题相比，现在问题的关键依然是求一个数的阶乘，问题的性质没有变，不过，原来需求523的阶乘，现在只要求出522的阶乘即可，问题的规模变小了，难度降低了。递归与原问题性质相同就意味着子问题可以继续转化为规模更小性质相同的子问题，新得到的子问题还可以继续转化，……，只要性质相同，转化的过程就可以一直重复下去。当转化后子问题的规模小到可以很容易地求解时，转化的过程就可以停止了。子问题有解后，就可以按照转化的过程逆向求解，每次都得到规模稍大一点的子问题的解，最终就能得到原问题的解。原问题转化子问题的过程可称为递进；由子问题的解构造原问题的解的过程可称为回归。通过递进和回归两个过程解决问题的方法称为“递归”。用递归算法求阶乘设函数fac可以求出整数n的阶乘，该函数的首部为intfac(intn)。求2的阶乘时用fac(2)；fac(2)的执行结果就是2的阶乘。实现递归算法时一定要转化为规模较小的子问题呢？那倒未必。如果整数n的规模已经小到能轻易地求出它的阶乘时（如0或1），就不再需要转化的过程了，直接返回结果；否则，求整数n的阶乘需要转化成求n-1的阶乘，返回n*(n-1)!的值。函数可定义为：用递归算法求阶乘C语言中有乘法命令，但没有求整数阶乘的命令，怎样命令计算机求出(n-1)的阶乘呢？函数fac的功能是求一个整数的阶乘，函数是C语言中的自定义命令，可以用函数fac命令计算机求出(n-1)的阶乘。fac(n)的返回值为n的阶乘，相应地fac(n-1)的返回值就是(n-1)的阶乘。求出了(n-1)的阶乘，函数fac也就定义好了。使用fac函数求3的阶乘可以使用fac函数求出3的阶乘。printf("3!=%u\n",fac(3));，语句的运行结果为：递归示例楼梯有n阶台阶，上楼时一步可以上1阶，也可以上2阶，计算n阶楼梯共有多少种不同的走法。分析：设n阶台阶的走法为f(n)，当楼梯只有1阶时，显然只有一种走法，f(1)=1。只有2阶时，有两种走法，一步一阶地或一步两阶地走上楼梯,f(2)=2。楼梯多于2阶的时，有几种走法呢？递归示例上楼梯时，第一步可以上1阶也可以上2阶并且只有这两种情况，也就是说，楼梯的所有不同走法等于这两种情况下上完整个楼梯的不同走法之和，即f(n)等于第一步上1阶时的走法加上第一步上2阶时的走法。第一步上1阶时上完整个楼梯的走法有多少种呢？它等于余下的n-1阶台阶的所有不同走法，于是问题变成了上有n-1阶台阶的楼梯有多少种走法？性质相同，规模变小了。n阶台阶的走法为f(n)，所以上n-1阶台阶的楼梯共有f(n-1)种走法。4阶楼梯的走法棋盘覆盖问题问题描述：在一个2k×2k个方格组成的棋盘中，有一个带有特殊标记的方格。要求是用4种不同形态的L型骨牌覆盖棋盘上除特殊方格以外的所有方格，在覆盖时L型骨牌不能重叠。如图所示。棋盘覆盖问题首先，解决如何在程序中表示棋盘的问题。可以用一个二维整型数组表示棋盘，如上面的棋盘可表示为：intchessboard[4][4]={0};，把特殊方格对应的元素赋值为-1（chessboard[0][1]=-1），则数组元素输出后即可形成棋盘形状，棋盘覆盖问题其次，表示L型骨牌的覆盖。把同一个L型骨牌覆盖的方格赋值为同一个整数，输出时用相同的数字模拟骨牌的形状。棋盘覆盖问题第一步：把棋盘一分为4，形成4个2k-1×2k-1个方格组成棋盘。如图所示。棋盘覆盖问题第二步：观察大棋盘中心位置的四个小方格，它们分属四个小棋盘，会发现其中一个小方格所在的小棋盘与其它三个不同，因为它包含了特殊方格。棋盘覆盖问题第三步：不考虑包含了特殊方格的小棋盘中的小方格，剩下的三个小方格恰好构成一个L型骨牌，用相同的数字标记这三个小方格，完成一个L型骨牌的覆盖，如图所示。棋盘覆盖问题第四步：观察这四个小棋盘会发现它们都是一个2n×2n（n的值为k-1）个方格组成的棋盘，且棋盘中都有一个带有特殊标记的方格，即黑色的方格（在程序中为非0的方格）。现在的任务是用L型骨牌覆盖这四个小棋盘，如图所示。棋盘覆盖问题依次用L型骨牌覆盖这四个小棋盘。先处理左上角的小棋盘。左上角的小棋盘由21×21个方格和一个特殊方格组成。任务相同，规模变小，可以用递归算法处理。其它三个小棋盘也用递归算法处理，任务完成。为便于初学者理解，下面详细分析一下用递归算法处理左上角小棋盘的过程。棋盘由21×21个方格组成，k的值为1，规模还是较大，应继续依照前面的步骤处理，即先把棋盘一分为四，如图所示。棋盘覆盖问题不考虑含有特殊方格小棋盘中的小方格，完成一个L型骨牌的覆盖恰好构成一个L型骨牌，用相同的数字标识这三个方格，完成一个L型骨牌的覆盖，棋盘覆盖问题图中的四个小棋盘均由一个小空格组成，处理这个四个小棋盘时依然要一分为四。左上角由一个小空格组成棋盘一分为四时，它们由20×20个方格组成，k的值为0，显然还是一个棋盘，且这个小空格还是特殊方格，因此，当k的值为0时，无须继续处理，不用再“递推”了。至此，左上角的小棋盘完成了覆盖。棋盘覆盖问题对于由2k×2k个方格组成的棋盘，如果k的值等于0，则棋盘由特殊方格组成无须覆盖，直接返回；否则，先把这个棋盘一分为四，找到中心位置的四个小方格，不考虑包含了特殊方格的小棋盘中的小方格，剩下的三个小方格恰好构成一个L型骨牌，用相同的数字标识标识这些小方