| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1894 人关注过本帖, 1 人收藏
标题:一道关于二进制的算法题,~~~求实现代码
只看楼主 加入收藏
LeslieCh
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2013-11-27
结帖率:77.78%
收藏(1)
已结贴  问题点数:20 回复次数:23 
一道关于二进制的算法题,~~~求实现代码
4122: No_stop玩硬币
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 268  Solved: 27

Description
No_stop特别喜欢玩硬币, 而且是他只喜欢自己一个人玩。第一次玩,他会把一些硬币排成一排,硬币要么是正面朝上(看成是1)要么是反面朝上(看成0),那么这样会产生一个二进制数(设为数a),No_stop会把它记录下来。他觉得玩一次不过瘾,所以会玩很多次,以后他每次玩会重新拿一些硬币重新排列,他要求每次硬币正面朝上的个数与上一次保持不变,由于他有很强很强的强迫症,他必须让产生数a越来越大,而且要让两次产生的数的差值尽可能小。现在给你No_stop第一次的硬币排列,问你他第二次玩的硬币排列是多少?


Input
第一行输入一个组数T(T<= 30),对于每一组测试数据,输入一个“01”序列(1<=长度<= 10),且 序列的第一个数字不为0。


Output
对于每组测试数据,输出一个“01”序列。


Sample Input
1
1010101

Sample Output
1010110

HINT

Source
Jiong King



搜索更多相关主题的帖子: Memory 强迫症 二进制 而且 记录 
2013-12-18 09:40
LeslieCh
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2013-11-27
收藏
得分:0 
简单的思路是,把产生的二进制数不断加1,知道与上一个二进制数中的1数量相同,,可以要怎么实现呀~~~?求教
2013-12-18 09:41
LeslieCh
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2013-11-27
收藏
得分:0 
我写的错误代码(只有题目测试数据能对,用1,111,100都不对),新人乱写的,求个正确的代码
#include<stdio.h>
#include<string.h>
int main()
{
    int T,j,i,k,q,n,count,recount,flag,w;
    char b[10],a[10];
    scanf("%d",&T);
    getchar();
    for(j=0;j<T;j++)
    {
        gets(b);
        n=strlen(b);
        q=0;count=0;recount=0;
        memset(a,0,sizeof(a));
        for(i=n-1;i>=0;i--)//zhuan zhi
        {
            if(b[i]=='1')
            {count++;}
            a[q]=b[i];
            q++;
        }
        flag=0;
         while(count!=0)
 {
     i=0;
     while(a[i]>='0')//mei ci jia 1
            {
                a[i]+=1;
                if(i>n-1)
                {
                     for(k=0;k<10;k++)
                    {
                        if(a[k]=='1')
                        {recount++;}
                    }
                    if(recount==count)
                    {flag=1;}
                    break;
                }
                if(a[i]>'1')
                {
                    a[i]='0';
                    i++;
                }
                else
                {
                    for(k=0;k<10;k++)//tong ji bu fen
                    {
                        if(a[k]=='1')
                        {recount++;}
                    }
                    if(recount==count)
                    {flag=1;break;}
                }
            }
            if(flag==1)
            {break;}
}
        q=0;
        for(i=9;i>=0;i--)//zhuan zhi
        {
            b[q]=a[i];
            q++;
        }
        for(i=0;i<10;i++)//zhao dao di yi ge '1'
        {
            if(b[i]=='1')
            {w=i;
             break;}
        }
        for(i=w;i<10;i++)//shu chu
        {
            printf("%c",b[i]);
        }
        printf("\n");
    }
    return 0;
}
      
2013-12-18 09:43
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:0 
我来教你一个排序组合的算法吧,也就是std::next_permutation算法的简化:

先读入“01”序列,并在最前面补上一个0,得到 0abcdefghij
从后向前遍历,找到第一个1的位置i,并把a[i]设为0
从i-1向前遍历,找到第一个0的位置j,并把a[j]设为1
将j之后的序列反序一下


[ 本帖最后由 rjsp 于 2013-12-18 10:55 编辑 ]
2013-12-18 10:22
loveClangage
Rank: 8Rank: 8
来 自:广东云浮
等 级:蝙蝠侠
帖 子:326
专家分:891
注 册:2013-8-23
收藏
得分:0 
最好求算法,自己实现,

编写的程序,不能改变世界,却可以改变自己...
2013-12-18 10:26
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:10 
回复 4楼 rjsp
供参考,我也不知道对不对

程序代码:
#include <stdio.h>
#include <string.h>

int main()
{
    unsigned t;
    scanf( "%u", &t );
    for( ; t; --t )
    {
        char a[12] = "0"; // 首部补一个'0'是为了确保不需要增加位数
        scanf( "%s", a+1 );

        size_t n = strlen(a);

        // 从后向前遍历,找到第一个1的位置i,并把a[i]设为0
        size_t i = n-1;
        for( ; a[i]=='0'; --i );
        a[i] = '0';

        // 从i-1向前遍历,找到第一个0的位置j,并把a[j]设为1
        size_t j = i-1;
        for( ; a[j]=='1'; --j );
        a[j] = '1';

        // 将j之后的序列反序一下
        for( size_t k=j+1; k<n-k+j; ++k )
        {
            char tmp = a[k];
            a[k] = a[n-k+j];
            a[n-k+j] = tmp;
        }

        printf( "%s\n", a[0]=='0' ? a+1 : a );
    }

    return 0;
}

2013-12-18 11:00
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
找到串中最后一个 ‘01’序列,替换为‘10’即可,如果找不到,说明已经是最大(X)

想当然了,楼上的逆序也不对,应该是移动,把 j之后所有的 ‘1’移到最后

[ 本帖最后由 azzbcc 于 2013-12-18 14:37 编辑 ]


[fly]存在即是合理[/fly]
2013-12-18 14:21
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:0 
以下是引用azzbcc在2013-12-18 14:21:29的发言:
把 j之后所有的 ‘1’移到最后
j之后一定是 1……1 0……0 这种形式
1…(a个1)…1 0…(b个0)…0 变为 0…(b个0)…0 1…(a个1)…1 就是逆序
当然,你也可以将之看成是将1移动到最后(即“排序”)。

标准排列组合算法中,使用“逆序”,而不是“排序”,因为j之后的序列一定是从大到小有序的,“逆序”就如同“排序”,并且执行效率更高。
2013-12-18 16:05
so_love
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:蒙面侠
威 望:7
帖 子:812
专家分:4151
注 册:2013-11-25
收藏
得分:0 
观摩。。。

一花一世界、一叶一追寻、片片花叶落、情系何人身。
2013-12-18 16:10
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
回复 8楼 rjsp
向 R 版学习,此题考虑不周全。


[fly]存在即是合理[/fly]
2013-12-18 16:35
快速回复:一道关于二进制的算法题,~~~求实现代码
数据加载中...
 
   



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

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