華師大 OJ 1147

題目連結：點選打開連結

這道題目重點的地方有2個：

1. 因為我們剛學過棧，是以這裡就是實踐棧的好地方了。

2. 因為輸入的整數有32位，是以要自己設計一個BIGINT的struct來存儲這樣的類型，也就是說自己定義一個BIGINT的抽象資料類型，并且提供基本的方法。

這裡我把關于這個整數的資訊都放在了struct裡面，包括他的正負号，位數等等。這裡用到了一個技巧。因為他有一個方法就是高精度除法，這個看起來挺麻煩的。

根據觀察得到，這裡高精度除以單精度中的單精度範圍是[2,36]，是以如果是[2,9]，我就用10進制來存儲BIGINT，否則的話，用100進制來存儲BIGINT，這樣一來，這個DIV方法就永遠都相當于高精度數字除以一個個位數了。

解決方案：

//7:50am-->8:48
#include <stdio.h>
#include <stdlib.h>

enum FLAG{true,false};
typedef struct {
    int cnt;
    int v[700];
} Stack;
typedef struct {
    int cnt;
    int base;
    int negtive;
    int v[32];
} BIGINT;

int DIV(BIGINT * bigint, int r);
void push(Stack * stack,int d);
int pop(Stack * stack);

void solve();

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}


void solve(){
    BIGINT bigint;
    Stack stack;
    char record[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";  //  記錄36個進制的數位
    char str[35];  //因為要用來儲存符号位
    int r;  // r進制
    int k,i;
    scanf("%s %d",str,&r);
    //printf("%s\n%d\n",str,r);
    int tmp;
    bigint.negtive = false;
    if(str[0] == '-'){
        bigint.negtive = true;
        strcpy(str,&str[1]);
        //printf("%s\n",str);
    }
    bigint.cnt = 0;              // initializing bigint
    //把數字讀進大數字類型bigint裡面

    //以10進制的方式存到bigint裡面
    if(2<=r && r <= 9){
            bigint.base = 10;
        for(k=strlen(str)-1;k >= 0;k--){
            bigint.v[bigint.cnt++] = str[k] - '0';
        }
    }

    else if (10 <= r  && r <= 36){
            bigint.base = 100;
        for(k=strlen(str)-1;k >= 0 ; k=k-2){  // k max = strlen - 1.
            if(k==0){
                bigint.v [bigint.cnt++] = str[k]-'0';
            } else{
                bigint.v[bigint.cnt++] = (str[k]-'0') + (str[k-1]  - '0')*10;
            }
        }
    }


    stack.cnt = 0;

    while(bigint.cnt > 0){
        push(&stack,DIV(&bigint,r));   //push,DIV還沒有寫完
    }

    if(bigint.negtive==true){
        printf("-");
    }

    while(stack.cnt>0){
        printf("%c",record[pop(&stack)]);    // pop還沒有寫
    }
    printf("\n");
}

void push(Stack * stack,int d){
    stack->v[stack->cnt++] = d;
}

int pop(Stack * stack){
    if(stack->cnt>0){
        return (stack->v[(stack->cnt--)-1]);
    }
    else return -1;
}



//高精度除以低精度數字,并且傳回餘數
int DIV(BIGINT * bigint,int r){
    int carry;
    int yushu; //餘數
    int k;
    int Base = bigint->base;
    int tmp;
    carry = 0;
    if(bigint->v[bigint->cnt-1] < r){
        carry = bigint->v[(bigint->cnt)-1];
        bigint->cnt--;
    }

    for(k = bigint->cnt-1;k>=0;k--){
        tmp = (bigint->v[k] + carry*Base);
        bigint->v[k] = tmp / r;
        carry = tmp % r;
    }
    return carry;
}