第1章绪论
布置的作业共6题：
基础知识题：1.6 1.7 1.8 1.10
算法设计题：1.17 1.20
一、基础知识题
◆1.6 ③在程序设计中，常用下列三种不同的出错处理方式：
（1）用exit语句终止执行并报告错误；
（2）以函数的返回值区别正确返回或错误返回；
（3）设置一个整型变量的函数参数以区别正确返回或某种错误返回。
试讨论这三种方法各自的优缺点。
]
答题思路：查错和容错能力
答：程序出错处理是指发现错误并根据出错的原因作出适当的处理，处理的目的是找到出错的原因。
出错的原因一般包括缺乏某些资源和程序设计有问题两类。
如果是前者，程序仍然可以继续运行，只是处于等待资源或执行其他流程的状态。
如果是后者，则需要修改源代码。
◆1.7 ③在程序设计中，可采用下列三种方法实现输出和输入：
（1）通过scanf和printf语句；
（2）通过函数的参数显式传递；
（3）通过全局变量隐式传递。
试讨论这三种方法的优缺点。
答题思路：错误局部化（软件模块化）、执行效率（内存开销）
答：在正规的软件设计中，要求各模块之间以恰当的方式进行调用，以便使各模块中出现的错误局部化。
其是方式3，在出现错误时查错的开销将很大，尽量不使用。
◆1.8 ④设n为正整数，试确定下列各程序段中前置以记号@的语句的频度。
评析：频度≠时间复杂度
注意：（1）、（2）、（3）三个程序段中任何两段都不等效(即k和i的终值不相同
)
书后附有答案
标答：程序段（8）取自著名的McCarthy91函数
⎩
⎨⎧≤+>-=100
))1((10010)(x x M M x x x M 对任何 x ≤100，M(x)=91。
此程序实质上是一个双重循环，对每个y(>0)值，@语句执行11次，其中10次是执行x++。
刘解：请注意x 的初值已经是91了，必须加到101才能终止程序的循环。
if 语句从x=91开始直到x=101都执行，共执行11次，其中10次是执行x++。
1.10 ②按增长率由小至大的顺序排列下列各函数：
2100,（2/3）n，（3/2）n，（4/3）n，n n，n2/3，n3/2，n，n!，n，log2n，n/ log2n，log22n，log2(log2n )，n log2n，n log2n。
解：按规律：
则可以先迅速粗分类，然后再用求比值极限的方法来确定大小？
【2100, log2(log2n )，log2n，log22n，n，n，n log2n，】
【n2/3，n3/2，n!，n/ log2n，n log2n】
【（2/3）n，（4/3）n，（3/2）n，n n】
正确顺序为：【（2/3）n，2100, log2(log2n )，log2n，log22n，n，n2/3，n/ log2n，n，n log2n】
【n3/2，（4/3）n，(3/2)n，n log2n，n!，n n】
二、算法设计题（1.17， 1.20）
评析：算法复杂度的考虑
◆ 1.17 ③已知k阶裴波那契序列的定义为：
f0=0, f1=0, …, f k-2=0, f k-1=1;
f n=f n-1+ f n-2+……+ f n-k，n=k, k+1,……
试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
解：该题答案思路见习题集P181。
在编写此题的函数的过程中，首先应根据参量m和k区分下列4种情况：
1）m<0;—————————非法
2）0≤m<k-1; ——————0
3）m=k-1；————————1
4）m≥k。
————————需要计算
其次，在计算m≥k的f m值时，可先对计算公式作数学处理，将f i+1表示为f i和f i-k的简单函数，最后考虑计算f n所需的辅助空间。
参考程序：
Status fib(int k, int m, int &f) //求k阶斐波那契序列的第m项的值f
{
int temp; // 开辟一维向量存放每个f值。
if(k<2||m<0) return ERROR; // k<2（即k≥2时才有意义）或m<0时属于非法越界
if(m<k-1) f=0;
else if (m= =k-1 || m= =k) f=1;
else
{
for(i=0;i<=k-2;i++) temp[i]=0;
temp[k-1]=1; temp[k]=1; //初始化,前面分量对应的f值为0，而后面开始有累加
sum=1;
j=0;
for(i=k+1; i<=m; i++, j++) //求出序列第k至第m个元素的值
temp[i]=2*sum-temp[j];//此公式怎么来的？见下面分析推导。
f=temp[m];
}
return OK;
}//fib
分析: k阶斐波那契序列的第m项的值
f[m]=f[m-1]+f[m-2]+...... + f[m-(k-1)] + f[m-k]
=f[m-1]+f[m-2]+......+ f[m-(k-1)] + f[m-k] + f[m-k-1]-f[m-k-1]
=2*f[m-1]-f[m-k-1]
所以上述算法的时间复杂度仅为O(m)。
如果采用递归设计，将达到O(k m)。
即使采用暂存中间结果的方法，也将达到O(m2)。
◆1.20 ④ 试编写算法求一元多项式∑==
n
i i
i n x
a x P 0
)(的值P n (x 0)，并确定算法中每一语句的执
行次数和整个算法的时间复杂度。
注意选择你认为较好的输入和输出方法。
本题的输入为a i (i=0, 1, … , n), x 0和n, 输出为P n (x 0)。
解： 答案思路见习题集P182。
注意计算过程中，不要对多项式中的每一项独立计算x 的幂。
网上参考程序如下（请自行核实是否正确）
void polyvalue() {
float temp; //temp 用来装从键盘输入的每一个临时a i ； float *p=a ;
printf("Input number of terms:");
scanf("%d", &n); //先输入入参：项数n printf("Input value of x:");
scanf("%f",&x); //再输入入参：x
printf("Input the %d coefficients from a0 to a %d: \n ",n+1,n); p=a; xp=1; sum=0; //xp 用于存放x 的i 次方 for(i=0;i<=n; i++) {
scanf("%f",&temp); //最后输入a i (i=0, 1, … , n) sum+=xp*(temp); // sum= sum+xp*(temp) xp*=x; }
printf("Value is:%f",sum); }//polyvalue
刘注：此题肯定需要编程技巧，原则是尽量利用前面的计算结果。