首页 > ACM题库 > HDU-杭电 > hdu 2169 Geek Challenge [SKRZAT] (Base Minus Two)[解题报告]C++
2013
12-30

hdu 2169 Geek Challenge [SKRZAT] (Base Minus Two)[解题报告]C++

Geek Challenge [SKRZAT] (Base Minus Two)

问题描述 :

Problem F: Geek Challenge [SKRZAT] (Base Minus Two)
Geek Challenge [SKRZAT] is an old, old game from Poland that uses a game console with two buttons plus a joy stick. As is true to its name, the game communicates in binary, so that one button represents a zero and the other a one. Even more true to its name, the game chooses to communicate so that the base of the number system is minus two, not plus two, so we’ll call this representation “Weird Binary”. Thus the bit positions label the powers of minus two, as seen in the following five-bit tables:

Numbers are presented on the screen in Weird Binary, and then numbers are accepted in response from the console as a stream of zeroes and ones, terminated by a five-second pause.
You are writing a computer program to support the novice geek in playing the game by translating numbers between decimal and Weird Binary.

输入:

The first line in the file gives the number of problems being posed without any white space. Following are that many lines. Each line will either be a conversion into Weird Binary or out of Weird Binary: the letter “b” indicates that the rest of the line is written in Weird Binary and needs to be converted to decimal; the letter “d” indicates that the rest of the line is written in decimal and needs to be converted to Weird Binary.
The input data are in the range to fit within a 15-bit Weird Binary number, which represents the decimal number range �10922 to 21845, inclusive.

输出:

The first line in the file gives the number of problems being posed without any white space. Following are that many lines. Each line will either be a conversion into Weird Binary or out of Weird Binary: the letter “b” indicates that the rest of the line is written in Weird Binary and needs to be converted to decimal; the letter “d” indicates that the rest of the line is written in decimal and needs to be converted to Weird Binary.
The input data are in the range to fit within a 15-bit Weird Binary number, which represents the decimal number range �10922 to 21845, inclusive.

样例输入:

10
b 1001101
b 0111111
b 101001000100001
b 010010001000010
b 100110100110100
d -137
d 137
d 8191
d -10000
d 21000

样例输出:

From binary: 1001101 is 61
From binary: 0111111 is -21
From binary: 101001000100001 is 19937
From binary: 010010001000010 is -7106
From binary: 100110100110100 is 15604
From decimal: -137 is 10001011
From decimal: 137 is 110011001
From decimal: 8191 is 110000000000011
From decimal: -10000 is 10100100110000
From decimal: 21000 is 101011000011000

#include<stdio.h>
#include<string.h>
int main()
{
 int n,i,j,k,sum,len,q,w = 1,p;
 char c,a[16];
 scanf("%d",&n);
 while(n--)
 {
  getchar();
  scanf("%c ",&c);
  if(c=='b')
  {
   k=1;
   sum=0;
   scanf("%s",a);
   len=strlen(a);
   for(i=len-1;i>=0;i--)
   {
    sum=sum+(a[i]-'0')*k;
    k=-2*k;
   }
   printf("From binary: %s is %d\n", a, sum);
  }
  else if(c=='d')
  {
   scanf("%d",&p);
   i=0;
   q=p;
   if(p==0){printf("From decimal: 0 is 0\n");continue;}
   while(p!=0)
   {
    a[i++]=p%(-2);
    p=p/(-2);
    if(a[i-1]==-1)
    {
     a[i-1]=1;
     if(p<0)p--;
     else p++;
    }
   }
   printf("From decimal: %d is ",q);
   for(j=i-1;j>=0;j--)
    printf("%d",a[j]);
   printf("\n");
  }
 }
 return 0;
}

 


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)