第一章作业(上交).doc

3 什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。解答：算法：为解决某一特定任务而规定的一个指令序列。算法的特性：（1） 有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。（2）有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。（3）确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。（4）有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。（5）有效性。算法中每一条运算都必须是足够基本的。就是说，它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。算法和程序不同，程序可以不满足上述的特性(4)。例如，一个操作系统在用户未使用前一直处于等待的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。此外，算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。4 指出下列各算法的功能并求出时间复杂度。31int Prime (int n) int i = 2; int x= (int) sqrt (n); while (i x) return 1; else return 0;解：功能：判断一个数是否为素数，若是，返回1；否则，返回0.时间复杂度：O(n1/2)(即：根号n)2int fun (int n) int i=1, s=1; while(s =n的最小i值。时间复杂度：O(n1/2)(即：根号n)3void UseFile(ifstream& inp, int c10) for(int i=0; i x) i=x%10; ci +; 解：时间复杂度：O(n)4void matable (int n) for(int i=1; i=n; i+) for(int j =i; j =n; j +) cout i* j = setw(2) i* j ; cout endl; 解：功能：打印出n行乘法表，第i行有n-i+1项乘积。 时间复杂度：O(n2)5void cmatrix(int aM N, int d) for(int i=0; iM; i+) for(int j =0; jN; j+) ai j* =d;功能：使数组aMN中每个元素的值都乘以d的值。时间复杂度：O(M*N)6void matrimult(int aM N, int bN L, int cM L) int i, j, k; for(i = 0; i M; i + ) for(j =0; j L; j +) cij =0; for(i = 0; i M; i + ) for(j =0; j L; j +) for(k= 0; k N; k+ ) cij +=aik *bkj;功能：矩阵相乘，即aMN*bNL = CML时间复杂度: O(M*N*L)7i=1;while(i=n) i=i*3; 解释：i是这样变化的：1， 3, 9, 27, . 如果用i(x)表示第x次循环时i的值，则 i(x) = 3x , x初始值为0。 循环在 i = n 的时候停止，即 i（x) = 3 x x= log3(n) 即循环结束时，最多进行了log3(n)次运算。按照大O表示法定义，它的复杂度为 O(log3(n), 即 O(lgn/lg3)8n是描述问题规模的非负整数，给出下面程序段的时间复杂度。（2011年考研计算机专业真题）x=2;while(x=n/2) x=x*2;功能：求小于n/2的最大的2的幂次方时间复杂度：O(n) = n 9while( in) for (j=1; j=n; j+) s=s+aij; i=i*2; 10n是3的倍数。for(i=1;i=n;i+) if(3*i=n)for(j=3*i;j=n;j+) y+=i*j; 11设n是偶数，运行下面的程序段后计算语句m=m+1的次数，并给出该程序段的时间复杂度。m=0;for(i=1; i=n; i+) for(j=2*i; j=0)阶乘的算法如下