[转载]伯努利装错信封问题

原⽂地址：伯努利装错信封问题作者：NINO今天是我⼀次写博客，之所以开这个博客也是受学长的启发，希望借这个博客好好整理⼀下，以后这⾥会有⼀些我认为有帮助的题⽬，有⽔题也有难题（可能对我来说），废话不说，直接说今天这道题。

这道题本质上就是全错排，我想很久都没有头绪，肯能是受装苹果问题的印象，⼀开始我就认为这是⽤递归做，这题⼤概下⼀篇博⽂我就很整理⼀下，受其影响，我认为也应该会是先确定⼀位，再⼀次往下推；

后来在群⾥听⼀些盆友的分析，知道了应该全排列，然后排除⼀些特殊的，怎么全牌呢？有两种思路，⼀个⼤概是放⼀个数组，这个数组表⽰⼀个数字，然后按数字的递增来表⽰全排列，另⼀种就是所谓的算法，显然我⼊了这个坑，，，虽然输出顺序有错，但细细想这个算法还是很赞的，事先声明，回溯法对此题并不受⽤，，，后来⾼中同学给了我⼀个代码，在他的指点下，我写了这个代码

#includeint count=0;

void print(int *,int);void fun(int *,int,int);int main(){ int arry[7]; int n;

scanf(\"%d\ fun(arry,0,n-1); if(count%5==0)

printf(\"s=%dn\ else

printf(\"ns=%dn\ return 0;}

//打印兼排除

void print(int *a,int n){ int i,j,flag=1;//排除⾮错位的 for(i=0;i<=n;i++) if(*(a+i)==i+1){ flag = 0; break; }

//排除重复的

for(i=0;i<=n;i++) for(j=i+1;j<=n;j++) if(*(a+i)==*(a+j)){ flag = 0; break; } if(flag){ count++;

if(count%5!=0){ for(i=0;i

printf(\"%d\ printf(\"%d \ } else{

for(i=0;i

printf(\"%d\

printf(\"%dn\ } }}

void fun(int *a,int index,int n){ if(index==n+1) print(a,n); else{

for(*(a+index)=1;*(a+index)<=n+1;(*(a+index))++) fun(a,index+1,n); }}

后来，⽼师给我⼀个算法，这个算法竟然不⽤递归，简直极好的，#include

int fun(int i,int n){

int a[10],j,k;

for(j=n-1;j>=0;j--) {

a[j]=i; i/=10; }

for(j=0;j {

if(a[j]==j+1) break;

if(a[j]>n||a[j]==0) break; for(k=j+1;k

if(a[j]==a[k]) break; if(k!=n) break; }

if(j==n) return 1; else return 0;}

int main(){

int n,i,s=0,a=1; double b;

scanf(\"%d\ b = n + n*0.1; for(i=0;i a*=10; b*=10; }

for(i=a;i

if(fun(i,n)==1) {

s++;

if(s%5==0) printf(\"%dn\ else printf(\"%d \ }

if(s%5!=0) printf(\"n\"); printf(\"s=%dn\ return 0;

}

其实百度知道也有这个代码，它的⽅法也和第⼀个异曲同⼯，可以说是加强版的；第⼆个思路很赞，但只能说是技巧，

#include#includeint printed;

void draw(int* a,int k){

int i; for(i=0;i {

printf(\"%d\",a[i]); }

printf(\"n\");}

void Settle(int *a,int iStep,int k){

int i; for(i=0;i

if(a[iStep-1]==a[i]) return; if(iStep==k) {

draw(a,k); printed++; }

for(i=1;i<=k;i++) {

if(i==iStep+1) continue; a[iStep]=i;

Settle(a,iStep+1,k); }}

void main(){

int* a; int k;

scanf(\"%d\",&k);

a=(int*)calloc(k,sizeof(int)); Settle(a,0,k);

printf(\"s=%dn\",printed);}

总结：这种递归格式很值得推崇，代码的模块化显然也是这⼏个代码的共同的优势所在，