我们都知道

编号为 1 ， 2 ，……， n 的 n
个元素排成一列，若每个元素所处位置的序号都与它的编号不同，则称这个排列为 n
个不同元素的一个错排。记 n 个不同元素的错排总数为 f(n) ，则

f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]（ 1 ）

本文从另一角度对这个问题进行一点讨论。

1. 一个简单的递推公式

n 个不同元素的一个错排可由下述两个步骤完成：

第一步，“错排” 1 号元素（将 1 号元素排在第 2 至第 n 个位置之一），有 n – 1
种方法。

第二步，“错排”其余 n – 1 个元素，按如下顺序进行。视第一步的结果，若 1
号元素落在第 k 个位置，第二步就先把 k 号元素“错排”好， k
号元素的不同排法将导致两类不同的情况发生：（ 1 ） k 号元素排在第 1
个位置，留下的 n – 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2)
种方法；（ 2 ） k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k
个位置，于是形成（包括 k 号元素在内的） n – 1 个元素的“错排”，有 f(n – 1)
种方法。据加法原理，完成第二步共有 f(n – 2)+f(n – 1) 种方法。

根据乘法原理， n 个不同元素的错排种数

f(n) = (n-1)[f(n-2)+f(n-1)] (n>2) 。 （ 2 ）

————————-

下面通过这个递推关系推导通项公式:
为方便起见，设M(k)=k!N(k), (k=1,2,…,n)
则N(1)=0,N(2)=1/2
n>=3时,n!N(n)=(n-1)(n-1)!N(n-1)+(n-1)!N(n-2)
即 nN(n)=(n-1)N(n-1)+N(n-2)
于是有N(n)-N(n-1)=-[N(n-1)-N(n-2)]/n=(-1/n)[-1/(n-1)][-1/(n-2)]…(-1/3)[N(2)-N(1)]=(-1)^n/n!
因此
N(n-1)-N(n-2)=(-1)^(n-1)/(n-1)!
N(2)-N(1)=(-1)^2/2!
相加，可得
N(n)=(-1)^2/2!+…+(-1)^(n-1)/(n-1)!+(-1)^n/n!
因此
M(n)=n![(-1)^2/2!+…+(-1)^(n-1)/(n-1)!+(-1)^n/n!]
可以得到
错排公式为M(n)=n!(1/2!-1/3!+…..+(-1)^n/n!)
此外也可以用容斥原理证明:
正整数1、2、3、……、n的全排列有n!种，其中第k位是k的排列有（n-1)!，当k取1、2、3、……、n时，共有n*（n-1)!种排列，由于是错排，这些排列应排除，但是此时把同时有两个以上的数不错排的排列多排除了一次，应补上；在补上时，把同时有三个以上的数不错排的排列多补上了一次，应排除；……；继续这一过程，得到错排的排列种数为
M(n)=n!-n!/1!+n!/2!-n!/3!+…+(-1)^n*n!/n!=sigma(k=2~n) (-1)^k*n!/k!
即M(n)=n![1/0!-1/1!+1/2!-1/3!+1/4!+..+(-1)^n/n!]
注:sigma表示连加符号,(k=2~n)是连加的范围

另外：书上的错排公式为Dn=n!(1-1/2!+1/3!-…..+(-1)n/n!),此公式算n很大时就很不方便．后来发现它可以化简为１个优美的式子Dn=[n!/e+0.5],[x]为取整函数．
公式证明较简单．观察一般书上的公式，可以发现e-1的前项与之相同，然后作比较可得/Dn-n!e-1/<1/(n+1)<0.5,于是就得到这个简单而优美的公式

A vector is a collection of objects of a single type, each of which has an associated integer index. As with strings, the library takes care of managing the memory associated with storing the elements. We speak of a vector as a container because it contains other objects. All of the objects in a container must have the same type. We’ll have much more to say about containers in Chapter 9.

vector 是同一种类型的对象的集合，每个对象都有一个对应的整数索引值。和 string 对象一样，标准库将负责管理与存储元素相关的内存。我们把 vector称为容器，是因为它可以包含其他对象。一个容器中的所有对象都必须是同一种类型的。我们将在第九章更详细地介绍容器。

To use a vector, we must include the appropriate header. In our examples, we also assume an appropriate using declaration is made:

使用 vector 之前，必须包含相应的头文件。本书给出的例子，都是假设已作了相应的 using 声明：

     #include <vector>
     using std::vector;

A vector is a class template. Templates let us write a single class or function definition that can be used on a variety of types. Thus, we can define a vector that holds strings, or a vector to hold ints, or one to hold objects of our own class types, such as Sales_items. We’ll see how to define our own class templates in Chapter 16. Fortunately, we need to know very little about how templates are defined in order to use them.

vector 是一个类模板（class template）。使用模板可以编写一个类定义或函数定义，而用于多个不同的数据类型。因此，我们可以定义保存 string对象的 vector，或保存 int 值的 vector，又或是保存自定义的类类型对象（如 Sales_items 对象）的 vector。将在第十六章介绍如何定义程序员自己的类模板。幸运的是，使用类模板时只需要简单了解类模板是如何定义的就可以了。

To declare objects of a type generated from a class template, we must supply additional information. The nature of this information depends on the template. In the case of vector, we must say what type of objects the vector will contain. We specify the type by putting it between a pair of angle brackets following the template’s name:

声明从类模板产生的某种类型的对象，需要提供附加信息，信息的种类取决于模板。以 vector 为例，必须说明 vector 保存何种对象的类型，通过将类型放在类型放在类模板名称后面的尖括号中来指定类型：

     vector<int> ivec;               // ivec holds objects of type int
     vector<Sales_item> Sales_vec;   // holds Sales_items

As in any variable definition, we specify a type and a list of one or more variables. In the first of these definitions, the type is vector<int>, which is a vector that holds objects of type int. The name of the variable is ivec. In the second, we define Sales_vec to hold Sales_item objects.

和其他变量定义一样，定义 vector 对象要指定类型和一个变量的列表。上面的第一个定义，类型是 vector<int>，该类型即是含有若干 int 类型对象的vector，变量名为 ivec。第二个定义的变量名是 Sales_vec，它所保存的元素是 Sales_item 类型的对象。

阅读全文…

比较著名的网络相册有Google Picasa及雅虎的Flickr等，但是这两个支持外链的且外链图片不加水印的网络相册在国内都无法访问或者访问不稳定。而国内的一些网络相册，很少有提供免费外链服务的，即使有免费的，也会被在图片上加上水印。如何找到让人满意的支持外链、无水印且访问稳定的网络相册呢？

众里寻她千百度，蓦然回首，那相册却在photobucket.com处。在Photobucket上可以上传，共享，连接并找到照片，影片，和图形。photobucket还提供免费工具，为使幻灯片的照片，影片与音乐。我们可以通过电子邮件，即时通讯和移动电话分享我们的照片及影片。截止在Alexa.com上Photebucket.com的网站排名是全球就53位：

Photobucket为免费用户提供500M的容量及每个月10G的访问流量。对于一般的个人博客，这个的容量和流量应该是完全够用的了。实在不够用，就多申请几个账户。

从Photobucket外部链接出来的图片，访问速度非常不错。本博客的所有图片也都是放在Photobucket，速度很稳定。而且Photobucket提供的外链图片不会加水印，这点是非常棒的。除此之外，相比Picasa与Flickr，Photobucket最大的优点就是访问稳定，不用担心某一天寄放在这里的外链图片突然无法显示了。

打下photobucket.com的主页如下图所示：

photobucket提供多种尺寸的图片供外部链接使用：

提供多种外部链接方式，如果是贴粘到个人博客，使用“HTML Code”就可以了

除此之外，Photobucket还提供了许多其他实用的图片处理功能，这里就不啰嗦了。赶紧去注册一个账户，慢慢研究吧。

5.       数据的查找（包括判定这个关键字是否在map中出现）
在这里我们将体会，map在数据插入时保证有序的好处。
要判定一个数据（关键字）是否在map中出现的方法比较多，这里标题虽然是数据的查找，在这里将穿插着大量的map基本用法。
这里给出三种数据查找方法
第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了
第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器，程序说明

阅读全文…