上篇日志中提出了一个EMC某年的笔试题目，题目如下：
题目：
函数声明如下：
int func(int i, int N); |
其中，i<=N， 功能输出i递增到N再递减到i的整数，每行输出一个数。比如func(1, 5)的输出是:
1 2 3 4 5 4 3 2 1 |
要求：
- 函数中只能有一个语句，即1个分号。
- 不能使用do while until goto for if关键字，不能使用?:和逗号操作符。
- 唯一能使用的库函数为printf。
我们都知道，&&是逻辑与， ||是逻辑或。对于这两个运算符，有下面的性质：
1 && 1 = 1; 1 && 0 = 0; 0 && 1 = 0; 0 && 0 = 0; 1 || 1 = 1; 1 || 0 = 1; 0 || 1 = 1; 0 || 0 = 0; |
出了这些基本的性质之外，额外需要注意的是，在C语言中，这两个运算符有如下的性质：
- && 的 优先级高于 ||。
让我们看如下代码：
算法是很巧妙的东西，很多时候你以为你写了一个时间复杂度和空间复杂度最低的算法，但实际上还有更好的方法，让我们来看两个通过位操作优化的小算法。
第一题：给两个变量a和b，如何不使用第三个变量，而交换a和b的值？
第二题：假设给一个长度为2n+1的数组，数组中有n个数是成对出现的，求只出现一次的数的值。要求尽量降低时间和空间复杂度。
第一个题目相对比较简单，第二个题目我觉得大多数人也能给出比较好的答案，大家不妨先思考下再看下面的答案。
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转。
现在给出旋转后的数组和一个数，旋转了多少位不知道，要求给出一个算法，算出给出的数在该数组中的下标，如果没有找到这个数，则返回-1。要求查找次数不能超过n。
这个题要想尽量减少是件复杂度，我觉得使用二分查找最好，只是需要稍微变化下，下面给出C语言描述的程序：
fork
是linux下的一个系统调用，它的作用是产生一个子进程，子进程是当前进程的一个副本，它跟父进程有一样的虚存内容，但也有一些不同点，读者可以自己参考这里。
但是，值得注意的是，父进程调用fork()后，fork()返回的是生成的子进程（如果能顺利生成的话）的ID。子进程执行的起点也是代码中fork的位置，不同的是子进程fork()返回的是0。如下代码：
int i; i = fork(); printf("%dn",i); |
这段代码中，父进程打印出来的值是“子进程id”，而子进程打印出来的是0。
www.spongeliu.com
好了，废话介绍完了，让我们切入正题，看两个比较有意思的C语言题目。
www.spongeliu.com
因为最近项目关系，需要动态二进制翻译一个驱动，所以看了下驱动相关知识，并在这里做一个简单普及性的介绍。
.
首先，我们都知道，Linux分为用户态和内核态，一般应用程序是在用户态执行，他们通过一系列的系统调用同内核态进行交互。那么驱动程序扮演一个什么样的角色呢？
.
驱动程序是内核与硬件的接口，他把系统调用映射到具体设备对于实际硬件的特定操作上，关系如下图所示：
.
本文是为了加深自己对各种算法的理解，部分摘自维基百科，这里主要介绍较为常用的排序方法，一些生僻的算法不做介绍。
.
总结各种算法之前，现介绍下几个概念：
1、稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。
2、计算的复杂度（最差、平均、和最好表现），依据串行（list）的大小（n）。一般而言，好的表现是O(n log n)，且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(n log n)。
.
稳定排序：
* 泡沫排序（bubble sort） — O(n²)
* 插入排序 （insertion sort）— O(n²)
* 桶排序 （bucket sort）— O(n); 需要 O(k) 额外空间
* 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
* 合并排序 （merge sort）— O(n log n); 需要 O(n) 额外空间
* 二叉排序树排序 （Binary tree sort） — O(n log n)期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
* 基数排序 （radix sort）— O(n·k); 需要 O(n) 额外空间
.
不稳定排序
* 选择排序 （selection sort）— O(n²)
* 希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
* 堆排序 （heapsort）— O(n log n)
* 快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
多线程程序可能存在很多潜在的bug，如data race，dead lock，信号bug等，而这些bug一向很难调试，现在有很多论文都是基于多线程程序的调试技术的，比如model check，死锁检测，replay技术等，也有很多对应的工具，如intel的pinplay，微软的Zing等。关于这些技术和工具，如果感兴趣可以 google相应的论文进一步了解。这里我主要讲述的是我在对二进制翻译下多线程程序调试中经常使用的一些方法以及一些调试经验，虽然我的调试的是二进制翻译器，但是这些方法也同样适用于大多数多线程程序。
问题1：安装guest addition时遇到如下问题
.. .. Building the Virtualbox Guest Additions kernel modules [FAILED] (Your system does not seem to be set up to build kernel modules. Look at /var/log/vboxadd-install.log to find out what went wrong) .. |
/var/log/vboxadd-install.log里面错误内容如下
Makefile:23: *** Error: Unable to find the sources of your current Linux kernel. Specify KERN_DIR=<directory> and run MAKE again.. Stop. |
最新回复评论