递推、错排公式-白红宇

递推、错排公式

阅读量：4074 次

发布时间：2019-05-25

本文共 1969 字，大约阅读时间需要 6 分钟。

以前刚接触ACM时做11页，有挺多题不懂的。最近据某人说校纳新赛和杭电11页差不多，于是顺便又回来补上，收获不少，对递推有了更深的理解.

Solved	Pro.ID	Title	Author	Source	(AC/Submit)Ratio
	2044				(/)36.84%
	2045				(/)39.69%
	2046				(/)48.06%
	2047				(/)46.79%
	2048				(/)42.51%
	2049				(/)37.94%
	2050				(/)70.31%

#include
   
    #define MAXN 52__int64 arr[MAXN];int main(){    int n,i;     arr[1]=3,arr[2]=6,arr[3]=6;     for(i=4; i

#include
   
    #define MAXN 52__int64 f[MAXN];int main(){     int i,n;    f[0]=0, f[1]=1, f[2]=2;    for(i=3; i

/*对于一串字符，分为两种情况：(1) 不以O结尾的， 如EF，那么它接下来有三种情况: EFF、EFE、EFO	注意，有两个是不以O结尾的，一个是以O结尾的(2) 以O结尾的，如EO,那么它接下来只有两种情况， EOF、EOE。	且这两种情况都不以O结尾那么可以推导出，对于某一次的情况，它以O结尾的个数是，上一次不以O结尾的个数不以O结尾的个数是上一次 “不以O结尾的”的两倍 加上上次 “以O结尾的”的两倍。可以得出递推方程f1[i] = f2[i-1];              // f1保存以O结尾的个数f2[i] = f1[i-1]*2+f2[i-1]*2;  // f2保存不以O结尾的个数得出了这两个，总数也自然就求出来了f[i] = f1[i]+f2[i];  // f保存总数*/#include
   
    #define MAXN 52__int64 f[MAXN],f1[MAXN],f2[MAXN];int main(){    int n,i;    f1[1]=1,f2[1]=2,f[1]=3;    // f1为以 O 结尾的个数，f2为以E、F结尾的个数    for(i=2; i<=40; ++i){        f1[i] = f2[i-1];            f2[i] = f1[i-1]*2+f2[i-1]*2;        f[i] = f1[i]+f2[i];    }    while(scanf("%d",&n)==1){        printf("%I64d\n",f[n]);    }        return 0;}

错排公式（1462,2048，2049）：

某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。

分析思路：

1、当N=1和2时，易得解～，假设F(N-1)和F(N-2)已经得到，重点分析下面的情况：

2、当有N封信的时候，前面N-1封信可以有N-1或者 N-2封错装

3、前者，对于每种错装，可从N-1封信中任意取一封和第N封错装，故=F(N-1)*(N-1)

4、后者简单，只能是没装错的那封和第N封交换信封，没装错的那封可以是前面N-1封中的任意一个，故= F(N-2) * (N-1)

基本形式：d[1]=0; d[2]=1
递归式：d[n]= (n-1)*( d[n-1] + d[n-2])

这就是著名的错排公式。

/*错排公式全部抽错的概率，即全部排错的情况个数除与的全排列个数*/#include
    
     #define MAXN 52__int64 f[MAXN],f1[MAXN],f2[MAXN];double ans[MAXN];int main(){    int C,n,i;    f[1]=0,f[2]=1;    __int64 sum=2;    ans[2]=0.5;    for(i=3; i<=20; ++i){        sum *= i;        f[i] = (i-1)*(f[i-1]+f[i-2]);        ans[i] = f[i]*1.0/sum;    }    scanf("%d",&C);    while(C--){        scanf("%d",&n);        printf("%.2f%%\n",ans[n]*100);    }      return 0;}

—— 生命的意义，在于赋予它意义。

原创

， By D_Double

转载地址：http://fuzni.baihongyu.com/

你可能感兴趣的文章

Unity3D普通开发人员，U3D主程分别需要掌握的技能