1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <string> 5 #include <stdlib.h> 6 #include <algorithm> 7 using namespace std; 8 string MULTIPLY_INT(string str1 , string str2); 9 string MINUS_INT(string str1 , string str2); 10 inline int compare(string str1 , string str2) 11 { 12 if(str1.size() > str2.size())//初步比较 长度长的整数大 13 return 1; 14 else if(str1.size() < str2.size()) 15 return -1; 16 else 17 return str1.compare(str2); 18 //若两数长度相等，按位比较，compare函数 ：相等返回0， 大于返回1，否则返回-1 19 } 20 21 //高精度加法 22 string ADD_INT(string str1 , string str2) 23 { 24 int sign = 1;//符号位 25 string str; 26 if(str1[0] == '-') 27 { 28 if(str2[0] == '-') 29 { 30 sign = -1; 31 str = ADD_INT(str1.erase(0,1) , str2.erase(0,1)); 32 } 33 else 34 str = MINUS_INT(str2 , str1.erase(0,1)); 35 } 36 else 37 { 38 if(str2[0] == '-') 39 str = MINUS_INT(str1 , str2.erase(0,1)); 40 else//把两个数，短整数前加0补齐 41 { 42 string :: size_type len1,len2; 43 int i; 44 len1 = str1.size(); 45 len2 = str2.size(); 46 if(len1 < len2) 47 { 48 for( i =1 ; i <= len2 - len1 ; i++) 49 str1 = "0" + str1; 50 } 51 else if(len1 > len2) 52 { 53 for(i = 1 ; i <= len1 - len2 ; i++) 54 str2 = "0" + str2; 55 } 56 int int1 = 0 , int2 = 0 ;//int2 记录进位 57 for( i = str1.size() - 1 ; i >= 0 ; i--) 58 { 59 int1 = (int (str1[i]) - 48 + int(str2[i]) - 48 + int2) % 10;//48 ASCII of 0 60 int2 = (int (str1[i]) - 48 + int(str2[i]) - 48 + int2) / 10; 61 str = char(int1 + 48) + str; 62 } 63 if(int2 != 0) 64 str = char(int2 + 48) + str; 65 } 66 } 67 //处理符号位 68 if((sign == -1) && (str[0] != '0')) 69 str = "-" + str; 70 return str; 71 } 72 73 //高精度减法 74 string MINUS_INT (string str1 , string str2) 75 { 76 int sign = 1;// 符号位 77 string str; 78 if(str2[0] == '-') 79 str = ADD_INT(str1 , str2); 80 else 81 { 82 int res = compare(str1 , str2); 83 if(res == 0) 84 return "0"; 85 if(res < 0) 86 { 87 sign = -1; 88 string temp = str1; 89 str1 = str2; 90 str2 = temp; 91 } 92 string :: size_type tempint; 93 tempint = str1.size() - str2.size();//两数相差位数 94 for(int i = str2.size() -1 ; i >= 0 ; i--)//str2.size() -1 str2 最低位 95 { 96 if(str1[i + tempint] < str2[i])//str1[i + tempint] 与str2 对应位数的数 97 { 98 str1[i + tempint -1] = char(int (str1[i + tempint - 1])-1);//借位 高位减一 99 str = char(str1[i + tempint] - str2[i] + 58) + str;// 58 ASCII of 10 100 } 101 else 102 str = char(str1[i + tempint] - str2[i] + 48) + str; 103 104 } 105 for(int i = tempint -1 ; i >=0 ; i--) 106 str = str1[i] + str;//将数补全 107 } 108 //去除结果中多余的前导0 109 str.erase(0,str.find_first_not_of('0')); 110 if(str.empty()) 111 str = "0"; 112 if((sign == -1) && str[0] != '0') 113 str = "-" + str; 114 return str; 115 } 116 117 //高精度乘法 118 string MULTIPLY_INT(string str1 , string str2) 119 { 120 int sign = 1;//符号位 121 string str; 122 if(str1[0] == '-') 123 { 124 sign *= -1; 125 str1 = str1.erase(0,1); 126 } 127 if(str2[0] == '-') 128 { 129 sign *= -1; 130 str2 = str2.erase(0,1); 131 } 132 int i,j; 133 string :: size_type len1,len2; 134 len1 = str1.size(); 135 len2 = str2.size(); 136 for(i = len2 - 1 ; i >= 0 ; i--)//实现手工乘法 137 { 138 string tempstr; 139 int int1 = 0 , int2 = 0 , int3 = int(str2[i]) - 48; 140 if(int3 != 0) 141 { 142 for(j = 1 ; j <= (int)(len2 - 1 - i) ; j++) 143 tempstr = "0" + tempstr; 144 for(j = len1 - 1 ; j >= 0 ; j--) 145 { 146 int1 = (int3 * (int(str1[j]) - 48) + int2) % 10; 147 int2 = (int3 * (int(str1[j]) - 48) + int2) / 10; 148 tempstr = char(int1 + 48) + tempstr; 149 } 150 if(int2 != 0) 151 tempstr = char(int2 + 48) + tempstr; 152 } 153 str = ADD_INT(str,tempstr); 154 } 155 //去除结果中的前导0 156 str.erase(0,str.find_first_not_of('0')); 157 if(str.empty()) 158 str = "0"; 159 if((sign == -1) && (str[0] != '0')) 160 str += "-" + str; 161 return str; 162 } 163 string DIVIDE_INT(string str1, string str2, int flag) 164 { 165 //flag = 1时,返回商; flag = 0时,返回余数 166 string quotient, residue; 167 int sign1 = 1, sign2 = 1, i; 168 if(str2 == "0") 169 { //判断除数是否为0 170 quotient = "ERROR!"; 171 residue = "ERROR!"; 172 if(flag == 1) return quotient; 173 else return residue; 174 } 175 if(str1 == "0") 176 { //判断被除数是否为0 177 quotient = "0"; 178 residue = "0"; 179 } 180 if(str1[0] == '-') 181 { 182 str1 = str1.erase(0, 1); 183 sign1 *= -1; 184 sign2 = -1; 185 } 186 if(str2[0] == '-') 187 { 188 str2 = str2.erase(0, 1); 189 sign1 *= -1; 190 } 191 int res = compare(str1, str2); 192 if(res < 0) 193 { 194 quotient = "0"; 195 residue = str1; 196 } 197 else if(res == 0) 198 { 199 quotient = "1"; 200 residue = "0"; 201 } 202 else 203 { 204 string::size_type len1, len2; 205 len1 = str1.size(); len2 = str2.size(); 206 string tempstr; 207 tempstr.append(str1, 0, len2 - 1); 208 209 //模拟手工除法 210 for(i = len2 - 1; i < len1; i++) 211 { 212 tempstr = tempstr + str1[i]; 213 for(char ch = '9'; ch >= '0'; ch --) 214 { 215 string str; 216 str = str + ch; 217 if(compare(MULTIPLY_INT(str2, str), tempstr) <= 0) 218 { 219 quotient = quotient + ch; 220 tempstr = MINUS_INT(tempstr, MULTIPLY_INT(str2, str)); 221 break; 222 } 223 } 224 } 225 residue = tempstr; 226 } 227 228 //去除结果中的前导0 229 quotient.erase(0, quotient.find_first_not_of('0')); 230 if(quotient.empty()) quotient = "0"; 231 if((sign1 == -1) && (quotient[0] !='0')) 232 quotient = "-" + quotient; 233 if((sign2 == -1) && (residue[0] !='0')) 234 residue = "-" + residue; 235 if(flag == 1) return quotient; 236 else return residue; 237 } 238 239 //高精度除法,返回商 240 string DIV_INT(string str1, string str2) 241 { 242 return DIVIDE_INT(str1, str2, 1); 243 } 244 245 //高精度除法,返回余数 246 string MOD_INT(string str1, string str2) 247 { 248 return DIVIDE_INT(str1, str2, 0); 249 }
基本照模板敲的，感觉要gg了