這次直接使用大數除法來運算
1. 取得a及b的位數數目len_a、len_b
2. 將乘數b乘上10的 (len_a - len_b) 次方，也就是前移(len_a-len_b)位
3. 由i=0開始將a和b*i比較，找出滿足b*i≦A＜B*(i+1)的i
4. 商的 len_a-len_b+1位 ( 即 c[len_a-len_ b ) 就是i， a = a - b*i ，b=b/10
5. 重複直到 len_a - len_b==0
//Big number : http://www.csie.ntnu.edu.tw/~u91029/BigNumber.html #include <stdio.h> #include <stdlib.h> #include <string.h> #include <cstdio> #include <cstring> #include <iostream> #define maxn 10000 using namespace std; int len_a,len_b; //a和b的長度 void print(int a[maxn]){ int i=maxn-1; // 要印的數字位置 while(i>=0 && a[i]==0) i--; // 數字開頭的零都不印 if(i<0)cout << '0'; else while(i>=0) cout << a[i--]; } // a > b or a < b int compare(int a[maxn], int b[maxn]) { for (int i=maxn-1; i>=0; i--) // 從高位數開始比，對應的位數相比較。 if (a[i] != b[i] && a[i] > b[i]){ // 發現 a b 不一樣大，馬上回傳結果。 return 1; // 1 = a>b } else if (a[i] != b[i] && a[i] < b[i]){ return 2; // 2 = a<b } return false; // 完全相等 } // c = a + b; void add(int a[maxn], int b[maxn], int c[maxn]) { for (int i=0; i<maxn; i++) // 對應的位數相加 c[i] = a[i] + b[i]; for (int i=0; i<maxn-1; i++) // 一口氣進位 { c[i+1] += c[i] / 10; // 進位 c[i] %= 10; // 進位後餘下的數 } } // c = a - b void sub(int a[maxn], int b[maxn], int c[maxn]) { //code優化 int max; if(len_a>=len_b)max=len_a; else max = len_b; for (int i=0; i<max; i++) // 對應的位數相加 c[i] = a[i] - b[i]; for (int i=0; i<max-1; i++) // 一口氣補位 { if(c[i]<0){ c[i] += 10; c[i+1] --; } } } // c = a * b; void mul(int a[maxn], int b[maxn], int c[maxn]) { //code優化 int max; if(len_a>=len_b)max=len_a; else max = len_b; for (int i=0; i<max; i++) c[i] = 0; for (int i=0; i<max; i++) for (int j=0; j<max; j++) if (i+j < max) c[i+j] += a[i] * b[j]; for (int i=0; i<max-1; i++) // 一口氣進位 { c[i+1] += c[i] / 10; c[i] %= 10; } } // c = a / b void div(int a[maxn], int b[maxn], int c[maxn]) { //code 優化 int max=0; if(len_a>=len_b)max=len_a+1; else max = len_b+1; int t[maxn]={0}; int t2[maxn]={0}; int b2[maxn]={0}; int b3[maxn]={0}; int len_diff = len_a-len_b; //兩數字位數差 difference of length memset(t,0,sizeof(t)); t[len_diff]=1; //t陣列的用意是，創造一個"...001000..."的陣列，好讓除數可以乘上 while(len_diff >= 0){ memset(b2,0,sizeof(b2)); mul(b,t,b2); //b2 = b * t for(int i=9;i>0;i--){ //商數由9→1 memset(b3,0,sizeof(b3)); for(int j=max-1;j>=0;j--){ b3[j] = b2[j] * i; // b3 = b2 * i ，測試商數 } for(int j=0;j<max;j++){ while(b3[j]>=10){ //所有位數進位 b3[j]-=10; b3[j+1]+=1; } } if(compare(a,b3)==1 || compare(a,b3)==0){ //若a>=b3 c[len_diff]+=i; // 於len_diff的商數+1 sub(a,b3,t2); // t2 = a - b3 for(int j=0;j<max;j++)a[j]=t2[j]; //a = t2 memset(t2,0,sizeof(t2)); } } memset(t,0,sizeof(t)); len_diff--; //位數往前一位 if(len_diff>=0)t[len_diff]=1; } } void mod(int a[maxn], int b[maxn], int c[maxn]) { //code 優化 int max=0; if(len_a>=len_b)max=len_a; else max = len_b; int t[maxn]={0}; int t2[maxn]={0}; int b2[maxn]={0}; int b3[maxn]={0}; int len_diff = len_a-len_b; //兩數字位數差 t[len_diff]=1; while(len_diff>=0){ memset(b2,0,sizeof(b2)); mul(b,t,b2); for(int i=9;i>0;i--){ memset(b3,0,sizeof(b3)); for(int j=max-1;j>=0;j--){ b3[j] = b2[j] * i; while(b3[j]>=10){ b3[j]-=10; b3[j+1]+=1; } } if(compare(a,b3)==1 || compare(a,b3)==0){ sub(a,b3,t2); for(int j=0;j<max;j++)a[j]=t2[j]; // a = t2 for(int j=0;j<max;j++)c[j]=t2[j]; // c = t2 memset(t2,0,sizeof(t2)); } } memset(t,0,sizeof(t)); len_diff--; if(len_diff>=0)t[len_diff]=1; } } char input_a[maxn]={'\0'}; char op,op1,op2,op3; char input_b[maxn]={'\0'}; int a[maxn],b[maxn],result[maxn]; int main(){ freopen("input.txt","r",stdin); while(scanf("%s%s%s",&input_a,&op2,&input_b)!=EOF){ memset(a,'\0',sizeof(a)); memset(b,'\0',sizeof(b)); memset(result,'\0',sizeof(result)); //printf("%s %c %s\n",input_a,op2,input_b); //轉換為倒轉數字陣列 len_a = strlen(input_a); for(int i=0;i<len_a;i++){ a[i]=input_a[len_a-i-1]-48; } len_b = strlen(input_b); for(int i=0;i<len_b;i++){ b[i]=input_b[len_b-i-1]-48; } if(op2=='/'){ if(compare(a,b)==2)printf("0"); //若b>a，則為0 else if(len_b==1 && b[0]==0)break; else { div(a,b,result); print(result); } } if(op2=='%'){ if(compare(a,b)==2)print(a); //若b>a，餘數則為a else { mod(a,b,result); print(result); } } printf("\n"); } return 0; }
沒有留言:
發佈留言