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= "";
14
int 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