计算机操作统第三章 1.ppt

第三章 第三章 算法基本工具和优化技巧 利用算法的基本机制——循环和递归设计算法 利用算法的基本操作提高算法效率的技巧 利用数组提高算法质量 建立高效的数学模型 3．1 循环与递归 3．3 算法优化基本技巧 3．2 算法与数据结构 3．4 优化算法的数学模型 3．1 循环与递归 【例1】求1/1!-1/3!+1/5!-1/7!+…+（-1）n+1/(2n-1)!分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。数学模型1：Sn=Sn-1+（-1）n+1/(2n-1)!算法设计1：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为： S=S+（-1）n+1/(2n-1)!需要用二重循环来完成算法，算法1如下： 算法如下： 数学模型2：Sn=Sn-1+（-1）n+1An； An=An-1 *1/((2*n-2)*(2*n-1)) 算法说明2：构造循环不变式时，一定要注意循环变量的意义，如当i不是项数序号时（右边的循环中）有关t的累乘式与i是项数序号时就不能相同。算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O（n）。 2．“自顶向下”的设计方法  自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的过程。  【例2】编算法找出1000以内所有完数 例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28 it’s factors are 1，2，4，7，14。 算法如下： 【例3】求一个矩阵的鞍点 (即在行上最小而在列上最大的点)。 算法设计： 算法如下： 3．由具体到抽象设计循环结构 3．1．2 递归设计要点 递归的关键在于找出递归方程式和递归条件。 两个经典的递归例题： 【例1】汉诺塔问题 【例2】整数的分划问题 【例1】汉诺塔问题描述： 算法设计： 2 算法如下： 【例2】整数的分划问题 模型建立： 算法如下： 3．1．3 递归与循环的比较 下面通过几个具体的例子来说明循环和递归的差异和优劣。【例1】任给十进制的正整数，请从低位到高位逐位输出各位数字。循环算法设计：从题目中我们并不能获知正整数的位数，再看题目的要求，算法应该从低位到高位逐位求出各位数字并输出。详细设计如下：1）? 求个位数字的算式为 n mod 102）? 为了保证循环体为“不变式”，求十位数字的算式仍旧为n mod 10，这就要通过算式n=n\10，将n的十位数变成个位数。 【例3】找出n个自然数(1,2,3,…,n)中r个数的组合。 算法设计1： 算法1如下： 则递归算法的三个步骤为： 递归算法如下： hanoi (int n,char a,char b,char c) / a,b,c 初值为”A”,”B”,”C”/ 1) if(n0) /*0阶的汉诺塔问题当作停止条件*/ 2) hanoi(n-1,a,c,b); 3) 输出 “ Move dise” ,n.”from pile”,a,” to”b); 4) haboi(n-1,c,b,a); 5) endif } 拼牡测貌知着荡充硫敢捡匠灾兔嵌删盏乞痰昌辙焰谰钉设拨句倾揖晃汁卿计算机操作系统第三章 1计算机操作系统第三章 1 对于一个正整数n的分划就是把n写成一系列正整数之和的表达式。例如，对于正整数n=6，它可以分划为： 6 ?5+1 ?4+2, ? 4+1+1 ?3+3, ? 3+2+1, ?3+1+1+1 ?2+2+2, ?2+2+1+1, ?2+1+1+1+1 ?1+1+1+1+1+1 根据例子发现“包括第一行以后的数据不超过6，包括第二行的数据不超过5，……，第六行的数据不超过1”。 因此，定义一个函数Q(n,m)，表示整数n的“任何被加数都不超过m”的分划的数目 。 橱懈针玖信假魏赡伪昧咒镣饺鹰螟渺嘶拌苛湛辜世潍童束鬼审兔美匝跃音计算机操作系统第三章 1计算机操作系统第三章 1 一般地Q(n.m)有以下递归关系： 1)Q(n,n)=1+Q(n,n-1) （m=n） Q(n,n-1)表示n的所有其他分划，即最大被加数m=n-1的划分。 2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn) Q(n,m-1)表示被加数中不包含m的分划的数目； Q(n-m,m)表示被加数中包含