Problem D
Base -2
Input: Standard Input

Output: Standard Output

 

Scott Adams

Everyone knows about base-2 (binary) integers and base-10 (decimal) integers, but what about base -2? An integer n written in base -2 is a sequence of digits (b_i), writen right-to-left. Each of which is either 0 or 1 (no negative digits!), and the following equality must hold.

n = b₀ + b₁(-2) + b₂(-2)² + b₃(-2)³ + ...

The cool thing is that every integer (including the negative ones) has a unique base--2 representation, with no minus sign required. Your task is to find this representation.

Input
The first line of input gives the number of cases, N (at most 10000). N test cases follow. Each one is a line containing a decimal integer in the range from -1,000,000,000 to 1,000,000,000.

Output
For each test case, output one line containing "Case #x:" followed by the same integer, written in base -2 with no leading zeros.

Sample Input                       Output for Sample Input

4 1 7 -2 0

Case #1: 1 Case #2: 11011 Case #3: 10 Case #4: 0

---

作法 : 遞迴

#include<stdio.h>
#include<stdlib.h>
void Base_2(int n) {
    if(n > 0) {
        Base_2(n/(-2));
        printf("%d", n%2);
    }
    if(n < 0) {
        Base_2(n/(-2)+(n%(-2) != 0));
        printf("%d", abs(n%(-2)));
    }
}
int main() {
    int t, C = 0, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        printf("Case #%d: ", ++C);
        if(n == 0)    puts("0");
        else Base_2(n), puts("");
    }
    return 0;
}