(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=
(5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= = = (6) n
(7) 向下取整 (8) 1100
1.9 假设n为2的乘幂 并且n>2
试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）
int Time(int n) {
count = 0; x=2; while(x x *= 2; count++; } return count; } 解： count= 1.11 已知有实现同一功能的两个算法 其时间复杂度分别为和 假设现实计算机可连续运算的时间为秒（100多天） 又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）次 试问在此条件下 这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由 解： n=40 n=16 则对于同样的循环次数n 在这个规模下 第二种算法所花费的代价要大得多 故在这个规模下 第一种算法更适宜 1.12 设有以下三个函数： 请判断以下断言正确与否： (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值 比较两函数和的增长趋势 并确定n在什么范围内 函数的值大于的值 解：的增长趋势快 但在n较小的时候 的值较大 当n>438时 1.14 判断下列各对函数和 当时 哪个函数增长更快？ (1) (2) (3) (4) 解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明： (1) (2) (3) (4) 1.16 试写一算法 自大至小依次输出顺序读入的三个整数X Y和Z的值 解： int max3(int x int y int z) { if(x>y) if(x>z) return x; else return z; else if(y>z) return y; else return z; } 1.17 已知k阶斐波那契序列的定义为 ... ； 试编写求k阶斐波那契序列的第m项值的函数算法 k和m均以值调用的形式在函数参数表中出现 解：k>0为阶数 n为数列的第n项 int Fibonacci(int k int n) { if(k<1) exit(OVERFLOW); int *p x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i j;