worm

为什么我的眼里饱含泪水?因为我程序没写完!
随笔 - 5, 文章 - 2, 评论 - 10, 引用 - 0
数据加载中……

poj 3191解题报告

The Moronic Cowmpouter
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 1344 Accepted: 676

Description

Inexperienced in the digital arts, the cows tried to build a calculating engine (yes, it's a cowmpouter) using binary numbers (base 2) but instead built one based on base negative 2! They were quite pleased since numbers expressed in base −2 do not have a sign bit.

You know number bases have place values that start at 1 (base to the 0 power) and proceed right-to-left to base^1, base^2, and so on. In base −2, the place values are 1, −2, 4, −8, 16, −32, ... (reading from right to left). Thus, counting from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.

Eerily, negative numbers are also represented with 1's and 0's but no sign. Consider counting from −1 downward: 11, 10, 1101, 1100, 1111, and so on.

Please help the cows convert ordinary decimal integers (range -2,000,000,000..2,000,000,000) to their counterpart representation in base −2.

Input

Line 1: A single integer to be converted to base −2

Output

Line 1: A single integer with no leading zeroes that is the input integer converted to base −2. The value 0 is expressed as 0, with exactly one 0.

Sample Input

-13

Sample Output

110111

Hint

Explanation of the sample:

Reading from right-to-left:
1*1 + 1*-2 + 1*4 + 0*-8 +1*16 + 1*-32 = -13
 题目的意思就是让你把一个数转换为-2进制,
基本原理:
               如果n为奇数,那么末位肯定为1,因此就可以转为求(x-1)/-2 的子问题了! (除以-2可以类比十进制就能理解了)
               如果n为偶数,末位必为0,然后再转为求x/-2的子问题;
结束条件当 n=1。
思路很简单,但是有两个小方面要提提,一定要考虑n=0的情况,我就是没考虑而一直超时,郁闷,还找不出错误,陷入了死循环怪不得超时,还有注意球的结果是逆序的!!呵呵下面是代码:
 1//============================================================================
 2// Name        : poj 3191.cpp
 3// Author      : worm
 4// Copyright   : Your copyright notice
 5// Description :把一个十进制的数转换为-2进制的数
 6//============================================================================
 7
 8#include <iostream>
 9#include <stdio.h>
10#include <string>
11#include <math.h>
12using namespace std;
13string a= "";
14int main() {
15    int x;
16    cin >> x;
17    if (x == 0{
18        cout <<"0"<<endl;
19        return 0;
20    }

21
22    while (x != 1{
23        if (abs(x) % 2 == 1{
24            a += '1';
25            x = (x-1)/-2;
26            continue;
27        }

28        a += '0';
29        x /= -2;
30    }

31    cout <<"1";
32    for (int i = a.length() - 1; i >= 0; i--{
33        printf("%c",a[i]);
34    }

35
36    return 0;
37}

38

posted on 2009-03-08 12:37 WORM 阅读(1007) 评论(1)  编辑 收藏 引用

评论

# re: poj 3191解题报告  回复  更多评论   

已阅 删之
2009-03-08 20:24 | cppexplore

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理