算法及其复杂性分析.ppt

《算法及其复杂性分析.ppt》由会员分享，可在线阅读，更多相关《算法及其复杂性分析.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析实用教程杨克昌 严权锋请用请用PowerPoint 2003PowerPoint 2003播放播放中国水利水电出版社n 课堂讲授课堂讲授课堂讲授课堂讲授 ：n学时安排：学时安排：学时安排：学时安排：36363636（讲授）（讲授）（讲授）（讲授）18181818（上机）（上机）（上机）（上机）(可根据实际教学计划进行调整；第可根据实际教学计划进行调整；第9 9 章不讲授，作为章不讲授，作为“算法设计与分析课程设计算法设计与分析课程设计”题材选用题材选用)n算法设计在案例求解中的地位与应用。算法设计在案例求解中的地位与应用。n算法时间复杂度分析方法与算法优劣评价。算法时间复杂度分析

2、方法与算法优劣评价。n重点讲授重点讲授应用算法设计求解典型案例，并进行复应用算法设计求解典型案例，并进行复杂性分析，引导设计变通。杂性分析，引导设计变通。n小组讨论小组讨论与基本案例相关的拓展与引申案例求解，与基本案例相关的拓展与引申案例求解，为为“课程设计课程设计”作准备。作准备。n 上机实践：上机实践：上机实践：上机实践：n学习建议：学习建议：学习建议：学习建议：n n学会归纳、总结和提炼；学会归纳、总结和提炼；n n自觉调整学习状态：自觉调整学习状态：培养算法设计与分析的兴趣培养算法设计与分析的兴趣自觉完成布置的作业自觉完成布置的作业加深对算法应用的理解加深对算法应用的理解善于变通、拓展

3、与改进善于变通、拓展与改进n n注重算法设计，提高解决实际案例的能力。注重算法设计，提高解决实际案例的能力。上机环境：上机环境：VC+6.0VC+6.0上机通过每章指定的案例求解与习题上机通过每章指定的案例求解与习题按要求填写实验报告按要求填写实验报告 教学要求教学要求了解了解了解了解算法概念、算法特征及算法的描述算法概念、算法特征及算法的描述算法概念、算法特征及算法的描述算法概念、算法特征及算法的描述建立建立建立建立算法的复杂性概念算法的复杂性概念算法的复杂性概念算法的复杂性概念掌握结构化掌握结构化掌握结构化掌握结构化设计设计设计设计的基本方法的基本方法的基本方法的基本方法 本章重点本章重点

4、应用应用应用应用 c c c c 语言描述算法语言描述算法语言描述算法语言描述算法掌握常用算法时间复杂度分析掌握常用算法时间复杂度分析掌握常用算法时间复杂度分析掌握常用算法时间复杂度分析第第第第 1 1 1 1 章章章章 算法及其复杂必分析算法及其复杂必分析1.1 1.1 算法及其描述算法及其描述算法是程序设计的基础，是计算机科学的核心。算法是程序设计的基础，是计算机科学的核心。算法是程序设计的基础，是计算机科学的核心。算法是程序设计的基础，是计算机科学的核心。1.1.1 1.1.1 1.1.1 1.1.1 算法定义算法定义算法定义算法定义 算法是计算机解决问题的过程，是解决某一算法是计算机解

5、决问题的过程，是解决某一算法是计算机解决问题的过程，是解决某一算法是计算机解决问题的过程，是解决某一问题的运算序列。问题的运算序列。问题的运算序列。问题的运算序列。或者说算法是或者说算法是或者说算法是或者说算法是问题求解过程的运算描述问题求解过程的运算描述问题求解过程的运算描述问题求解过程的运算描述。当面临某一问题时，算法就是当面临某一问题时，算法就是当面临某一问题时，算法就是当面临某一问题时，算法就是解决这个问题解决这个问题解决这个问题解决这个问题的方法与步骤的描述的方法与步骤的描述的方法与步骤的描述的方法与步骤的描述。1.1.算法的三要素算法的三要素 n n算法由操作、控制结构与数据结构算

6、法由操作、控制结构与数据结构三者组成。三者组成。(1)(1)(1)(1)操作：算术运算，关系运算，逻辑运算；输入、操作：算术运算，关系运算，逻辑运算；输入、操作：算术运算，关系运算，逻辑运算；输入、操作：算术运算，关系运算，逻辑运算；输入、输出、赋值等操作。输出、赋值等操作。输出、赋值等操作。输出、赋值等操作。(2)(2)(2)(2)控制结构：顺序结构，选择结构，循环结构，控制结构：顺序结构，选择结构，循环结构，控制结构：顺序结构，选择结构，循环结构，控制结构：顺序结构，选择结构，循环结构，模块调用。模块调用。模块调用。模块调用。(3)(3)(3)(3)数据结构：数据之间的逻辑关系，如数组数据

7、结构：数据之间的逻辑关系，如数组数据结构：数据之间的逻辑关系，如数组数据结构：数据之间的逻辑关系，如数组 、堆栈堆栈堆栈堆栈 、队列、链表、队列、链表、队列、链表、队列、链表 、树、树、树、树 、图、图、图、图 、堆、堆、堆、堆 、散列等。、散列等。、散列等。、散列等。2.2.算法的基本特征算法的基本特征 n n一个算法由有限条可完全机械地执一个算法由有限条可完全机械地执行的、有确定结果的指令组成，具行的、有确定结果的指令组成，具有以下特性：有以下特性：n n (1)(1)确定性确定性n n(2)(2)可行性可行性n n(3)(3)有穷性有穷性n n(4)(4)算法有零个或多个输入算法有零个或

8、多个输入n n(5)(5)算法有一个或多个输出算法有一个或多个输出 1.1.2 1.1.2 算法描述算法描述 （1 1 1 1）一个问题可以设计不同的算法来求解；）一个问题可以设计不同的算法来求解；）一个问题可以设计不同的算法来求解；）一个问题可以设计不同的算法来求解；同一个算法可以采用不同的形式来描述。同一个算法可以采用不同的形式来描述。同一个算法可以采用不同的形式来描述。同一个算法可以采用不同的形式来描述。（2 2 2 2）描述算法可以有：）描述算法可以有：）描述算法可以有：）描述算法可以有：自然语言方式、流程自然语言方式、流程自然语言方式、流程自然语言方式、流程图方式、伪代码方式、计算机

9、语言表示方图方式、伪代码方式、计算机语言表示方图方式、伪代码方式、计算机语言表示方图方式、伪代码方式、计算机语言表示方式与表格方式式与表格方式式与表格方式式与表格方式等等等等。（3 3 3 3）当一个算法使用计算机程序设计语言描）当一个算法使用计算机程序设计语言描）当一个算法使用计算机程序设计语言描）当一个算法使用计算机程序设计语言描述时，就是程序。述时，就是程序。述时，就是程序。述时，就是程序。本书采用本书采用本书采用本书采用C C C C语言与自然语言相结合来描述算语言与自然语言相结合来描述算语言与自然语言相结合来描述算语言与自然语言相结合来描述算法。法。法。法。例例1-1 1-1 求两个

10、整数最大公约数的欧几里德算法求两个整数最大公约数的欧几里德算法 n n(1)(1)(1)(1)数数数数 a a a a 除以除以除以除以 b b b b 得余数得余数得余数得余数 r r r r；若；若；若；若r=0r=0r=0r=0，则，则，则，则b b b b为所求的最为所求的最为所求的最为所求的最大公约数。大公约数。大公约数。大公约数。n n(2)(2)(2)(2)若若若若 r0 r0 r0 r0，以，以，以，以b b b b为为为为a a a a，r r r r为为为为b b b b，继续，继续，继续，继续(1).(1).(1).(1).n n描述如下：描述如下：描述如下：描述如下：n

11、 nscanf(%ld,%ld,&a,&b);/scanf(%ld,%ld,&a,&b);/scanf(%ld,%ld,&a,&b);/scanf(%ld,%ld,&a,&b);/输入整数输入整数输入整数输入整数n nr=a%b;r=a%b;r=a%b;r=a%b;n nwhile(r!=0)/while(r!=0)/while(r!=0)/while(r!=0)/实施辗转相除实施辗转相除实施辗转相除实施辗转相除n n a=b;b=r;r=a%b;a=b;b=r;r=a%b;a=b;b=r;r=a%b;a=b;b=r;r=a%b;n nprintf(%ld,b);/printf(%ld,b);

12、/printf(%ld,b);/printf(%ld,b);/输出结果输出结果输出结果输出结果 1.2 1.2 算法的复杂性分析算法的复杂性分析 n n算法的复杂性越高，所需的计算机资源算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需越多；反之，算法的复杂性越低，所需的计算机资源越少。的计算机资源越少。n n最重要的计算机资源是时间资源与空间最重要的计算机资源是时间资源与空间资源。资源。n n需要计算机时间资源的量称为时间复杂需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间度，需要计算机空间资源的量称为空间复杂度。复杂度。n n时间复杂度与空间复杂度集中

13、反映算法时间复杂度与空间复杂度集中反映算法的效率。的效率。1.2.1 1.2.1 时间复杂度时间复杂度 对算法时间复杂度的分析，通常利用对算法时间复杂度的分析，通常利用实验实验对比方法、数学方法对比方法、数学方法来分析算法来分析算法。实验对比分析很简单，两个算法相互比较实验对比分析很简单，两个算法相互比较求解时间求解时间 。数学方法能在严密的逻辑推理基础上判断数学方法能在严密的逻辑推理基础上判断算法的优劣。算法的优劣。在算法分析中，我们往往采用能近似表达在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。性能的方法来展示某个算法的性能指标。一个算法的时间复杂度是指算法运行所

14、需的时一个算法的时间复杂度是指算法运行所需的时一个算法的时间复杂度是指算法运行所需的时一个算法的时间复杂度是指算法运行所需的时间。间。间。间。一个算法的运行时间取决于算法所需执行的语一个算法的运行时间取决于算法所需执行的语一个算法的运行时间取决于算法所需执行的语一个算法的运行时间取决于算法所需执行的语句（运算）的多少。句（运算）的多少。句（运算）的多少。句（运算）的多少。算法的时间复杂度通常用该算法执行的总语句算法的时间复杂度通常用该算法执行的总语句算法的时间复杂度通常用该算法执行的总语句算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。（运算）的数量级决定。（运算）的数量级决定。

15、（运算）的数量级决定。n n一条语句的数量级即执行它的频数，一个算一条语句的数量级即执行它的频数，一个算一条语句的数量级即执行它的频数，一个算一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。法的数量级是指它所有语句执行频数之和。法的数量级是指它所有语句执行频数之和。法的数量级是指它所有语句执行频数之和。n n在分析算法时，隐藏细节的数学表示方法为在分析算法时，隐藏细节的数学表示方法为在分析算法时，隐藏细节的数学表示方法为在分析算法时，隐藏细节的数学表示方法为大写字母大写字母大写字母大写字母“OOOO”记法，它可以帮助我们简化算记法，它可以帮助我们简化算记法，它可以帮

16、助我们简化算记法，它可以帮助我们简化算法复杂度计算的许多细节，提取主要成分法复杂度计算的许多细节，提取主要成分法复杂度计算的许多细节，提取主要成分法复杂度计算的许多细节，提取主要成分。http:/ 算法的执行频数的数量级直接决定算算法的执行频数的数量级直接决定算法的时间复杂度。法的时间复杂度。2 2 2 2个语句各执行个语句各执行个语句各执行个语句各执行1 1 1 1次，共执行次，共执行次，共执行次，共执行2 2 2 2次次次次。时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(1)O(1)O(1)O(1)(1)x=x+1;s=s+x;(1)x=x+1;s=s+x;例例1-3 1-3 试计算

17、下面三个程序段的时间复杂度试计算下面三个程序段的时间复杂度n n(2)for(k=1;k=n;k+)(2)for(k=1;k=n;k+)n n x=x+y;x=x+y;n n y=x+y;y=x+y;n n s=x+y;s=x+y;“k=1”“k=1”“k=1”“k=1”执行执行执行执行1 1 1 1次；次；次；次；“k=n”“k=n”“k=n”“k=n”与与与与“k+”“k+”“k+”“k+”各执行各执行各执行各执行n n n n次；次；次；次；3 3 3 3个赋值语句，每个个赋值语句，每个个赋值语句，每个个赋值语句，每个赋值语句各执行赋值语句各执行赋值语句各执行赋值语句各执行n n n n

18、次；共执行次；共执行次；共执行次；共执行5n+15n+15n+15n+1次次次次.时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(n).O(n).O(n).O(n).例例1-3 1-3 试计算下面三个程序段的执行频数试计算下面三个程序段的执行频数(3)for(t=1,k=1;k=n;k+)(3)for(t=1,k=1;k=n;k+)n t=t*2;t=t*2;n for(j=1;j=t;j+)for(j=1;j=t;j+)n s=s+j;s=s+j;“t=1”“t=1”“t=1”“t=1”与与与与“k=1”“k=1”“k=1”“k=1”各执行各执行各执行各执行1 1 1 1次；次；次；次；

19、“k=n”“k=n”“k=n”“k=n”与与与与“k+”“k+”“k+”“k+”各执各执各执各执行行行行n n n n次；次；次；次；“t=t*2”“t=t*2”“t=t*2”“t=t*2”执行执行执行执行n n n n次；次；次；次；“j=1”“j=1”“j=1”“j=1”执行执行执行执行n n n n次；次；次；次；“j=t”“j=t”“j=t”“j=t”、“j+”“j+”“j+”“j+”与内循环的赋值语句与内循环的赋值语句与内循环的赋值语句与内循环的赋值语句“s=s+j”“s=s+j”“s=s+j”“s=s+j”各执各执各执各执行频数为行频数为行频数为行频数为:总的执行频数为：总的执行频

20、数为：总的执行频数为：总的执行频数为：http:/ 时间复杂度符号时间复杂度符号OO的两个定理的两个定理:n n 在估算算法的时间复杂度时，为简单计，以后在估算算法的时间复杂度时，为简单计，以后在估算算法的时间复杂度时，为简单计，以后在估算算法的时间复杂度时，为简单计，以后只考虑内循环语句的执行频数，而不细致计算只考虑内循环语句的执行频数，而不细致计算只考虑内循环语句的执行频数，而不细致计算只考虑内循环语句的执行频数，而不细致计算各循环设计语句及其它语句的执行次数，这样各循环设计语句及其它语句的执行次数，这样各循环设计语句及其它语句的执行次数，这样各循环设计语句及其它语句的执行次数，这样简化处

21、理不影响算法的时间复杂度。简化处理不影响算法的时间复杂度。简化处理不影响算法的时间复杂度。简化处理不影响算法的时间复杂度。n n例例例例1-41-4 估算以下程序段所代表算法的时间复杂度。估算以下程序段所代表算法的时间复杂度。n nfor(k=1;k=n;k+)for(k=1;k=n;k+)n nfor(j=1;j=k;j+)for(j=1;j=k;j+)n n x=k+j;x=k+j;n n s=s+x;s=s+x;每个赋值语句执行频率为每个赋值语句执行频率为n(n+1)/2,该算法的该算法的时间复杂度为时间复杂度为:O(n2)一个算法的运行时间，与问题的规模相关，也一个算法的运行时间，与问

22、题的规模相关，也一个算法的运行时间，与问题的规模相关，也一个算法的运行时间，与问题的规模相关，也与输入的数据相关。与输入的数据相关。与输入的数据相关。与输入的数据相关。n例如对给定的例如对给定的n n个整数个整数a(1),a(2),a(n)a(1),a(2),a(n)排序：排序：n for(i=1;i=n for(i=1;i=n 1;i+)1;i+)n for(j=i+1;j=n;j+)for(j=i+1;jaj)h=ai;ai=aj;aj=h;if(aiaj)h=ai;ai=aj;aj=h;3 3个赋值语句的执行频数之和，最理想的情形下个赋值语句的执行频数之和，最理想的情形下个赋值语句的执行

23、频数之和，最理想的情形下个赋值语句的执行频数之和，最理想的情形下为零（当所有为零（当所有为零（当所有为零（当所有n n个整数已从小到大排列时），最坏情个整数已从小到大排列时），最坏情个整数已从小到大排列时），最坏情个整数已从小到大排列时），最坏情形下为形下为形下为形下为3n(n1)/23n(n1)/2（当（当（当（当n n个整数为从大到小排列时）。个整数为从大到小排列时）。个整数为从大到小排列时）。个整数为从大到小排列时）。按平均情形来分析，其时间复杂度为按平均情形来分析，其时间复杂度为按平均情形来分析，其时间复杂度为按平均情形来分析，其时间复杂度为O(n2)O(n2)。对于一个实用算法，我们

24、通常不必深入研究它对于一个实用算法，我们通常不必深入研究它对于一个实用算法，我们通常不必深入研究它对于一个实用算法，我们通常不必深入研究它时间复杂度的上界和下界，只需要了解该算法时间复杂度的上界和下界，只需要了解该算法时间复杂度的上界和下界，只需要了解该算法时间复杂度的上界和下界，只需要了解该算法的特性，然后在合适的时候应用它。的特性，然后在合适的时候应用它。的特性，然后在合适的时候应用它。的特性，然后在合适的时候应用它。为了求解某一问题，设计出为了求解某一问题，设计出复杂性尽可能低复杂性尽可能低的算的算法是追求的重要目标。或者说，求解某一问题有多法是追求的重要目标。或者说，求解某一问题有多种

25、算法时，选择其中种算法时，选择其中复杂性最低的算法是选用算法复杂性最低的算法是选用算法的重要准则的重要准则。对算法的改进与优化，主要表现在有效缩减对算法的改进与优化，主要表现在有效缩减算法的运行时间与所占空间。算法的运行时间与所占空间。http:/ 1.2.2 1.2.2 空间复杂度空间复杂度n n一一个个程程序序运运行行所所需需的的存存储储空空间间通通常常包包括括固固定定空空间间需求与可变空间需求两部分。需求与可变空间需求两部分。1.1.固固定定空空间间需需求求包包括括程程序序代代码码、常常量量与与静静态态变变量量等所占的空间。等所占的空间。2.2.可可变变空空间间需需求求包包括括局局部部作

26、作用用域域非非静静态态变变量量所所占占用用的的空空间间、从从堆堆空空间间中中动动态态分分配配的的空空间间与与调调用用函数所需的系统栈空间等。函数所需的系统栈空间等。算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。二维或三维数组是空间复杂度高的主要因素之二维或三维数组是空间复杂度高的主要因素之二维或三维数组是空间复杂度高的主要因素之二维或三维数组是空间复杂度高的主要因素之一。在算法设计时，为降低空间复杂度，要注一。在算法设计时，为降低空间复杂度，要注一。在算法设计时，为降低空间复杂度，要注一。在算法设计时，为降低空间复杂度，要注意尽可能少用高维数组。意尽可能少用高维数组。

27、意尽可能少用高维数组。意尽可能少用高维数组。从应用的角度看，因空间所限影响算法运行的情形较为少见。因而在设计算法时，应把降低算法的时间复杂度作为首要的考虑因素。在论述某一算法时，如果其空间复杂度不高，不在论述某一算法时，如果其空间复杂度不高，不在论述某一算法时，如果其空间复杂度不高，不在论述某一算法时，如果其空间复杂度不高，不至于因所占有的内存空间而影响算法实现时，通至于因所占有的内存空间而影响算法实现时，通至于因所占有的内存空间而影响算法实现时，通至于因所占有的内存空间而影响算法实现时，通常不涉及对该算法的空间复杂度的讨论。常不涉及对该算法的空间复杂度的讨论。常不涉及对该算法的空间复杂度的讨

28、论。常不涉及对该算法的空间复杂度的讨论。1.3 算法设计与分析实例1.1.欧几里德算法的时间复杂度估算，设每次辗欧几里德算法的时间复杂度估算，设每次辗转相除的余数减半，开始时输入数转相除的余数减半，开始时输入数a,ba,b的最小值为的最小值为n=2tn=2t，则有，则有即得欧几里德算法的时间复杂度为即得欧几里德算法的时间复杂度为O(logn)O(logn)。1.3.1 求解最大公约数 2.2.应用最大公约数的定义求解应用最大公约数的定义求解应用最大公约数的定义求解应用最大公约数的定义求解 设置设置设置设置c c枚举循环，枚举循环，枚举循环，枚举循环，c c从从从从b b开始递减取值至开始递减取

29、值至开始递减取值至开始递减取值至1 1，若，若，若，若c c同同同同时是时是时是时是a a、b b的约数的约数的约数的约数(即满足即满足即满足即满足a%c=0 and b%c=0a%c=0 and b%c=0，最，最，最，最先出现的显然为最大公约数），则输出最大公先出现的显然为最大公约数），则输出最大公先出现的显然为最大公约数），则输出最大公先出现的显然为最大公约数），则输出最大公约数约数约数约数(a,b)(a,b)的结果。的结果。的结果。的结果。scanf(%ld,%ld,&a,&b);/输入整数 for(c=b;c=1;c-)/枚举循环 if(a%c=0&b%c=0)break;/定义判别

30、 printf(%ld,%ld)=%ldn,a,b,c);/输出结果。设输入数设输入数设输入数设输入数a,ba,b的最小值为的最小值为的最小值为的最小值为n n，以上按最大公约数，以上按最大公约数，以上按最大公约数，以上按最大公约数定义的枚举的平均频数或为定义的枚举的平均频数或为定义的枚举的平均频数或为定义的枚举的平均频数或为n/2,n/2,或为或为或为或为n/3n/3，其时，其时，其时，其时间复杂度为间复杂度为间复杂度为间复杂度为O(n)O(n)。3 3 复杂度比较复杂度比较复杂度比较复杂度比较 两个算法相比，显然欧几里德算法的时间复杂两个算法相比，显然欧几里德算法的时间复杂两个算法相比，显

31、然欧几里德算法的时间复杂两个算法相比，显然欧几里德算法的时间复杂度较低，即其求解效率较高。度较低，即其求解效率较高。度较低，即其求解效率较高。度较低，即其求解效率较高。注意：求解一个实际案例，算法可能有多种多样，我注意：求解一个实际案例，算法可能有多种多样，我们不必局限于某一个或某一种模式，可选择一些自己们不必局限于某一个或某一种模式，可选择一些自己所熟悉的算法进行设计。当面临的数据量规模很大时，所熟悉的算法进行设计。当面临的数据量规模很大时，选择时间复杂度低的算法是必要的。选择时间复杂度低的算法是必要的。1.1.当当n n规模较小规模较小(n13)(n13)时时 scanf(%d,&n);s

32、canf(%d,&n);/输入输入n n t=1;t=1;for(k=1;k=n;k+)for(k=1;k=n;k+)t*=k;/t*=k;/循环累乘循环累乘 printf(%d!=%ldn,n,t);/printf(%d!=%ldn,n,t);/输出输出n!n!单循环设计，时间复杂度为单循环设计，时间复杂度为O(n)O(n)，空间复杂度为，空间复杂度为O(1)O(1)。1.3.2 计算n!试精确计算n!=123n，这里正整数n从键盘输入。2.2.当当当当n n规模较大时规模较大时规模较大时规模较大时 n n规模较大，规模较大，规模较大，规模较大，n!n!的位数也就相应地大，设计的位数也就相应

33、地大，设计的位数也就相应地大，设计的位数也就相应地大，设计a a数数数数组存储组存储组存储组存储n!n!的各位数字，的各位数字，的各位数字，的各位数字，a1a1存储个位数字，存储个位数字，存储个位数字，存储个位数字，a2a2存储十位数字，余类推。存储十位数字，余类推。存储十位数字，余类推。存储十位数字，余类推。通过常用对数累加和通过常用对数累加和s=lg2+lg3+lgns=lg2+lg3+lgn确定确定n!n!的位数的位数m=s+1,m=s+1,即即a a数组元素数组元素的个数。的个数。设置设置2 2重循环，模拟整数竖式乘法实施各数组元素的累乘：重循环，模拟整数竖式乘法实施各数组元素的累乘：

34、乘数乘数k k：k=2,3,nk=2,3,n；累乘积各位累乘积各位ajaj：j=1,2,mj=1,2,m；实施乘运算：实施乘运算：t=aj*k+g;/t=aj*k+g;/第第j j位乘位乘k k，g g为进位数为进位数 aj=t%10;/aj=t%10;/乘积乘积t t的个位数字存于本元素的个位数字存于本元素 g=t/10;/g=t/10;/乘积乘积t t的十位以上数字作为进位数的十位以上数字作为进位数输出：输出：从高位从高位amam开始，逐位输出，至开始，逐位输出，至a1a1结束。结束。scanf(%d,&n);scanf(%d,&n);/输入输入输入输入n n s=0;s=0;for(k=

35、2;k=n;k+)for(k=2;k=n;k+)s+=log10(k);/s+=log10(k);/对数累加确定对数累加确定对数累加确定对数累加确定n!n!的位数的位数的位数的位数mm m=(int)s+1;m=(int)s+1;for(k=1;k=m;k+)ak=0;/for(k=1;k=m;k+)ak=0;/数组清零数组清零数组清零数组清零 a1=1;g=0;a1=1;g=0;for(k=2;k=n;k+)for(k=2;k=n;k+)for(j=1;j=m;j+)for(j=1;j=1;j-)for(j=m;j=1;j-)printf(%d,aj);/printf(%d,aj);/输出输

36、出输出输出n!n!的各位数的各位数的各位数的各位数http:/ 当当当当n n规模较大时的双循环设计，时间复杂度为规模较大时的双循环设计，时间复杂度为规模较大时的双循环设计，时间复杂度为规模较大时的双循环设计，时间复杂度为O(mn)O(mn)，空间复杂度为，空间复杂度为，空间复杂度为，空间复杂度为O(m)O(m)。显然。显然。显然。显然mnmn，把，把，把，把mm换算为换算为换算为换算为n n，注意到，注意到，注意到，注意到mm数量级平均为数量级平均为数量级平均为数量级平均为n*lgnn*lgn，因而时，因而时，因而时，因而时间复杂度为间复杂度为间复杂度为间复杂度为O(n2logn)O(n2l

37、ogn)，空间复杂度为，空间复杂度为，空间复杂度为，空间复杂度为O(nlogn)O(nlogn)。注意：注意：同样是精确求解同样是精确求解n n的阶乘的阶乘n!n!，求解范围的差异导致了，求解范围的差异导致了算法设计及其复杂性的不同。大规模算法设计及其复杂性的不同。大规模n n情形下精确求情形下精确求解，算法的时间复杂度与空间复杂度都要高于小规模解，算法的时间复杂度与空间复杂度都要高于小规模情形的算法。或者说，扩大情形的算法。或者说，扩大n!n!精确求解的范围，是以精确求解的范围，是以提高算法的时间复杂度与空间复杂度为代价的。提高算法的时间复杂度与空间复杂度为代价的。1.4 算法与程序设计计算

38、机的一切操作都是由程序控制的，离开了程序，计算机的一切操作都是由程序控制的，离开了程序，计算机将一事无成。从这个意义来说，计算机的本质计算机将一事无成。从这个意义来说，计算机的本质是程序的机器，程序是计算机的灵魂。是程序的机器，程序是计算机的灵魂。而算法是程序的核心。程序是某一算法用计而算法是程序的核心。程序是某一算法用计算机程序设计语言的具体实现。算机程序设计语言的具体实现。1.4.1 算法与程序 程序设计反映了利用计算机解决问题的全过程，程序设计反映了利用计算机解决问题的全过程，程序设计反映了利用计算机解决问题的全过程，程序设计反映了利用计算机解决问题的全过程，包括包括包括包括:建立数学模

39、型建立数学模型建立数学模型建立数学模型;数据的组织方式数据的组织方式数据的组织方式数据的组织方式;设计合适设计合适设计合适设计合适的算法的算法的算法的算法;编写程序来实现算法编写程序来实现算法编写程序来实现算法编写程序来实现算法;上机调试程序，上机调试程序，上机调试程序，上机调试程序，使之运行后能产生求解问题的结果。使之运行后能产生求解问题的结果。使之运行后能产生求解问题的结果。使之运行后能产生求解问题的结果。一个程序应包括对数据的描述与对运算操作的描述两个方面的内容。数据结构数据结构+算法算法=程序程序 数据结构是对数据的描述数据结构是对数据的描述;算法是对运算操作的描述。算法是对运算操作的

40、描述。1.4.2 1.4.2 结构化程序设计结构化程序设计 任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。所以，顺序结构、选择结构和循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的结构。结构化程序设计方法是目前国内外普遍采用的一结构化程序设计方法是目前国内外普遍采用的一结构化程序设计方法是目前国内外普遍采用的一结构化程序设计方法是目前国内外普遍采用的一种程序设计方法。种程序设计方法。种程序设计方法。种程序设计方法。结构化程序设计方法在实践中不断发展和完善，结构化程序设计方法在实践中不断发展和完善，结构化程序设计方法在实践中不断发展和完善，结构

41、化程序设计方法在实践中不断发展和完善，已成为软件开发的重要方法讨论。已成为软件开发的重要方法讨论。已成为软件开发的重要方法讨论。已成为软件开发的重要方法讨论。结构化程序设计的基本要点结构化程序设计的基本要点:n（1）自顶向下，逐步求精自顶向下，逐步求精n（2）模块化设计模块化设计n（3）结构化编码结构化编码逐步求精总是和自顶向下结合使用，将逐步求精总是和自顶向下结合使用，将问题求解逐步具体化的过程，一般把逐问题求解逐步具体化的过程，一般把逐步求精看作自顶向下设计的具体体现。步求精看作自顶向下设计的具体体现。模块化是结构化程序设计的重要原则。模块化是结构化程序设计的重要原则。模块化是结构化程序设

42、计的重要原则。模块化是结构化程序设计的重要原则。一个程序是由一个主控模块和若干子模块组成。一个程序是由一个主控模块和若干子模块组成。一个程序是由一个主控模块和若干子模块组成。一个程序是由一个主控模块和若干子模块组成。主控模块用来完成某些公用操作及功能选择主控模块用来完成某些公用操作及功能选择主控模块用来完成某些公用操作及功能选择主控模块用来完成某些公用操作及功能选择;而子模块用来完成某项特定的功能。而子模块用来完成某项特定的功能。而子模块用来完成某项特定的功能。而子模块用来完成某项特定的功能。n n例1-9 把欧几里德算法设计成子模块，通过主模块调用实现求n个整数的最大公约数。n n /实现欧

43、几里德算法的函数实现欧几里德算法的函数gcd(a,b)gcd(a,b)n n /求求n n个整数的最大公约数个整数的最大公约数,n-1,n-1次调用次调用gcd(a,b)gcd(a,b)第第1 1章作业章作业习题习题习题习题1:1,3,4,61:1,3,4,61:1,3,4,61:1,3,4,6 第第1 1章上机章上机 (VC+6.0)(VC+6.0)上机通过上机通过上机通过上机通过1.3.1,1.3.21.3.1,1.3.21.3.1,1.3.21.3.1,1.3.2；上机通过习题上机通过习题上机通过习题上机通过习题 1-7:1-7:1-7:1-7:输出输出输出输出n=15,n=21n=15

44、,n=21n=15,n=21n=15,n=21的对称方阵的对称方阵的对称方阵的对称方阵;上机通过上机通过上机通过上机通过 1.3.3 1.3.3 1.3.3 1.3.3，输出能被，输出能被，输出能被，输出能被2011201120112011、2017201720172017整除的整除的整除的整除的n.n.n.n.小组讨论：小组讨论：小组讨论：小组讨论：1.31.31.31.3三例算法的时间复杂度。三例算法的时间复杂度。三例算法的时间复杂度。三例算法的时间复杂度。参见附录参见附录A A 在在VC+6.0VC+6.0环境环境下运行下运行C C程序方法简介程序方法简介 欢迎大家提出教学建议欢迎大家提出教学建议返回返回