2015NOIP普及组初赛

 二、问题求解

1.重新排列1234使得每一个数字都不在原来的位置上，一共有（         ）种排法。

拿到试卷，看到这题我就想到之前用错排公式做过这样的题，就是想不起来错排公式。只有四个数，可以采用手工排的方式。

1234

2143

2413

3142

3412

3421

4132

4312

4321

答案是：9 。

如果用程序代码来解决这道题，又该如何来解决呢？查询相关资料，下面这段解释比较清晰。

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位置为元素，可以放到1位置中),于是形成（包括 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) 。

  

#include

#include

 long long cp(int); //定义函数 

using namespace std;

int main()

{ int a;

long long b;

cin>>a;

b=cp(a);

cout<<b;

} 

long long cp(int a)

{

if (a==1) return 0;//只有一个数的情况

if (a==2) return 1;//两个数，只有一种排法

return (a-1)*(cp(a-1)+cp(a-2));

// 第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；

//第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；

//综上得到

//D(n) = (n-1) [D(n-2) + D(n-1)]

//特殊地，D(1) = 0, D(2) = 1.

}