首页 > ACM题库 > 九度OJ > 九度-1208-10进制 VS 2进制[解题代码]
2013
12-13

九度-1208-10进制 VS 2进制[解题代码]

题目来源:2007年清华大学计算机研究生机试真题

题目描述:

    对于一个十进制数A,将A转换为二进制数,然后按位逆序排列,再转换为十进制数B,我们乘B为A的二进制逆序数。
    例如对于十进制数173,它的二进制形式为10101101,逆序排列得到10110101,其十进制数为181,181即为173的二进制逆序数。

输入:

    一个1000位(即10^999)以内的十进制数。

输出:

    输入的十进制数的二进制逆序数。

样例输入:
173
样例输出:
181

cpp 代码如下:
#include<stdio.h>
#include<string.h>
int main()
{
        int a[1000],b[100000],c[1500],temp[1500],i,j,l,sum,remain,len,flag;//a为原数组,b为二进制,c为转换后,temp为幂次临时数组
        char cccc[1000];
        while(scanf("%s",cccc)!=EOF){memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(temp,0,sizeof(temp));
        l=strlen(cccc);
        for(i=0;i<l;i++)
                a[i]=cccc[i]-'0';
        if(l==1&&a[0]==0){printf("0\n");continue;}
        sum=1;
        len=0;//记录二进制数的位数#3##
        while(sum>0)//计算二进制数
        {
                
                remain=0;//记录除2的余数
                for(i=0;i<l;i++)
                {
                        a[i]+=remain*10;
                        remain=a[i]%2;
                        a[i]=a[i]/2;
                }
                b[len]=remain;
                len++;
                for(i=0,sum=0;i<l;i++)
                        sum+=a[i];
        }
        temp[0]=1;
        for(i=len-1;i>=0;i--)
        {        
                if(b[i])//若该二次项为1 则相加,否则不加
                {
                        for(j=0;j<1500;j++)
                                c[j]+=temp[j];        
                        for(j=0;j<1499;j++)
                        {
                                c[j+1]+=c[j]/10;
                                c[j]=c[j]%10;
                        }
                }
        for(j=0;j<1499;j++)
                        temp[j]=temp[j]*2;
                 for(j=0;j<1499;j++)
                 {
                         temp[j+1]+=temp[j]/10;
                         temp[j]=temp[j]%10;
                 }
        }        
        flag=0;
        for(j=1499;j>=0;j--)
        {
                if(flag==1)
                        printf("%d",c[j]);
                else if(c[j]>0)
                {
                        flag=1;
                        printf("%d",c[j]);
                }
        }
        printf("\n");
        }
        return 1;
}
/**************************************************************
	Problem: 1208
	User: coder
	Language: C++
	Result: Accepted
	Time:130 ms
	Memory:1344 kb
****************************************************************/

java 代码如下:

import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	static String str;
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNext()){
			str = s.next();
			BigInteger b = new BigInteger(str);
			str = new StringBuffer(b.toString(2)).reverse().toString();
			b = new BigInteger(str,2);
			System.out.println(b.toString());
		}
	}

}

/**************************************************************
	Problem: 1208
	User: coder
	Language: Java
	Result: Accepted
	Time:270 ms
	Memory:18636 kb
****************************************************************/


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  3. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环