| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4195 人关注过本帖
标题:洗牌问题设 2n 张牌分别标记为
只看楼主 加入收藏
hackrol
Rank: 4
来 自:世界和平组织
等 级:业余侠客
帖 子:62
专家分:267
注 册:2014-9-6
结帖率:0
收藏
 问题点数:0 回复次数:4 
洗牌问题设 2n 张牌分别标记为
Description
设2n张牌分别标记为1,2,…,n,n+l,…,2n,初始时这2n张牌按其标号从小到大排列。
经一次洗牌后,原来的排列顺序变成n+l,l,n+2,2,··,,2n,n。
即前n张牌被放到偶数位置2,4,·,·,2n,而后n张牌被放到奇数位置1,3,…,2n-l。
可以证明对于任何一个自然数n,经过若干次洗牌后可恢复初始状态。
编程任务:对于给定的n的值(n<=24000),编程计算最少经过多少次洗牌可恢复到初始状态。
Input
由键盘输入n的值。
输入包含多组数据,每行一个整数N。
Output
程序运行结束时,将计算出的最少洗牌次数在屏幕上输出。
对于输入的N,输出最少需要的洗牌次数。
Sample Input
10
Sample Output
6
程序代码:
#include <stdio.h>
#include <stdlib.h>
#define NO 0
#define YES 1

void xipai(int *p,int n);
int pd(int *p,int n);

int main(void)
{
    int n,*pai,i,flag=NO,count=0;                //flag标记是否回到初始状态
    scanf("%d",&n);
    pai=(int *)malloc(2*n*sizeof(int));
    for(i=0;i<2*n;i++)                            //初始化动态数组
    pai[i]=i;
    while(!flag)                                
    {    
        count++;                                //洗牌次数累计
        xipai(pai,n);
        flag=pd(pai,n);        
    }
    printf("%-5d",count);                        //输出共洗牌几次
    return 0;
}

void xipai(int *p,int n)                        //洗牌
{
    int *tmp=(int *)malloc(2*n*sizeof(int));    //创建临时动态数组
    int i;
    for(i=0;i<2*n;i++)                            
    {
        tmp[i]=p[i%2?(i/2):(n+i/2)];            //洗牌之后的排序
    }
    for(i=0;i<2*n;i++)                            //复制洗牌之后的数进原来数组
    p[i]=tmp[i];
    free(tmp);                                    //释放临时动态数组
}

int pd(int *p,int n)                            //判断是否回到原点
{
    int i;
    for(i=0;i<2*n-1;i++)
    {
        if(p[i+1]!=p[i]+1)break;                //如果不满足后面一个数是前一个数+1就退出
    }
    return i==2*n-1?YES:NO;                        //根据跳出循环时i的大小来判断是否回到原点
}
搜索更多相关主题的帖子: 自然数 键盘 
2014-10-25 15:06
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
很奇怪为什么你的帖子都没有分给大家?也看不出你是在提问,还是在展示代码。

至少在这里你的代码对于题目一不满足输入输出格式,二效率很低估计也不能满足时间限制。

重剑无锋,大巧不工
2014-10-25 19:32
hackrol
Rank: 4
来 自:世界和平组织
等 级:业余侠客
帖 子:62
专家分:267
注 册:2014-9-6
收藏
得分:0 
回复 2 楼 beyondyf
有好的算法分享下不??我只是在练手!有人能看出其中的BUG和问题,我自己看不出来!你说展示也可以啊.共享就是我的精神!而且 我不是在做题,只是实现这样的功能!oj的限制太多了!我也不知道怎么去讨好它!只要实现功能就好了.练手.才自学两个多月,打代码就是我现在唯一也必须要做的事!,欢迎各位惊人算法!希望大家把算法公开化!
2014-10-25 20:14
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
那你看看这个吧。ACM本来就是种极限编程。
程序代码:
#include <stdio.h>
int main()
{
    int n, x, c;
    for(; scanf("%d", &n) != EOF; printf("%d\n", c))
    for(c = x = 1; (x = x>n ? (x-n)*2-1 : x*2) - 1; c++);
    return 0;
}

重剑无锋,大巧不工
2014-10-25 21:39
hackrol
Rank: 4
来 自:世界和平组织
等 级:业余侠客
帖 子:62
专家分:267
注 册:2014-9-6
收藏
得分:0 
回复 4 楼 beyondyf
感谢,我看懂了你的算法 了,你是只追踪第一张牌的位置,只有当他在第n+1的位置时下一次才会回到初始位置.你并没有考虑其他牌的位置,因为他们都是相关的,位置不会乱.

十分感谢你的算法!
2014-10-26 04:17
快速回复:洗牌问题设 2n 张牌分别标记为
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015131 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved