算法，还是算法，不过这章的算法里面，我们加入了数据结构的体验。
本章两个案例：一个面试的案例，另外一个还是面试的案例。
只不过，第一个是别人面试的案例，我在整理本书的时候发现，把他编写了进来。
第二个，确确实实是我自己面试碰到的案例，当我用英语简单的说出了这个算法之后，成功通过了面试。并感概良多。
好了，我们具体来谈这两个案例吧，每个案例的解答有三种答案，代表了三种境界，我给他们取了一个名字：
一个合格学生的解答；
一个优秀学生的解答；
一个工程师的解答。
第一个题目是：
（1） 写一个函数计算当参数为n(n很大)时的值 1-2+3-4+5-6+7......+n
看起来相当的简单吧。
一个合格学生的解答
一般说来，任何一个C语言基础还不错的学生会做出来：
long fn(long n)
{
long temp=0;
int i,flag=1;
if(n<=0)
{
printf("error: n must > 0);
exit(1);
}
for(i=1;i<=n;i++)
{
temp=temp+flag*i;
flag=(-1)*flag;
}
return temp;
}
确实，这个程序执行结果肯定是没有问题！但当n很大的时候我这个程序执行效率很低， 还记得我们前面讲算法的案例吗？会浪费很多的时间的啊。在嵌入式系统的开发中，程序的运行效率很重要，能让CPU少执行一条指令都是好的。
一个优秀学生的解答
让我们看看，一个优秀学生，为了更好的节约计算资源，而给出的答案。
long fn(long n)
{
long temp=0;
int j=1,i=1,flag=1;
if(n<=0)
{
printf("error: n must > 0);
exit(1);
}
while(j<=n)
{
temp=temp+i;
i=-i;
i>0?i++:i--;
j++;
}
return temp;
}
比起上一个程序，这个程序将所有涉及到乘法指令的语句改为执行加法指令，既达到要题目的要求而且运算时间上缩短了很多！而代价仅仅是增加了一个整型变量！
一个工程师的解答
不错，第二个程序确实在效率上有的很大的提高！但是，你知道一个合格的工程师有更加严格的要求，我们看看工程师的答案吧：
long fn(long n)
{
if(n<=0)
{
printf("error: n must > 0);
exit(1);
}
if(0==n%2)
return (n/2)*(-1);
else
return (n/2)*(-1)+n;
}
对比一下，在n越来越大的时候这三个程序运行时间的差别简直是天壤之别！
但如果你数论学得好，了解这个算法，直接就可以写出第三个答案来。
第二个题目：
在一个很小的内存空间里面，将北京某电话局的8位电话号码排序。号码在一万个以内。
合格学生的答案：
在硬盘中找一个缓存空间，讲一万个号码一一读入，先比较第一位，然后比较第二位……用一个排序算法。
优秀学生的答案：
将电话号码由字符串转化为自然数，比如88180675，转化后，存储空间，由8位字节，变成了2个字节，大大降低了存储空间，然后排序。
工程师的答案：
在内存中开辟一个顺序存储空间，第一个字节的第一位(bit)表示：10000000，第二位(bit)表示10000001……，直到99999999，组成一个向量。然后将所有“bit”置零，开始读电话号码，有一个电话号码，就把相应的位置改为“1”，当电话号码读完的时候，在这个bit向量上，就自然把所有的电话号码排序了。
一个电话号码，8个字节，对应程序中一个bit，空间减少了64倍，更关键的是，排序代码变得无比简洁和简单。
感谢我过去的经历，我用ucOS/-II开发过程序，这个系统的优先级管理就是用的这个原理。当我面试碰到这个问题的时候，举一反三，显得非常简单。
这个案例，我一直觉得是体现算法和数据结构的魅力的最好案例。你掌握了吗？
好了，今天的作业题目是：
用一个函数实现两个函数的功能。
fn1(n)=n/2!+n/3!+n/4!+n/5!+n/6!
fn2(n)=n/5!+n/6!+n/7!+n/8!+n/9!
现在用一个函数fn(int n,int flag)实现，当flag为0时，实现fn1功能，如果flag为1时
实现fn2功能！
提示：空间换时间的算法
答案：
定义一个二维数组 float t[2][5]存入{{2!,3!,4!,5!,6!},{5!,6!,7!,8!,9!}}然后给出一个循环：
for(i=0;i<6;i++)
{
temp=temp+n/t[flag];
}
评论