华师大 OJ 1147

    xiaoxiao2021-03-26  15

    题目链接:点击打开链接

    这道题目重点的地方有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; }

    转载请注明原文地址: https://ju.6miu.com/read-600247.html

    最新回复(0)