Uva 10494 – If We Were a Child Again(大数相除）
Problem CIf We Were a Child AgainInput: standard inputOutput: standard outputTime Limit: 7 seconds
“Oooooooooooooooh!If I could do the easy mathematics like my school days!!I can guarantee, that I’d not make any mistake this time!!”Says a smart university student!!But his teacher even smarter – “Ok! I’d assign you such projects in your software lab. Don’t be so sad.”“Really!!” – the students feels happy. And he feels so happy that he cannot see the smile in his teacher’s face.
The Problem The first project for the poor student was to make a calculator that can just perform the basic arithmetic operations. But like many other university students he doesn’t like to do any project by himself. He just wants to collect programs from here and there. As you are a friend of him, he asks you to write the program. But, you are also intelligent enough to tackle this kind of people. You agreed to write only the (integer) division and mod (% in C/C++) operations for him. InputInput is a sequence of lines. Each line will contain an input number. One or more spaces. A sign (division or mod). Again spaces. And another input number. Both the input numbers are non-negative integer. The first one may be arbitrarily long. The second number n will be in the range (0 < n < 231).
OutputA line for each input, each containing an integer. See the sample input and output. Output should not contain any extra space. Sample Input110 / 10099 % 102147483647 / 21474836472147483646 % 2147483647 Sample Output1912147483646
1 #include<stdio.h> 2 #include<string.h> 3 #define MAXN 1002 4 int a[MAXN], c[MAXN], last[MAXN]; // a是存储整型的被除数，c是存储得数，last存储的是每次相除后（其实是相减）的余数5 char s[MAXN]; //存储输入的被除数67 int dealb(int (*b)[20], char *d) 8 {// 求出 除数*n 的每个值并存于数组b中(n = 1 2 3 4 ….. 9)9int len = strlen(d), i, j, e, temp, t; 10for(i=0; i<len; ++i) 11for(j=1; j<10; ++j) 12b[j][i+1] = d[len-1-i] – ‘0’; 13b[1][0] = len; 14 15for(i=2; i<10; i++) 16{//大数相乘 17e = 0; 18for(t=1; t<len+1; ++t) 19{ 20temp = i*b[i][t] + e; 21b[i][t] = temp%10; 22e = temp/10; 23} 24if(e) b[i][t++] = e; 25b[i][0] = t-1; 26} 27return 0; 28 } 29 30 int cmp(int (*b)[20], int n) 31 {// 从上到下筛选dealb函数得到的数组，返回的值是得数的依次低位数， 32 //n存储的是余数数组或者说除数依次高位向下的数个数和最高下标 33int i, j, temp, t, k, flag; 34for(k=0; k<n && last[k]==0; ++k); 35for(i=9; i>0; –i) 36{ 37// 两个数比较的三种情况 38if(b[i][0] > n-k+1) continue; // 位数不相同情况之一，减数较大则继续找下一位 39if(b[i][0] < n-k+1) return i; // 位数不相同情况之二，减数较小则返回减数的所在的下标，这个值也是得数的当前最低位数 40for(j=b[i][0],t=k,flag=0; t<=n && j>0 && b[i][j] == last[t]; ++t, –j) //位数相同的，逐个位权的数进行比较 41; 42if(t>n || j<=0 || b[i][j] < last[t]) return i; 43} 44return 0; 45 } 46 47 int main() 48 { 49int i, j, k, t, len, flag, temp, count = 0, loc, e, h; 50int b[12][20]; // b[i]存储的除数*i的值（i=1 2 3…9），每个第一位即b[i][0]存储该值的长度 51char opt, d[20]; 52while(scanf(“%s”, s) != EOF) 53{ 54while((opt = getchar()) == ‘ ‘); 55scanf(“%s”, d); 56dealb(b, d); 57len = strlen(s); 58for(i=0; i<len; ++i) a[i] = s[i] – ‘0’; 59count = loc = h = 0; 60for(i=0; i<len; ++i) 61{ 62last[count++] = a[i]; 63if((loc = cmp(b, count-1)) != 0) 64{ 65for(t=count-1,j=1,e=0; t>=0 && j<=b[loc][0]; –t, ++j) 66{// 从cmp得到的信息保证了b[1oc] – last >=0，此处进行相减运算 67if((temp = last[t]-b[loc][j] + e) < 0) 68{ 69e = -1; 70last[t] = 10 + temp; 71} 72else 73{ 74e = 0; 75last[t] = temp; 76} 77} 78if(j>b[loc][0] && t>=0) 79{ 80for(; t>=0; –t) 81{ 82temp = last[t] + e; 83if(temp < 0) e = -1, last[t] = 10+temp; 84else e = 0, last[t] = temp; 85} 86} 8788} 89c[h++] = loc; 90} 91if(opt == ‘/’) 92{ 93for(i=0; i<h-1 && c[i] == 0; ++i); // 除去前缀零 94for(; i<h; ++i) printf(“%d”, c[i]); 95} 96 97else 98{ 99for(i=0; i<count-1 && last[i] == 0; ++i);100for(; i<count; ++i)printf(“%d”, last[i]);101}102printf(“\n”);103}104return 0;105 }
1Wa
解题思路：
大数的运算主要是根据笔算的步骤用代码实现，不管是乘法、加法、减法都不例外，下面说说大数相除的思路：
变量声明：
便于理解，首先为每个变量设一个字符（根据我的代码）
被除数：a （存储从左至右 即 xxx… = a[0]a[1]a[2]….）
除数：b[1] (存储从右至左 即 xxx… = b[1][n]b[n-1][n-2]… 长度n=b[1][0]）同样可以理解 b[m](m = 1 2 3 4…9) = b[1] * m;
商： c （存储从左至右 即xxx… = c[0][1][2]…）输出时应该省略掉前缀无意义的0
找一个让心里安静和干净的地方，自己变得跟水晶一般透明，
