内容发布更新时间 : 2024/12/23 13:01:36星期一 下面是文章的全部内容请认真阅读。
返回操作系统。
(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。
(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。
1.7 在程序设计中，可采用下列三种方法实现输出和输入： (1) 通过scanf和printf语句； (2) 通过函数的参数显式传递； (3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。
解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。
(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。
(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：
(1) i=1; k=0; while(i<=n-1){ @ k += 10*i;
i++; }
(2) i=1; k=0; do {
@ k += 10*i; i++; } while(i<=n-1); (3) i=1; k=0; while (i<=n-1) { i++; @ k += 10*i; } (4) k=0;
for(i=1; i<=n; i++) { for(j=i; j<=n; j++) @ k++; }
(5) for(i=1; i<=n; i++) { for(j=1; j<=i; j++) { for(k=1; k<=j; k++) @ x += delta; }
(6) i=1; j=0; while(i+j<=n) { @ if(i>j) j++; else i++; }
(7) x=n; y=0; // n是不小于1的常数 while(x>=(y+1)*(y+1)) { @ y++; }
(8) x=91; y=100; while(y>0) {
@ if(x>100) { x -= 10; y--; } else x++; } 解：(1) n-1 (2) n-1 (3) n-1
(4) n+(n-1)+(n-2)+...+1=
n(n?1) 2n (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=?i?1i(i?1) 21n1n21n21n =?i(i?1)??(i?i)??i??i
2i?12i?12i?12i?1 =
111n(n?1)(2n?1)?n(n?1)?n(n?1)(2n?3) 12412
(6) n
(7) ?n? 向下取整 (8) 1100
1.9 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。 int Time(int n) {
count = 0; x=2; while(x return count; } 解：o(log2n) count=log2n?2 1.11 已知有实现同一功能的两个算法，其时间复杂度分别为O?2n?和 On10，假设现实计算机可连续运算的时间为107秒（100多天），又每 x *= 2; count++; ??秒可执行基本操作（根据这些操作来估算算法时间复杂度）105次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。 解：2n?1012 n=40 n=16 n10?1012 则对于同样的循环次数n，在这个规模下，第二种算法所花费的 代价要大得多。故在这个规模下，第一种算法更适宜。 1.12 设有以下三个函数： f?n??21n4?n2?1000，g?n??15n4?500n3，h?n??500n3.5?nlogn 请判断以下断言正确与否： (1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n3.5) (5) h(n)是O(nlogn) 解：(1)对 (2)错 (3)错 (4)对 (5)错 1.13 试设定若干n值，比较两函数n2和50nlog2n的增长趋势，并确定n在什么范围内，函数n2的值大于50nlog2n的值。 解：n2的增长趋势快。但在n较小的时候，50nlog2n的值较大。 当n>438时，n2?50nlog2n 1.14 判断下列各对函数f?n?和g?n?，当n??时，哪个函数增长更快？ (1) f?n??10n2?lnn!?10n，g?n??2n4?n?7 3??(2) f?n???ln?n!??5?2，g?n??13n2.5 (3) f?n??n2.1?n4?1，g?n???ln?n!??2?n (4) f?n??2?n???2n?，g?n??n?n??n5 322解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明： (1) ?i2?n?n?1??2n?1?/6 i?1n?n?0?