1 //  2 //  main.cpp  3 //  正整数高精度运算  4 //  5 //  Created by ashley on 14-11-9.  6 //  Copyright (c) 2014年 ashley. All rights reserved.  7 //  8   9 #include <iostream> 10 #include <string> 11 using namespace std; 12  13 string clearZeros(string data) 14 { 15     if (data[0] == ‘0‘) { 16         int key = (int) data.length() - 1; 17         for (int i = 0; i < data.length(); i++) { 18             if (data[i] != ‘0‘) { 19                 key = i; 20                 break; 21             } 22         } 23         data.erase(0, key); 24     } 25     if (data =http://www.mamicode.com/= "") { 26         data = http://www.mamicode.com/"0"; 27     } 28     return data; 29 } 30  31 //对位操作 32 void countPoint(string &operand1, string &operand2) 33 { 34     while (operand1.length() < operand2.length()) { 35         operand1 = "0" + operand1; 36     } 37     while (operand1.length() > operand2.length()) { 38         operand2 = "0" + operand2; 39     } 40 } 41  42 //判断大小 43 bool bigger(string operand1, string operand2) 44 { 45     return operand1 >= operand2; 46 } 47  48 string addition(string addent, string adder) 49 { 50     //先对位，在加数和被加数前面适当补0，使他们包含相同的位数 51     countPoint(addent, adder); 52     //前面再补一个0，确定和的最多位数 53     addent = "0" + addent; 54     adder = "0" + adder; 55     //从低位开始，对应位相加，结果写进被加数中，如果有进位，直接给被加数前一位加1 56     for (int i = (int) addent.length() - 1; i > 0; i--) { 57         addent[i] = addent[i] + adder[i] - 48; 58         if (addent[i] > ‘9‘) { 59             addent[i] = addent[i] - 10; 60             addent[i - 1] = addent[i - 1] + 1; 61         } 62     } 63     return clearZeros(addent); 64 } 65  66 string subtraction(string subtrahend, string subtractor) 67 { 68     //先对位，在减数和被减数前面适当补0，使他们包含相同的位数 69     countPoint(subtrahend, subtractor); 70     //判断被减数和减数谁大，保证被减数大于减数 71     if (bigger(subtrahend, subtractor)) { 72         subtrahend[0] = subtrahend[0] - subtractor[0] + 48; 73         for (int i = 1; i < (int)subtrahend.length(); i++) { 74             if (subtrahend[i] >= subtractor[i]) { 75                 subtrahend[i] = subtrahend[i] - subtractor[i] + 48; 76             } else { 77                 subtrahend[i] = subtrahend[i] - subtractor[i] + 10 + 48; 78                 subtrahend[i - 1]--; 79             } 80         } 81     } else { 82         subtrahend = ‘-‘ + subtraction(subtractor, subtrahend); 83     } 84     return subtrahend; 85 } 86  87 string multiplication(string multiplicand, string multiplier) 88 { 89     string result = "0"; 90     for (int i = (int)multiplier.length() - 1; i >= 0 ; i--) { 91         for (char c = ‘1‘; c <= multiplier[i]; c++) { 92             result = addition(result, multiplicand); 93         } 94         multiplicand = multiplicand + "0"; 95     } 96     return clearZeros(result); 97 } 98  99 // 试商法100 string division(string dividend, string divisor)101 {102     // 存放商103     string result;104     // 存放余数105     string remains;106     for (int i = 0; i < (int)dividend.length(); i++) {107         remains = remains + dividend[i];108         result = result + "0";109         // 从1往上试110         while (bigger(remains, result)) {111             cout << result << "-----------" << remains << endl;112             result[result.length() - 1]++;113             remains = subtraction(remains, divisor);114         }115     }116     return clearZeros(result);117 }118 int main(int argc, const char * argv[])119 {120     string a, b;121     int tests;122     cin >> tests;123     while (tests--) {124         cin >> a >> b;125         //正整数高精度加法，从低位开始126         //cout << addition(a, b) << endl;127         //正整数高精度减法，从高位开始128         //cout << subtraction(a, b) << endl;129         //正整数高精度乘法，将乘法转换为加法进行运算130         //cout << multiplication(a, b) << endl;131         cout << division(a, b) << endl;132         //正整数高精度除法133 134     }135     return 0;136 }