[转载]伯努利装错信封问题_竞赛之路

http://blog.sina.com.cn/u/3639641512

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

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

(2016-12-29 22:40:30)

标签：

转载

原文地址：伯努利装错信封问题作者：NINO

今天是我一次写博客，之所以开这个博客也是受学长的启发，希望借这个博客好好整理一下，以后这里会有一些我认为有帮助的题目，有水题也有难题（可能对我来说），废话不说，直接说今天这道题。

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

后来在群里听一些盆友的分析，知道了应该全排列，然后排除一些特殊的，怎么全牌呢？有两种思路，一个大概是放一个数组，这个数组表示一个数字，然后按数字的递增来表示全排列，另一种就是所谓的算法，显然我入了这个坑，，，虽然输出顺序有错，但细细想这个算法还是很赞的，事先声明，回溯法对此题并不受用，，，

后来高中同学给了我一个代码，在他的指点下，我写了这个代码

#include
int count=0;
void print(int *,int);
void fun(int *,int,int);
int main(){
    int arry[7];
    int n;
    scanf("%d",&n);
    fun(arry,0,n-1);
    if(count%5==0)
        printf("s=%dn",count);
    else
        printf("ns=%dn",count);
    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",*(a+i));
            printf("%d ",*(a+i));
        }
        else{
            for(i=0;i
                printf("%d",*(a+i));
            printf("%dn",*(a+i));
        }
    }
}

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",&n);

    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",i);
            else printf("%d ",i);
        }
    if(s%5!=0) printf("n");
    printf("s=%dn",s);
    return 0;
}

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


#include


#include

int

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);

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

阅读┊ 收藏 ┊转载原文 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：[转载]轨迹方程有妙法,今朝重现蒙日圆

后一篇：解学生提问的一道自主招生题

新浪BLOG意见反馈留言板　欢迎批评指正