2011年2月27日星期日

打印质数的各种算法

打印质数的算法应该是学习计算机编程的一个经典的问题，在这里想给大家展示一些方法，相信这些方法会对你的编程有一定的启发作用。请你注意几点，

实际应用和教学应用有很大的差别。
最后的那个使用编译时而不是运行时的方法大家可以重点看看。

教科书的示例

首先，先给一个教科书的示例。下面这个示例应该是教科书（至少是我上大学时的教科学）中算法复杂度最好的例子了。其想法很简单，先写一个判断是否是质数的函数isPrime()，然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心，其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n))，看上去不错，但其实很不经济。


#include <iostream> 
using namespace std;  
bool isPrime(int nr) {
     for (int d = 2; (d * d) <= (nr + 1); ++d){
         if (!(nr % d)){
             return false;
         }
      }
     return true;
 }  

int main (int argc, char * const argv[]) {
     for (int i = 0; i < 50; ++i){
         if (isPrime(i)){
             cout << i << endl;
         }
     }
 }

较好的算法

我们知道，我们的算法如果写成线性算法，也就是O(n)，已经算是不错了，但是最好的是O(Log(n))的算法，这是一个级数级的算法，著名的二分取中（Binary Search）正是O(Log(n))的算法。通常来说，O(Log(n))的算法都是以排除法做为手段的。所以，找质数的算法完全可以采用排除法的方式。如下所示，这种算法的复杂度是O(n(log(logn)))。
示例：打印30以内的质数
一、初始化如下列表。

2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

二、把第一个数（2）取出来，去掉所有可以被2整除的数。

2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

三、取第二个数（3），去掉所有可以被 3整除的数。

2  3     5     7          11    13          17    19          23    25          29

四、取第三个数（5），因为4已经被去除了，再去掉所有可以被5整除的数。

2  3     5     7          11    13          17    19          23                29

接下来的数是7，但是7的平方是49，其大于了30，所以我们可以停止计算了。剩下的数就是所有的质数了。

实际应用的算法

实际应用中，我们通常不会使用上述的两种算法，因为那是理论学院派的算法。实际中的算法是，我把质数事先就计算好，放在一个文件中，然后在程序启动时（注意是在启动时读这个文件，而不是运行时每调用一次就读一次文件），读取这个文件，然后打印出来就可以了。如果需要查找的化，二分查找或是hash表查找将会获得巨大的性能提升。当然，这样的方法对于空间来说比前面两个都要消耗得大，但是你可以有O(log(n))或是O(1)的时间复杂度。
所以，我想在这里提醒大家——实际和理论的的方法很不一样的，千万不要读书读成书呆子。在游戏编程的世界里，大量的数据都不是运行计算的，而都是写在文件中的。比如，一个火焰效果，一个人物跑动的动作，都是事先写在文件中的。

使用编译时而不是运行时

下面这个例子（本例参考于这里）你需要注意了，这是一个高级用法，使用模式来在编译时计算质数，而不是运行时。这种技术使用了C++编译器对模板的特化时的处理来生成自己相要的结果。这种方法在技术上是相当Cool的，但并不一定实用，这里只是想像大家展示这种用法。这是C++的最骨灰级的用法了。
请看下面的两个模板类，第一个模板以递归的方式检查是否是质数，第二个方法是递归的退出条件（当N=1时），对于模板的重载，请参看相关的C++书籍。

template<int N, int D = N - 1> 
struct isPrime {
     enum {
         result = (N % D) && isPrime<N, D-1>::result
     };
 };

template<int N> 
struct isPrime<N, 1> {
     enum {
         result = true
     };
 };

于是，通过这个模板，我们可以使用下面的代码来检查是否是质数：

if (isPrime<3>::result)
     cout << "Guess what: 3 is a prime!";

下一步，我们需要打出一个区间内的质数，所以，我们需要继续设计我们的print模板。

template<int N, bool ISPRIME> 
struct printIfPrime {
     static inline void print() {} 
};  
template <int N> 
struct printIfPrime<N, true> {
     static inline void print() {
         std::cout << N << endl;     
     }
};

从上面的代码中，我们可以看到，我们的第一个实际是什么也没做，而第二个有输出，注意第二个的模板参数中有一个true，其意味着那个质数的判断。于是我们就可以给出下面的代码来尝试着打印出一段区间内的质数：（请不要编译！！因为那会让编译器进入无限循环中，原因是printPrimes会不停地调用自己永不停止）


template<int N, int MAX> 
struct printPrimes {
     static inline void print()     {
         printIfPrime<N, isPrime<N>::result>::print();
         printPrimes<N + 1, MAX>::print();
     }
 };

为了避免这个问题，你需要再加一个模板类，如下所示。这样当N变成MAX的时候，递归就结束了。


template<int N> 
struct printPrimes<N, N> {
     static inline void print() {
         printIfPrime<N, isPrime<N>::result>::print();     
     } 
};

最后，让我们来看看最终的调用：

int main (int argc, char * const argv[]) {
     printPrimes<2, 40>::print();
     return 0;
 }

这个方法很NB，但是有两个问题：

比较耗编译时间。
不能在运行时输入MAX的值。

不过，相信这种玩法会启动你很多的编程思路。
（全文完)

2011年2月10日星期四

C++中数组参数详解

在C++中，数组永远不会按值传递。它是传递第一个元素（准确地说是第0个）的指针。

例如，如下声明：

void putValues(int[10]);

被编译器视为：

void putValues(int*);

数组的长度与参数声明无关。因此，下列三个声明是等价的：

void putValues(int*);

void putValues(int[]);

void putValues(int[10]);

因为数组被传递为指针，所以这对程序员有两个含义：

1、在被调函数内对参数数组的改变将被应用到数组实参上而不是本地拷贝上。当用作实参的数组必须保持不变时，程序员需要保留数组的拷贝。函数可以通过把参数类型声明为const来表明不希望改变数组元素：

void putValues(const int[10]);

2、数组长度不是参数类型的一部分。函数不知道传递给它的数组的实际长度，编译器也不知道，当编译器对实参类型进行参数类型检查时，并不检查数组的长度。

例如：

void putValues(int[10]); //视为int*

int main()

{

int i, j[2];

putValues(&i); //ok:&i是int*; 潜在的运行错误

putValues(j); //ok:j被转换成第0个元素的指针

// 实参类型为int*:潜在的运行错误

return 0;

}

参数的类型检查只能保证putValues()的再次调用都提供了int*型的实参。类型检查不能检验实参是一个10元素的数组。

习惯上，C风格字符串是字符的数组，它用一个空字符编码作为结尾。但是所有其他类型，包括希望处理内含字符的字符数组，必须以某种方式在向函数传递实参时使其知道它的长度。一种常见的机制是提供一个含有数组实参的长度的额外参数。例如：

void putValues(int[], int size);

int main()

{

int i,j[2];

putValues(&i, 1);

putValues(j, 2);

return 0;

}

另外一种机制是将参数声明为数组的引用。当参数是一个数组类型的引用时，数组长度成为参数和类型的一部分，编译器检查数组实参的长度与在函数参数类型中指定的长度是否匹配。

// 参数为10个int的数组

// parameter is a reference to an array of 10 ints

void putValues(int (&arr)[10]);

int main()

{

int i, j[2];

int a[10];

putValues(i); // 错误：实参不是10个int的数组

putValues(j); // 错误：实参不是10个int的数组

putValues(a); // 正确

return 0;

}

因为数组的长度现在是参数类型的一部分，所以putValues()的这个版本只接受10个int的数组。这限制了可以作为实参被传递给putValues()的数组的种类。但是，它也使函数的实现更加简单。

ShowWindow的疑问

本文：[转寄][转贴][删除][修改][回复][作者:novice][人气:81]

发信人: novice (Android), 信区: VC

标题: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月06日23:59:04 星期天), 站内信件 WWWPOST

BOOL WINAPI ShowWindow(

__in HWND hWnd,

__in int nCmdShow

);

中 nCmdShow,MSDN中有这么段话：

This parameter is ignored the first time an application calls ShowWindow, if

the program that launched the application provides a STARTUPINFO structure.

Otherwise, the first time ShowWindow is called, the value should be the

value obtained by the WinMain function in its nCmdShow parameter.

要怎么理解？？？

我的理解是，如果我用CreateProcess创建某程序，该程序就是创建个窗口，别无其他功

能，调用CreateProcess时提供了STARTUPINFO si，并将相应的标志位设置si.dwFlags =

STARTF_USESHOWWINDOW，si.wShowWindow = SW_SHOWMINIMIZED.

这样的话，即使被创建的程序第一次调用ShowWindow时传入参数 SW_SHOWMAXIMIZED ,程

序也应该刚开始是最小化的。因为按照文档说明，参数该被忽略。

但实际试验了一下，还是会出现最大化得窗口。不知道我哪里理解错误？

本文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:7]

发信人: CrLF (CrLF(落羽猫)), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月07日13:26:12 星期一), 站内信件 WWWPOST

注意认真读文档：if the program that launched the application provides a

STARTUPINFO structure.

典型的提供STARTUPINFO的方法如：建立一个快捷方式，通过双击快捷方式启动。

本文：[转寄][转贴][删除][修改][回复][作者:novice][人气:2]

发信人: novice (Android), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月07日21:04:18 星期一), 站内信件 WWWPOST

调用CreateProcess时，给 STARTUPINFO 赋值，不算提供STARTUPINFO 么？

本文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:5]

发信人: CrLF (CrLF(落羽猫)), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月08日13:40:44 星期二), 站内信件 WWWPOST

之前理解错了。查了一下，使用STARTUPINFO 里提供的wShowWindow的条件是：

第一种情况：ShowWindow的参数设为SW_SHOWDEFAULT

第二种情况：满足以下条件，系统认定为主窗口：

1. 设置了 STARTF_USESHOWWINDOW.

2. 窗口是顶级窗口、无所有者、有WS_CAPTION、不是系统模态窗口

这种情况下若ShowWindow 的参数为 SW_SHOWNORMAL 或 SW_SHOW，则使用你给定的参数.

于是SW_MAXIMIZE不在此列…………

好吧，MSDN的文档不全……

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.157]

※ 修改:・CrLF 于 2011年02月09日17:24 修改本文・[FROM: 60.18.151.188]

novice

69307364

本文：[转寄][转贴][删除][修改][回复][作者:novice][人气:6]

发信人: novice (Android), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月08日16:27:05 星期二), 站内信件 WWWPOST

不好意思，没明白你的意思。我能理解，在你列举的两种情况下，如果给ShowWindow提

供SW_SHOWDEFAULT或者SW_SHOWNORMAL使得窗口按照STARTUPINFO的wShowWindow显示。

我不能明白的是，MSDN文档里说的，第一次调用ShowWindow忽略nCmdShow参数的情况。

对于“忽略”一词，我的理解是不管传入什么值，它都按照固定的方式显示。

调用CreateProcess时给STARTUPINFO赋值，不算提供STARTUPINFO么？

【在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: 之前理解错了。查了一下，使用STARTUPINFO 里提供的wShowWindow的条件是：

: 第一种情况：ShowWindow的参数设为SW_SHOWDEFAULT

: 第二种情况：满足以下条件，系统认定为主窗口：

: 1. 设置了 STARTF_USESHOWWINDOW.

: 2. 窗口是顶级窗口、无所有者、有WS_CAPTION、不是系统模态窗口

: 3. ShowWindow 的参数为 SW_SHOWNORMAL 或 SW_SHOW.

: 于是SW_MAXIMIZE不在此列…………

: 好吧，MSDN的文档不全……

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 125.78.224.32]

※ 修改:・novice 于 2011年02月08日16:28 修改本文・[FROM: 125.78.224.32]

CrLF

53453131364

本文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:5]

发信人: CrLF (CrLF(落羽猫)), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月08日18:11:36 星期二), 站内信件 WWWPOST

不是，我查给你的规则是实际的规则（系统实际是这样做的）。msdn文档写的含糊 :)

信我查的好了。写msdn文档的人肯定没有写windows的人知道的清楚:P

【在 novice (Android) 的大作中提到: 】

: BOOL WINAPI ShowWindow(

: __in HWND hWnd,

: __in int nCmdShow

: );

: 中 nCmdShow,MSDN中有这么段话：

: This parameter is ignored the first time an application calls ShowWindow, if

: the program that launched the application provides a STARTUPINFO structure.

: Otherwise, the first time ShowWindow is called, the value should be the

: value obtained by the WinMain function in its nCmdShow parameter.

: 要怎么理解？？？

: 我的理解是，如果我用CreateProcess创建某程序，该程序就是创建个窗口，别无其他功

: 能，调用CreateProcess时提供了STARTUPINFO si，并将相应的标志位设置si.dwFlags =

: STARTF_USESHOWWINDOW，si.wShowWindow = SW_SHOWMINIMIZED.

: 这样的话，即使被创建的程序第一次调用ShowWindow时传入参数 SW_SHOWMAXIMIZED ,程

: 序也应该刚开始是最小化的。因为按照文档说明，参数该被忽略。

: 但实际试验了一下，还是会出现最大化得窗口。不知道我哪里理解错误？

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.146]

novice

69307364

本文：[转寄][转贴][删除][修改][回复][作者:novice][人气:3]

发信人: novice (Android), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月08日20:18:32 星期二), 站内信件 WWWPOST

那意思是 ShowWindow第一次调用与后续调用没区别？

【在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: 不是，我查给你的规则是实际的规则（系统实际是这样做的）。msdn文档写的含糊 :)

: 信我查的好了。写msdn文档的人肯定没有写windows的人知道的清楚:P

: 【在 novice (Android) 的大作中提到: 】

: : BOOL WINAPI ShowWindow(

: : __in HWND hWnd,

: : __in int nCmdShow

: : );

: : 中 nCmdShow,MSDN中有这么段话：

: : This parameter is ignored the first time an application calls ShowWindow, if

: : the program that launched the application provides a STARTUPINFO structure.

: : Otherwise, the first time ShowWindow is called, the value should be the

: : value obtained by the WinMain function in its nCmdShow parameter.

: :

: : 要怎么理解？？？

: :

: : 我的理解是，如果我用CreateProcess创建某程序，该程序就是创建个窗口，别无其他功

: : 能，调用CreateProcess时提供了STARTUPINFO si，并将相应的标志位设置si.dwFlags =

: (以下引言省略...)

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 125.78.224.32]

CrLF

53453131364

本文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:3]

发信人: CrLF (CrLF(落羽猫)), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月09日17:28:30 星期三), 站内信件 WWWPOST

不不，你还是没明白我的意思。

首先是，不一定是*第一次*调用ShowWindow~ 而是第一次对符合主窗口条件（见上面）

的窗口调用ShowWindow 的时候。

这个时候如果你用SW_SHOW或SW_SHOWNORMAL，系统会替换。

你的程序系统认为它是主窗口了，但是你给的是最大化，系统就不管了~

【在 novice (Android) 的大作中提到: 】

: 那意思是 ShowWindow第一次调用与后续调用没区别？

: 【在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: : 不是，我查给你的规则是实际的规则（系统实际是这样做的）。msdn文档写的含糊 :)

: :

: : 信我查的好了。写msdn文档的人肯定没有写windows的人知道的清楚:P

: :

: : (以下引言省略...)

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.188]

novice

69307364

本文：[转寄][转贴][删除][修改][回复][作者:novice][人气:5]

发信人: novice (Android), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月09日20:12:03 星期三), 站内信件 WWWPOST

抱歉在这个问题上纠缠这么久。

再说说我现在的理解。你的意思是：在满足主窗口条件时，第一次调用ShowWindow时使

用SW_SHOW或SW_SHOWNORMAL，会使窗口按照STARTUPINFO的信息显示？

MSDN里文档里说的“忽略”就是上述意思？“This parameter is ignored the first

time an application calls ShowWindow, if the program that launched the

application provides a STARTUPINFO structure.”感觉另有深意啊。

那为什么要称为“ignored”呢？因为是上述说法的话，那等同于在SW_SHOW或SW_

SHOWNORMAL时，使用STARTUPINFO的信息。而其他参数也按照各自本来的效果显示，并没

有被忽略。

感觉你的意思是在说明在什么条件下使用STARTUPINFO的信息，而我最大的疑惑是MSDN文

档里的“忽略”二字。不对之处请指正。

【在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: 不不，你还是没明白我的意思。

: 首先是，不一定是*第一次*调用ShowWindow~ 而是第一次对符合主窗口条件（见上面）

: 的窗口调用ShowWindow 的时候。

: 这个时候如果你用SW_SHOW或SW_SHOWNORMAL，系统会替换。

: 你的程序系统认为它是主窗口了，但是你给的是最大化，系统就不管了~

: 【在 novice (Android) 的大作中提到: 】

: : 那意思是 ShowWindow第一次调用与后续调用没区别？

: :

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 222.77.201.102]

※ 修改:・novice 于 2011年02月09日20:25 修改本文・[FROM: 222.77.201.102]

CrLF

53453131364

本文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:2]

发信人: CrLF (CrLF(落羽猫)), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月09日23:00:37 星期三), 站内信件 WWWPOST

it is "ignored" becuase it is "overridden" :)

MSDN只是没说识别的细节而已。实际上你从设计意图上理解比较好。它之所以这么设计

，就是为了让写程序的人不用考虑到底该用什么参数。你只要主窗口的ShowWindow用

WinMain参数里给定的那个，根本不用考虑这些。如果需要在前面显示对话框，就该是模

态的。如果同时显示对话框，主窗口一般是所有者……总之，为了方便，你什么都不做

，交给Windows就好。

【在 novice (Android) 的大作中提到: 】

: 抱歉在这个问题上纠缠这么久。

: 再说说我现在的理解。你的意思是：在满足主窗口条件时，第一次调用ShowWindow时使

: 用SW_SHOW或SW_SHOWNORMAL，会使窗口按照STARTUPINFO的信息显示？

: MSDN里文档里说的“忽略”就是上述意思？“This parameter is ignored the first

: time an application calls ShowWindow, if the program that launched the

: application provides a STARTUPINFO structure.”感觉另有深意啊。

: 那为什么要称为“ignored”呢？因为是上述说法的话，那等同于在SW_SHOW或SW_

: SHOWNORMAL时，使用STARTUPINFO的信息。而其他参数也按照各自本来的效果显示，并没

: 有被忽略。

: 感觉你的意思是在说明在什么条件下使用STARTUPINFO的信息，而我最大的疑惑是MSDN文

: 档里的“忽略”二字。不对之处请指正。

: 【在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: : 不不，你还是没明白我的意思。

: :

: : 首先是，不一定是*第一次*调用ShowWindow~ 而是第一次对符合主窗口条件（见上面）

: (以下引言省略...)

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.188]

※ 修改:・CrLF 于 2011年02月09日23:08 修改本文・[FROM: 60.18.151.188]

novice

69307364

本文：[转寄][转贴][删除][修改][回复][作者:novice][人气:0]

发信人: novice (Android), 信区: VC

标题: Re: ShowWindow 的疑问

发信站: 瀚海星云 (2011年02月10日09:59:17 星期四), 站内信件 WWWPOST

it is "ignored" becuase it is "overridden" 。了解了。

哦哦，那结论是第一次调用时乖乖用WinMain的nCmdShow啦。

多谢！

【在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: it is "ignored" becuase it is "overridden" :)

: MSDN只是没说识别的细节而已。实际上你从设计意图上理解比较好。它之所以这么设计

: ，就是为了让写程序的人不用考虑到底该用什么参数。你只要主窗口的ShowWindow用

: WinMain参数里给定的那个，根本不用考虑这些。如果需要在前面显示对话框，就该是模

: 态的。如果同时显示对话框，主窗口一般是所有者……总之，为了方便，你什么都不做

: ，交给Windows就好。

: 【在 novice (Android) 的大作中提到: 】

: : 抱歉在这个问题上纠缠这么久。

: :

: : 再说说我现在的理解。你的意思是：在满足主窗口条件时，第一次调用ShowWindow时使

: : 用SW_SHOW或SW_SHOWNORMAL，会使窗口按照STARTUPINFO的信息显示？

: :

: : MSDN里文档里说的“忽略”就是上述意思？“This parameter is ignored the first

: : time an application calls ShowWindow, if the program that launched the

: : application provides a STARTUPINFO structure.”感觉另有深意啊。

: :

: : 那为什么要称为“ignored”呢？因为是上述说法的话，那等同于在SW_SHOW或SW_

: : SHOWNORMAL时，使用STARTUPINFO的信息。而其他参数也按照各自本来的效果显示，并没

: (以下引言省略...)

给定一个数组，找出不在数组中的最小的那个数字

来源:原文链接

这是在TL讨论中Liu xinyu给出的一个例子，觉得思路挺有启发的，所以整理记录一下。
给定一个数组，其内容是一些随机的、不重复的正整数，如：
{4, 23, 1, 8, 9, 21, 6, 12}
要求找出不在数组中出现的最小的那个数，比如这个数组中未在数组中出现的最小值是：2
这个问题实际应用的原型可以是一个ID分配系统，其使用一个数组来保存已分配的ID，每次回收就从数组中删除一个元素(O(n))，而分配则需要找到最小的那个可用的ID，就是这个算法要做的事情。
这个问题从naive的解法到快速的解法的思路转换是十分巧妙的，当然，如果之前没有接触过类似的题，注意到这个特性应该不是一件很容易的事。
设数组为A，大小为n，下标从1开始，下面是一系列逐步改进的算法：
一、穷举查找
一般的问题都可以通过这种很暴力的方式来做，从1到n逐个判断是否在数组中：
MIN-AVAILABLE-NUM(A, n)
for i = 1 to n
do if i not in A
then return i
return n+1
显然，这里的算法复杂度是O(n^2)
二、先排序再二分查找
第一种方法，每次查找都是线性查找，要改进最先想到的自然是二分查找，二分查找的前提是有序，所以：

先排序，用O(nlgn)的快速排序、归并排序或者堆排序；因为数组中的元素是一些自然数，我们甚至可以使用O(n) 的基数排序，当然，需要更多的内存。
对1..n进行判断，复杂度也为O(nlgn)

所以，整体的算法复杂度为O(nlgn)
三、该数组的一个特性
其实仔细观察该数组A[1]..A[n]，我们可以得出一个结论：如果该数组中存在未被使用的数，那么Max(A) > n。
证明很简单，假设Max(A) <= n，由于该数组大小为n，那么该数组中的元素只能是从1到n的某个排列，从而得出该数组中不存在未被使用的数，矛盾。
这个特性和抽屉原理有些类似之处。
从而我们可以有另外一个方法：

先排序
再利用该特性搜索

MIN-AVAILABLE-NUM(A, n)

for i = 1 to n

do A[i] > i

then return i

return n+1

注意到，如果我们使用基数排序，可以将复杂度降低到O(n)。
四、一个线性时间，线性空间的算法
第三个算法虽然能达到理论意义上的O(n)，但是基数排序隐含的常数因子较大，而且不是原地排序，这里给出一个不需要排序的算法：
MIN-AVAILABLE-NUM(A, n)
for i = 1 to n
B[i] = 0
for i = 1 to n
do if A[i] < n
then B[A[i]] = 1
for i = 1 to n
if(B[i] == 0) return i;
return n+1;
这里使用一个辅助数组B来表示1到n这些数是否存在在数组A中，只要不存在就将其标为0，最后在B中找到第一个值为0的便是我们要找的那个元素；如果B中元素全为1，这说明A使用了所有1到n这些数，那么返回的便是下一个n+1.
此处无须排序，且复杂度为O(n)，但需要一个额外的O(n)的数组。
五、一个线性时间、常数空间的算法
利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
MIN-AVAILABLE-NUM(A, low, up)
if(low == up) return low
m = (low + up) / 2
split = partition(A, low, up, m)
if a[split] == m
then return MIN-AVAILABLE-NUM(A, low, split)
else return MIN-AVAILABLE-NUM(A, split+1, up)
这里递归式为：T(n) = T(n/2) + O(n)，根据主定理的第三种情况，复杂度为O(n)，其实也就是一个等比数列：n + n/2 + n/4...

2011年1月28日星期五

我的Linux书架

来源:原文链接

工作几年来，一直从事Linux内核驱动方面的开发。从接触Linux到现在，读过不少Linux方面的书籍，现把认为很不错的一部分列出来和大家分享一下。

入门类

一直认为，在一个系统上学习开发之前，首先需要熟悉这个系统的使用。鉴于天朝的国情，绝大部分人第一个接触的操作系统就是Windows，因此对于这绝大部分人来说，如果要学习Linux开发，学会使用这个系统都是必不可少的一个环节。

现在的Linux初学者是幸福的，随着Linux桌面环境越来越易用，入门一个新的系统是非常容易的事情。虽然命令行对于提高工作效率更加有效，但我们完全可以把熟悉命令的过程放到日常使用中进行。无论学习什么知识，在实践中学习都是高效而且有趣的。在这个阶段，我们也未必一定需要书籍。现在很多Linux发行版的Wiki写得都非常详细，在使用某一种发行版时找到相应的Wiki阅读查询就可以了。而且，桌面环境变化太快，关于桌面的介绍类书籍几乎都没有必要看，这类书籍大多刚一出版就过时了。

那入门类书籍里哪些比较有价值呢？我比较推荐涉及的技术相对比较稳定的书。比如，Linux基本的体系结构和命令一般都是经久不变的，甚至从上古时期的Unix开始就没太多变化，这类书籍讲解的知识也是以后大幅提高我们的生产力的基础。比如《鸟哥的Linux私房菜》，比如《Unix Power Tools》（中译名是"UNIX超级工具"），或者是为Linux+认证考试准备的《Linux+ Study Guide》。当然，这一类书籍其实都不必精读，快速浏览之后作为工具书备查就可以了。

编程类

类Unix系统的编程书籍里，最经典的莫过于简称为APUE的《Advanced Programming in the UNIX Environment》（中译名是"Unix环境高级编程"），这本书被广大Unix程序员（包括Linux）捧为"圣经"。借用葛大爷的广告词："这就像进馆子一样，一条街上，哪家人多我进哪家"。APUE对类Unix系统的编程接口讲解的非常全面详细，对于这本书，我们不仅要精读，还应该放在案头常备。

但是，APUE对于Linux编程初学者似乎稍深了一点，而且很多细节在Linux中并不会用到。讲述Linux编程的书籍里，《Advanced Linux Programming》应该更加适合初学者。不要被书名中的"Advanced"吓到，书里的内容还是很容易理解的。看完这本书再看APUE应该效果会更好。

如果要开发GUI程序，上面两本书就无能为力了。在Linux世界里，最常用的GUI Toolkit是GTK+和QT。

GTK+的书籍并不多，在线文档只适合查阅，并不是一个完整的学习体系。《Foundations of GTK+ Development》是其中很不错的一本书，喜欢GTK+的开发者可以拿来作为入门书籍。

相对来说，QT的书籍就很丰富了，这和QT具有良好的跨平台能力有很大关系，QT的书籍并不只是写给Linux程序员看的，在Windows和MAC OSX下同样可以使用QT开发程序。比较值得一看的QT类书籍有《C++ GUI Programming with QT4》、《Foundations of QT Development》、《The Art of Building QT Applications》，这三本都比较适合QT初学者阅读。另外，《Advanced Qt Programming》会介绍到QT一些比较高级的用法，适合有一定QT基础的读者阅读。

内核类

对于Linux内核或者设备驱动的开发者，最全面最直接的学习资料一定是Linux内核代码及其文档。Linux内核的发布周期很短，相关书籍的出版完全跟不上脚步。但随着内核代码的日益庞大，学习曲线越来越陡峭，入门者又非常需要书籍来作为指导，这确实是非常矛盾的事情。所幸，很多Linux内核技术作家也是很勤奋的，经常会更新自己的作品。就像Robert Love，以2.6内核为蓝本的《Linux Kernel Development》已经更新到第三版了。LKD是非常适合内核初学者阅读的一本好书，对它的评价可以引用陈莉君老师的译者序：

相对于 Daniel P. Bovet 和 Marco Cesati 的内核巨著《 Understand the Linux Kernel 》，它少了五分细节，相对于实践经典《 Linux Device Drivers 》，它多了五分说理。可以说，本书填补了 Linux 内核理论和实践之间的鸿沟，"一桥飞架南北，天堑变通途"。

谢谢陈老师，她的译者序帮我引出了另外要谈到的两本经典书籍，对，就是《Understanding the Linux Kernel》和《Linux Device Drivers》。对于这两本书，如果要挑它们的缺点，我只能说，内容有点老，很多知识点都需要更新了，除此之外，我要说的是，是它们把我带上了内核驱动开发这条路上来，当然，还有LKD。

最近，我又发现一本分析Linux内核的优秀书籍，就是《Professional Linux Kernel Architecture》。这本书我目前正在读，写得非常好，而且因为此书相对较新（只是相对，2.6.24内核在现在看来也很老了），没有看过ULK的同学可以直接看这本书。

工具类

工欲善其事，必先利其器。进行Linux开发，相关工具还是需要熟练使用的。比如，GNU Tool Chain、自动构建工具、编辑器、版本控制工具等等。

这里有一本包罗万象的书，叫做《Handbook of Open Source Tools》，书中介绍了各种各样的开源工具，可称之为开源技术的总决式。这本书试图面面俱到，因此并不深入，粗读即可。

GNU Tool Chain参考Redhat的《The GNUPro Toolkit》已经足够了，如果单独把makefile拎出来，还可以参考《Managing Projects with GNU Make》。

自动构建工具可以参考《Autotools》。如果您准备使用cmake，推荐cjacker的《Cmake实践》。《Mastering CMake》据说是cmake的权威书籍，但一直无缘得见啊。

说到编辑器，在Linux里最著名的莫过于Vim和Emacs，关于这两者的背景，可以去看看《为何Emacs和Vim被称为两大神器》。我几乎没用过Emacs，曾经在当当做活动时花9块钱买了一本《学习GNU Emacs》，有这本书作为Emacs的入门我想应该够了。Vim是我经常使用的编辑器之一（另一个是Kate，最初喜欢上Kate的原因之一就是它提供了Vim编辑模式），相关的书籍有两本值得一读：《A Byte of Vim》和《Hacking Vim 7.2》，但是对于初学者，首先跟着Vim自带的vimtutor练习效果会更好。

Linux下的版本控制工具很多，有传统的Subversion，也有现在非常流行分布式工具如Git等。Subversion可以参考这本《Version Control with Subversion》，Git可以参考《Version Control with Git》或者《Git Internals》或者《Pro Git》。

其它

除了以上几个类别，还有一些书籍值得推介。

比如《The Art of Unix Programming》，主要介绍了Unix系统领域中的设计开发哲学、思想文化体系以及社群文化等，覆盖面非常广。书中的一些内容和《Revolution OS》有相似之处，大家可以自己印证一下。对于这本书，我们也完全可以把它当做小说或者历史书来看，可以躺在床上看，也可以瘫在沙发上看，或者像怪怪那样坐在马桶上看，总之，不必一定要端坐在书桌前。

《Computer Systems: A Programmer's Perspective》很多人都推荐过，这是一本非常经典的计算机体系方面的教材。CSAPP的内容基础全面，讲解简明扼要，易于理解，仔细读完之后对理清计算机体系结构甚至是Linux内核都非常有帮助的。虽然中文名被译为《深入理解计算机系统》（这个译名很不贴切），但相比之下，为什么会让人感觉国内的同类教材更加"深奥"呢？也许，这就是作者功力的差距吧。

注：这里列出的书大多都可以在library.nu上下载到，注册登录之后会有搜索框，用书名搜索即可。

2011年1月26日星期三

趣题：两步猜出多项式的各项系数

来源: Matrix67

有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。有一个不可思议的结论：你可以在两步之内还原出整个多项式！这是如何做到的呢？

首先，输入 1 ，于是便得到整个多项式的所有系数之和。不妨把这个系数和记作 S 。下一步，输入 S + 1 ，于是黑匣子返回

a_n * (S + 1)ⁿ + a_n-1 * (S + 1)^n-1 + … + a₁ * (S + 1) + a₀

把这个值转换成 S + 1 进制，依次读出每一位上的数，它们就是多项式的各项系数了。

来源：http://rjlipton.wordpress.com/2010/12/20/some-mathematical-gifts/
这个有趣的问题曾经以另一形式出现在了这个 Blog 里，见这里的 35 题。

2011年1月10日星期一

VC++ 2005 Express + SDK

You can use Visual C++ Express to build powerful .NET Framework applications immediately after installation. In order to use Visual C++ Express to build Win32 applications, you'll need to take just a few more steps. I'll list the steps necessary for building Win32 applications using Visual C++ Express.

Step 1: Install Visual C++ Express.

If you haven't done so already, install Visual C++ Express.

Step 2: Install the Microsoft Platform SDK.

Install the Platform SDK over the Web from the Download Center. Follow the instructions and install the SDK for the x86 platform.

Step 3: Update the Visual C++ directories in the Projects and Solutions section in the Options dialog box.

From the Tools menu in Visual Studio, select Options. The Options dialog box appears.

From the Options dialog box, expand the Projects and Solutions node and select VC++ Directories. In that section, add the following paths to the appropriate subsection:

    * Executable files: C:\Program Files\Microsoft Platform SDK for Windows Server 2003 R2\Bin
    * Include files: C:\Program Files\Microsoft Platform SDK for Windows Server 2003 R2\Include
    * Library files: C:\Program Files\Microsoft Platform SDK for Windows Server 2003 R2\Lib

Note: Alternatively, you can update the Visual C++ Directories by modifying the VCProjectEngine.dll.express.config file located in the \vc\vcpackages subdirectory of the Visual C++ Express install location. Please make sure that you also delete the file "vccomponents.dat" located in the "%USERPROFILE%\Local Settings\Application Data\Microsoft\VCExpress\8.0" if it exists before restarting Visual C++ Express Edition.

Step 4: Update the corewin_express.vsprops file.

One more step is needed to make the Win32 template work in Visual C++ Express. You need to edit the corewin_express.vsprops file (found in C:\Program Files\Microsoft Visual Studio 8\VC\VCProjectDefaults) and

Change the string that reads:

AdditionalDependencies="kernel32.lib"

to

AdditionalDependencies="kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib"

Step 5: Generate and build a Win32 application to test your paths.

In Visual C++ Express, the Win32 Windows Application type is disabled in the Win32 Application Wizard. To enable that type, you need to edit the file AppSettings.htm file located in the folder %ProgramFiles%\Microsoft Visual Studio 8\VC\VCWizards\AppWiz\Generic\Application\html\1033\".

In a text editor comment out lines 441 - 444 by putting a // in front of them as shown here:

// WIN_APP.disabled = true;
// WIN_APP_LABEL.disabled = true;
// DLL_APP.disabled = true;
// DLL_APP_LABEL.disabled = true;

Save and close the file and open Visual C++ Express.

From the File menu, click New Project. In the New Project dialog box, expand the Visual C++ node in the Product Types tree and then click Win32. Click on the Win32 Console Application template and then give your project a name and click OK. In the Win32 Application Wizard dialog box, make sure that Windows application is selected as the Application type and the ATL is not selected. Click the Finish button to generate the project.

As a final step, test your project by clicking the Start button in the IDE or by pressing F5. Your Win32 application should build and run.

参考译文：

安装之后,您可以立即使用Visual C++ 2005速成版来生成功能强大的.NET Framework 应用程序。若要使用 Visual C++ 速成版生成Win32应用程序，只需采取几个步骤，下面对此进行了详细介绍。

1. 安装 Platform SDK 以便与 Visual C++ 速成版结合使用从 Platform SDK 更新站点的 Platform SDK Update 站点通过 Web 安装 Microsoft Platform SDK。在该页上，单击“Download”（下载），然后确保从列表中依次选择“Windows SDK”和“Core SDK”。

2. 从 Visual Studio 中的“工具”菜单上，选择“选项”。出现“选项”对话框。
从“选项”对话框中，展开“项目和解决方案”节点并选择“VC++ 目录”。在该部分，将以下路径添加到相应的子节：
可执行文件：C:\Program Files\Microsoft SDK\Bin
包含文件：C:\Program Files\Microsoft SDK\include
库文件：C:\Program Files\Microsoft SDK\lib
    注意在您的系统上，Platform SDK 的位置可能有所不同。

3. 更新 corewin_express.vsprops 文件
（位于C:\Program Files\Microsoft Visual Studio 8\VC\VCProjectDefaults 中）

并将以下字符串：

AdditionalDependencies="kernel32.lib"

更改为：

              AdditionalDependencies="kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib"

注意在您的系统上，Visual C++ 速成版可能安装到了不同的位置。

4. 在Visual C++ 速成版,Win32应用程序向导上的Windows 应用程序选项是不可选的,要使用这个选项,你需要修改AppSettings.htm这个文件,它位于"%ProgramFiles%\ Microsoft Visual Studio 8\VC\VCWizards\AppWiz\Generic\Application\html\1033\".

在文本编辑器用"// "符号把文件里的441 - 444这几行注释掉,像下面这样:

// WIN_APP.disabled = true;

// WIN_APP_LABEL.disabled = true;

// DLL_APP.disabled = true;

// DLL_APP_LABEL.disabled = true;

保存和关闭文件,然后打开Visual C++ 速成版.

订阅：博文 (Atom)