《自顶向下细化算法及流程图》由会员分享，可在线阅读，更多相关《自顶向下细化算法及流程图（25页珍藏版）》请在金锄头文库上搜索。
1、算法设计及流程图,王 璐 中原工学院计算机学院 2012-10,“自顶向下”的设计方法,自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的过程。【例】编算法找出1000以内所有完数找出1000之内的所有完数，并按下面格式输出其因子：28 its factors are 1，2，4，7，14。,理解问题：例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。这里不是要质因数，所以找到因数后也无需将其从数据中“除掉”。每个因数只记一次，如8的因数为1，2，4而不是1，2，2，2，4。（注：本题限定因数不包括这个数本身）,流程图分
2、析（1）,开始,依次测试每个数是否为完数,输入待测试数的范围 n=1000,按格式输出完数,结束,测试第i个数是否为完数,令i=1（从第一个数开始）,i=n,N,Y,流程图分析（2）,从1到i-1测试是否i的因子,如果是，求和,若和等于i，则是完数,令j=1,j能否整除i,记录j，计算和值sum,ji?,j+,Y,N,Y,sum=i?,Y,是完数,for(i=1;i=n;i+),从流程图到代码,void main() ,开始,输入待测试数的范围n=1000,结束,令j=1,j能否整除i,记录j,计算和值sum,ji?,j+,Y,N,Y,N,sum=i?,Y,令i=1（从第一个数开始）,按格式输
3、出完数i,i=n,N,Y,N,i+,for(j=1;ji;j+),if(i%j)=0) ,1）顶层算法 for(i=2;i=n;i+) 判断i是否是“完数”； 是完数则按格式输出； ,2）判断是否是”完数” 的算法 for(j=2;ji;j+) 找i的因子，并累加； 如果累加值等于i,i是完数,伪代码（语言）分析（1）,3）进一步细化判断i是否“完数”算法,s=1 for(j=2;ji;j=j+1)if (i%j=0) (j是i的因素) s=s+j; if （s=i） i是“完数”;,伪代码（语言）分析（2）,4）考虑输出格式判断i是否“完数”算法考虑到要按格式输出结果，应该开辟数组存储数据i
4、的所有因子，并记录其因子的个数，因此算法细化如下：,定义数组a，s=1; k=0; for(j=2;ji;j=j+1)if (i%j=0) (j是i的因素) s=s+j; ak=j;k=k+1; if （s=i） 按格式输出结果,伪代码（语言）分析（3）,代码如下：,main( ) int i,k,j,sum,a20;for(i=1;i=1000;i+) sum=1; /*两个赋初值语句s=1,k=0k=0; 一定要位于外部循环的内部*/for(j=2;ji;j+)if (i%j)=0)sum=sum+j; ak=j; k+;if(i=sum) printf(“%d its factors a
5、re : 1”,i);for(j=0; jk; j+)printf(“, %d”,aj);,作业,画出以下问题的算法流程图，然后根据流程图写出代码 （1）为加强居民节水意识，某市制定了以下生活用水收费标准：每户每月用水未超过7m3时，每立方米收费1.0元，并加收0.2元的城市污水处理费；超过7m3的部分，每立方米收费1.5元，并加收0.4元的城市污水处理费。请你写出某户居民每月应缴纳的水费y(元)与用水量x(m3)之间的函数关系，然后设计一个求该函数值的算法，画出程序框图。,作业,（2）Gold Bar银行收到可靠消息：在前次的N个金币中有一枚重量不同的假金币（其它金币的重量都相同）。经济危机
6、之后他们只有一台天平可用。用这台天平，可以称量出左边托盘中的物体是轻于、重于或等于右边托盘的物体。为了分辨出假金币，银行职员将所有的金币编为1-N号。然后用天平称量不同的金币组合，每次仔细记载称量金币的编号和结果。 输入： 第一行输入两个空格隔开的整数N和K，N是金币的总数（2N1000），K是称量的次数（1N100）。随后的2K行记录称量的情况和结果，连续两行记录一次称量：第一行首先是Pi(1PiN/2)，表示两边托盘中放置的金币数目，随后是左边托盘中Pi个金币编号和右边托盘中Pi个金币编号，所有的数之间都由空格隔开；第2行用、=记录称量结果。 输出： 输出假金币的编号。如果根据称量记录无法
7、确定假金币，输出0。 输入样例： 5 3 2 1 2 3 4 1 1 4 = 1 2 5 = 输出样例： 3,算法复杂度分析示例,【例】求1/1!-1/3!+1/5!-1/7!+（-1）n+1/(2n-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如下：,算法如下：,m
8、ain( ) int i,n,j,sign=1;float s,t=1;/s存储最终的结果，t存储(2k-1)的阶乘input(n);/输入ns=1；for(i=2;i=n;i=i+1)t=1; 求阶乘for(j=1;j=2*i-1;j=j+1)t=t*j;sign =1;求（-1）n+1 for(j=1;j=i+1;j=j+1)sign = sign *(-1);s=s+ sign/t; print(“Snm=”,s);,算法分析：以上算法是二重循环来完成 ，但算法的效率却太低是O（n2）。其原因是，当前一次循环已求出7！，当这次要想求9！时，没必要再从1去累乘到9，只需要充分利用前一次的结
9、果，用7！*8*9即可得到9！，模型为An=An-1*1/(2*n-2)*(2*n-1)。另外运算sign = sign *(-1);总共也要进行n*(n-1)/2次乘法，这也是没有必要的。下面我们就进行改进。,数学模型2：Sn=Sn-1+（-1）n+1An； An=An-1 *1/(2*n-2)*(2*n-1),main( ) int i,n, sign;float s,t=1;input(n); s=1； sign=1; for(i=2;i=n;i=i+1) 或 for(i=1;i=n-1;i=i+1)sign=-sign; sign=-sign; t= t*(2*i-2)*(2*i-1)
10、; t= t*2*i*(2*i+1); s=s+ sign/t; s=s+ sign/t; print(“Sum=”,s); ,算法说明2： 构造循环不变式时，一定要注意循环变量的意义，如当i不是项数序号时（右边的循环中）有关t的累乘式与i是项数序号时就不能相同。 算法分析：按照数学模型2，只需一重循环就能解决问题 算法的时间复杂性为O（n）。,【例】狱吏问题某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这
11、样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的？,算法设计1： 1）用n个空间的一维数组an,每个元素记录一个锁的状态，1为被锁上，0为被打开。 2）用数学运算方便模拟开关锁的技巧，对i号锁的一次开关锁可以转化为算术运算：ai=1-ai。 3）第一次转动的是1，2，3，n号牢房；第二次转动的是2，4，6，号牢房；第三次转动的是3，6，9，号牢房；第i次转动的是i，2i，3i，4i，号牢房，是起点为i，公差为i的等差数列。4）不做其它的优
12、化，用蛮力法通过循环模拟狱吏的开关锁过程，最后当第i号牢房对应的数组元素ai为0时，该牢房的囚犯得到大赦。算法1如下：,void main( ) int *a,i,j,n;input(n);a=calloc(n+1,sizeof(int);for (i=1; i=n;i+)ai=1;for (i=2; i=n;i+)for (j=i; j=n;j=j+i)ai=1-ai;for (i=1; i=n;i+)if (ai=0) print(i,”is free.”); ,算法分析：以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+1/n)=O(nlogn)。,问题分析：转动门锁的规则可以
13、有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)有的为奇数，有的为偶数，见下表:表 编号与因数个数的关系n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1i之间的不
14、重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。,算法设计2: 1）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。 2）一个数的因子是没有规律的，只能从1n枚举尝试。算法2如下： main2( ) int s,i,j,n;input(n);for (i=1; i=n;i+) s=1;for (j=2; j=i;j=j+)if （i mod j=0） s=s+1;if （s mod 2 =1） print(i,”is free.”); ,算法分析：狱吏开关锁的主要操作是ai=1- ai;共执行了n*(1+1/2+1/3+1/n)次，时间近似为复
15、杂度为O（n log n）。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断i mod j是否为0，共执行了n*(1+2+3+n)次，时间复杂度为O（n2）。数学模型2：仔细观察表4-3，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且ab时，必有两个因子a，b; 只有n为完全平方数，也即当n=a2时, 才会出现d(n)为奇数的情形。 算法设计3：这时只需要找出小于n的平方数即可。算法3如下：,main3( ) int s,i,j,n;input(n); for (i=1;i=n;i+) if（i*i=n） print(i,”is free.”);else break;由此算法我们应当注意：在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。,
