Problem 11121 Base -2，-2 進位

你沒有看錯，就是 -2 進位，這題是要我們輸入一個 n 值，算出他的 -2 進位為何。例如 n = 7，則輸出 11011。

這題須把握幾個原則，用迴圈以 n 持續 mod -2，而 mod 的值就是要印出的數，再用 -2 除它。當遇 n 為奇數且為負數時，除 -2 後須將值加上 1；當持續除到 n = -1 時，則印出 1，將 n 變為 1；當 n = 1，印出 1，則跳出迴圈。例如 n = -25，
n = -25 為奇數且為負數，mod -2 為 1，印出 1，除 -2 後為 12，需加 1，則 n = 13。
n = 13 mod -2 後為 1，印出 1，除 -2 後為 -6， n = -6。
n = -6 mod -2 為 0，印出 0，除 -2 後為 3， n = 3。
n = 3 mod -2 後為 1，印出 1，除 -2 後為 -1， n = -1。
n = -1 則需先印出 1，再將 n 變為 1。
n = 1 ，印出 1， 跳出迴圈。

所以答案 111011。記住：順序是反的，所以可能需要將這些數字記錄下來。
寫成程式如下：

scanf("%d", &n);
a = n;
while (n --)
{  
    scanf("%d", &m);
    index = 0;
    for (;m != 1 && m != 0;)
    {
        int add = 0;
        if (m < 0 && m % 2) add = 1;
        ans[index ++] = abs(m % -2);
        m /= -2;
        if (add) m ++; 
        if(m == -1) ans[index ++] = 1, m = 1;
          
    }
    if (m == 1) ans[index ++] = 1;
    printf("Case #%d: ", a - n);
    for (i = index - 1; i >= 0; i --)
        printf("%d", ans[i]);
    if (m == 0) printf("%d", 0);    
    printf("\n");
}

By David.K

p11121題目連結
回ACM題庫目錄
回首頁