華師大 OJ 3031

題目連結：點選打開連結

值得一提的是，我覺得這道題目是我第一次完全靠自己的力量，按照資料結構的思路做出來的。

其實換成資料結構+算法的思路在用C語言來解決問題還是能簡化思考的複雜度。

因為人的腦子很笨，無法一下子解決一團問題，需要将其分解。

那麼設計好這裡的資料結構，其實運作在資料結構上的算法也是非常的重要的。正是有了那些小小的配套的方法，才讓思考的過程顯得格外的清晰。

解決方案

/******************************************************************************/
/*                                                                            */
/*  DON'T MODIFY main() function anyway!                                      */
/*                                                                            */
/******************************************************************************/
#include <stdio.h>
#include <string.h>
//把個位數放在v[0],十位數放在v[1]
//特殊資料：資料0，表示為{0,{0}},
typedef struct {
    int cnt;
    int v[101];
} BIGINT;

void solve(); /* write function solve() to process one case of the problem    */
void init(){}
void ADD01(BIGINT *n,int bin);
void MUL2(BIGINT *n);
void DIV2(BIGINT * n);


int main()
{  int i,t; init();
   scanf("%d\n",&t);
   for (i=0;i<t;i++)
   { printf("case #%d:\n",i);
     solve();
   }
   return 0;
}

//1. 十進制n-->二進制數bin
//2. 二進制bin倒置-->binReverse
//3. binReverse-->倒置
//要自己設計大整數類型

void solve(){  //10
    char str[102];
    int bin[334];
    int countBin;
    int flag;
    BIGINT n;
    int i;
    scanf("%s",str);
    if(strlen(str)==1 && str[0] == '0'){ printf("0\n");return;}
    for(i=0;i<strlen(str);i++){
        n.v[i] = str[strlen(str) - 1 -i]-'0';
    }
    n.cnt = strlen(str);
    countBin = 0;
    while(n.cnt>0){
        bin[countBin++] = n.v[0] % 2;   //bin[0]存放的是原本的二進制的最低位
        DIV2(&n);                       //bin一共有countBin個二進制位，位bin[0],bin[1],...,bin[countBin-1]
    }
    flag = 0;

    for(i=0;i < countBin;i++){
        if(bin[i] != 0)   break;
    }


    flag = countBin-1;
    while(flag){
        if(bin[flag]!=0){
            break;
        }
        else flag--;
    }
    for(;i <=flag ;i++){
        MUL2(&n);
        ADD01(&n,bin[i]);
    }


    for(i=0;i<n.cnt-1;i++){
        printf("%d",n.v[n.cnt - 1 - i]);
    }
    printf("%d\n",n.v[n.cnt - 1 - i]);
}

//大整數加0 or 1
//大整數乘以2
//大整數除以2

void ADD01(BIGINT *n,int bin){
    int i;
    int t;
    int carry;
    if(bin!=0){  //bin == 1
        if(n->cnt == 0) n->cnt=1,n->v[0] = 1;
        else{
            carry = bin;
            for(i=0;i < n->cnt; i++){
                t = n->v[i] + carry;
                n->v[i] = t % 10;
                carry = t / 10;
            }
            if(carry>0){
                n->v[n->cnt++] = carry;
            }
        }
    }
}

void MUL2(BIGINT *n){
    int i;
    int t;
    int carry;
    if(n->cnt != 0){
        carry = 0;
        for(i=0;i<n->cnt;i++){
            t = n->v[i] * 2  + carry;
            n->v[i] = t % 10;
            carry = t / 10;
        }
        if(carry>0){
            n->v[n->cnt++] = carry;
        }
    }
}

void DIV2(BIGINT * n){ //  {2,{3,4} }
    int i;
    int t;
    int cnt = n->cnt;
    int carry;
    if(n->v[n->cnt-1] == 1){
        carry = 1;
        n->cnt--;
    } else{
        t = n->v[n->cnt-1];
        n->v[n->cnt-1] = t / 2;
        carry = t % 2;
    }

    for(i=cnt-2;i>=0;i--){
        t = ( n->v[i] + carry*10 );
        n->v[i] = t / 2;
        carry = t % 2;
    }
}