• 好好学习,天天向上~
  • 欢迎欢迎~

C语言面试题详解第14节

c语言 lcc 121℃ 0评论

有句古话叫“隔行如隔山”,在有些外行人看来,编写程序是一项非常有技术含量的工作,甚至还有些“科幻”色彩。其实没那么夸张,程序员编写程序其实只是为了控制计算机替人类工作而已。区分程序员技术水平的方法,就是看他编写的程序是否能够使用更小的开销,以更高的效率完成工作。

提升程序工作效率

就像中国老板指挥他的美国员工工作,要用英语,指示法国员工则要说法语一样,程序员若想指挥计算机替自己工作,得使用计算机语言,也就是所谓的编程语言(C语言只是其中一种),这么看来,编程语言只是一门沟通工具而已。

只不过,编程语言非常注重逻辑,绝对不能引发歧义,因为计算机非常死板,它不能“随机应变”,出现意料之外的情况就会罢工。也就是说,若希望计算机能够替人类处理事务,必须要把事务所有的可能发展方向都考虑清楚,然后通过编程语言告诉计算机:若发生情况 a 该如何处理,若发生情况 b 该如何处理…

可以看出,计算机只会严格按照程序员事先设定好的程序处理工作,它处理问题的效率取决于程序员告诉它的方法,而完成工作的方法常常不止一种,各种方法之间的开销以及效率差异也往往比较大,因此优秀的C语言程序员应该尽力找到开销小,但是处理效率高的方法,并编写出相关C语言代码。

现在设想这种情况:小明在一个陌生城市旅游,想去C语言乐园,但是不知道路,于是就向当地人 A 和当地人 B 问路。A 说可以先走到街尾,右转再左转找到商店,买一份地图,然后就知道怎么去C语言乐园了。B 说直接从这个巷子过去,走几步就到C语言乐园了。

现在将小明看作是计算机, A 和 B 是两个程序员,AB 要处理的任务是:指导小明到达C语言乐园。AB提供的方案(编写的程序)都能完成任务,不过 B 的方案显然更好,因为按照这个方案小明能够走更少的路(开销小),更快的到达C语言乐园(效率高)。B 之所以能够提供更优方案,是因为他对城市(编程环境)了解的更深,并能在此基础上找到最优路径。

从上面的案例可以看出,程序员若想编写出开销低,效率高的程序,首先要非常了解自己使用的编程语言,也就是基本功一定要扎实。事实上,本专栏前面13节讨论的都属于C语言的基础知识,正是希望能够帮助读者巩固基本功。

在充分了解自己的编程环境后,还需要有较清晰的头脑找到“通往C语言乐园的最优路径”,这在编程中一般被称为“设计出优秀的算法”。如果 B 是个糊涂蛋,就算他对城市非常了解,也有可能给小明指出一条更远的路。不过这不太容易发生在程序员身上,基础扎实的程序员,设计优秀算法的能力也不会差。

总结一下,程序员若想写出开销小、执行效率高的程序,既要充分了解自己的开发工具,也要具备设计优秀算法的能力

什么是算法?

上文提到了“算法”这个词,那什么是算法呢?按照百度百科的解释,算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。

这样的定义有些书本化,姑且把百科这个解释先放到一边。简单理解,算法就是解决问题的方法,是将一组输入转化成一组输出的一系列计算步骤,只不过每一个计算步骤都要能在有限时间内完成。应注意,算法是解决一类问题的,因此只解决特定问题就谈算法没有意义。例如,要求对数组 a 排序

int a[] = {3, 2, 4, 1};

若某程序员写出如下C语言代码:

void sort()
{
    a[0] = 1;
    a[1] = 2;
    a[2] = 3;
    a[3] = 4;
}

这的确能够解决数组 a 的排序问题,但是如果换个数组,sort() 函数可能就无法完成任务了。真正的数组排序算法,应该能够处理任意一组数据,并且都能得到正确结果。

正确的算法自不必说了,算法出错有两种情况:一是得到了错误的结果,再就是算法无法在有限时间内完成,而是会持续计算下去。

某个算法就算输出了错误结果,但是只要错误率可控,仍然是有用的。例如,现代科学中计算机处理各种复杂的数学方程式,很多情况下都难以在短时间内得到精确解,甚至根本就无法得到精确解,这种情况下,若是能得到误差允许内的解也是可以的。

前面提到,绝大多数情况下,解决一个问题的算法都不止一种,程序员应尽力设计出开销小,执行效率高的算法。在求职面试中,招聘公司一般都会出算法题,考察最多的就是数组排序问题。也许这些招聘公司认为:算法更多是考察程序员的思维能力,若能设计出解决 X 问题的优秀算法,设计出解决其他问题的算法也不在话下。

来看看这个面试题

下面这道题目出自中国某视频监控公司的笔试题:

利用C语言编写程序,对数组排序。(使用你最常使用的几种排序方法,并对比它们的效率。)

这显然是一道算法题。

对于少量元素的排序,插入排序法是一个有效的算法。插入排序就像我们玩扑克牌一样,拿到一张牌后,我们从右往左(或从左往右)将它与已在手中的每张牌做比较,以此决定它的插入位置。

就像图中拿到一张梅花7,发现它比 10 小,继续往左看,发现它比 5 大,所以把它插在 5 和 10 之间。为什么不继续比较左边的 4 和 2 呢?这是因为之前的牌已经是排好序的。把 7 插入以后,一手牌又是排好序的了,下次接到牌可以继续按照这个方法决定插入位置。

使用 C 语言编程对数组进行插入排序也是一样的道理,只不过数组的两个元素之间不能插入,只能将插入点之后的元素往后移动一个单元。现在思路清晰了,只需要使用C语言把算法描述给计算机就可以了,请看如下代码:

#include <stdio.h>

void insertion_sort(int* a)
{
    int i = 0, j = 0;
    int cur = 0;    /** 要比较的值 */
    for (j = 1; j < 5; ++j) {
        /** 每次排序前,打印出数组元素 */
        printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
        cur = a[j];
        i = j - 1;
        /** 将 cur 与它左边的值一一比较 */
        while ( (0 <= i)&&(cur<a[i]) ) {
            a[i+1] = a[i];
            --i;
        }
        a[i+1] = cur;
    }
    /** 排序完成后,打印出数组元素 */
    printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
}
int main(void)
{
    int a[5] = { 9, 7, 3, 1, 8 };
    insertion_sort(a);
    return 0;
}


程序还是比较简单的,编译这段C语言代码并执行:

# gcc t.c
# ./a.out 
9, 7, 3, 1, 8
7, 9, 3, 1, 8
3, 7, 9, 1, 8
1, 3, 7, 9, 8
1, 3, 7, 8, 9

发现最终数组被正确排序了,算法是有效的。插入排序法在处理超大数组时耗时比较多,而且笔试题目要求写出多种算法并对比效率,因此我们还需要再写出其他排序算法,并分析它们之间的效率差异。限于篇幅,下一节再说了。


C语言面试题详解第14节 - 刘冲的博客(https://blog.popkx.com) 原创版权所有,转载请注明出处。
点赞 (0)分享 (0)
发表我的评论
取消评论
表情     9 + 4 = ? (必填)