文章目录
大数加法大数减法c++版本Java版本大数乘法36进制加法c++版Java版大数加法
1、是整数; 2、两个数无限大,long都装不下; 3、不能用BigInteger; 4、不能用任何包装类提供的运算方法; 5、两个数都是以字符串的方式提供。
/*** 思路:* 字符串逐位相加,需要进位则进位处理,考虑两个问题:* 1、char怎么转换为integer, 减去'0'即可* 2、怎么处理对应位相加?反转字符串相加,正确处理进位即可,* 这样个位对应个位,十位对应十位,剩余的直接追加 * */public static String add(String str1, String str2) {char[]arr1 = new StringBuilder(str1).reverse().toString().toCharArray();char[]arr2 = new StringBuilder(str2).reverse().toString().toCharArray();int maxlen = arr1.length>arr2.length?arr1.length:arr2.length;int [] newlen = new int[maxlen+1];for (int i = 0; i < maxlen; i++) {int an1 = i < arr1.length?arr1[i]-'0':0;int an2 = i < arr2.length?arr2[i]-'0':0;newlen[i] = an1+an2;}for (int i = 0; i < newlen.length; i++){if(newlen[i] >= 10){newlen[i+1] += newlen[i]/10;newlen[i] %=10;}}StringBuilder ans = new StringBuilder();for (int i = newlen.length-1; i >=0;i--) {ans.append(newlen[i]);}if(ans.toString().charAt(0)=='0'){return ans.toString().substring(1,ans.length());//去掉开头可能有的0}return ans.toString();}public static void main(String[] args) {System.out.println( add("9234","22999999999"));}
大数减法
题目描述
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的差。
注意:
num1 和num2 都只会包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库
两个非负整数相减的结果可能为负。
因此,首先比较两个数的大小。
如代码所示,当小减大时,需将两个参数调换一下位置执行减法,在结果前填上负号即可
注意:结果为0时不加负号。
如何比较两个大数的大小呢?
由于是大数,肯定不能直接转成int比较。
我们可以比较两个字符串的长度。
长度更长的字符串,数一定更大;当长度一样的就去比较字典序。
c++版本
bool isLess(string a, string b) {if (a.size() == b.size()) return a < b;return a.size() < b.size();}
减法操作代码:
string sub(string a, string b) {string res = "";int borrow = 0;int i = a.size() - 1, j = b.size() - 1;while (i >= 0 || j >= 0) {int x = i >= 0 ? (a[i] - '0') : 0; //字符转整数int y = j >= 0 ? (b[j] - '0') : 0; //字符转整数int z = (x - borrow - y + 10) % 10;res += ('0' + z); //整数转成字符borrow = x - borrow - y < 0 ? 1 : 0;i--, j--;}reverse(res.begin(), res.end());//删除前导0,注意边界是res.size()-1!!防止当res为"0000"时,删为""的清空int pos;for (pos = 0; pos < res.size() - 1; pos++) {if (res[pos] != '0') break;}return res.substr(pos);}
主方法:
string subStrings(string num1, string num2) {string res;if (isLess(num1, num2)) {res = sub(num2, num1);if (res != "0") res.insert(0, "-");}else res = sub(num1, num2);return res;}
Java版本
public boolean isless(String a,String b)//判断两个字符串大小{if(a.length()==b.length()) if( pareTo(b)<0){return true;}else {return false;}else return a.length()<b.length();}public String reverse(String s){//字符串反转char[]arr = new char[s.length()];int i = 0,j = s.length()-1;while(i <=j){arr[i] = s.charAt(j);arr[j] = s.charAt(i);i++;j--;}return new String(arr);}public String sub(String a,String b){//两个字符串相减int i = a.length()-1,j=b.length()-1;int borrow=0;String ans="";while(i>=0||j>=0){int x = i>=0?(a.charAt(i)-'0'):0;int y = j>=0?(b.charAt(j)-'0'):0;int result = (x-borrow-y+10)%10;ans+=result;borrow = x-borrow-y<0?1:0;i--;j--;}ans=reverse(ans);int ii = 0;for(ii= 0;ii<ans.length();ii++)if(ans.charAt(ii)!='0') break;return ans.substring(ii,ans.length());}public String mainope(String a,String b){//用于判断两个字符串哪个大,如果是小的减去大的则在答案前面加符号,且最后的结果转化为字符串输出String res="";StringBuilder str= new StringBuilder();if(isless(a,b)){res = sub(b,a);if(res!="0") {str.append("-");str.append(res);return str.toString();}else return "0";}else {return sub(a,b);}}
调用:
mainope("1000","8988");//输出-7988
大数乘法
(字符串相乘)
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
public String multiply(String num1, String num2) {LinkedList<Integer>temp = new LinkedList<>();if(num2.equals("0")||num1.equals("0")) return "0";int[]ans = new int[num1.length()+num2.length()];for(int i = num1.length()-1;i>=0;i--){for(int j = num2.length()-1;j>=0;j--){int digi1 = num1.charAt(i)-'0';int digi2 = num2.charAt(j)-'0';int tot = ans[i+j+1]+digi1*digi2;ans[i+j+1]=tot%10;ans[i+j] += tot/10;}}String ut ="";boolean flag = true;for(int i = 0;i < ans.length;i++){if(ans[i]==0&&flag)continue;flag = false;if(!flag)ut+=ans[i];}return ut;}
36进制加法
题目描述
36进制由0-9,a-z,共36个字符表示。
要求按照加法规则计算出任意两个36进制正整数的和,如1b + 2x = 48 (解释:47+105=152)
要求:不允许使用先将36进制数字整体转为10进制,相加后再转回为36进制的做法
参考代码
c++版
#include <iostream>#include <algorithm>using namespace std;char getChar(int n){if (n <= 9)return n + '0';elsereturn n - 10 + 'a';}int getInt(char ch){if ('0' <= ch && ch <= '9')return ch - '0';elsereturn ch - 'a' + 10;}string add36Strings(string num1, string num2){int carry = 0;int i = num1.size() - 1, j = num2.size() - 1;int x, y;string res;while (i >= 0 || j >= 0 || carry){x = i >= 0 ? getInt(num1[i]) : 0;y = j >= 0 ? getInt(num2[j]) : 0;int temp = x + y + carry;res += getChar(temp % 36);carry = temp / 36;i--, j--;}reverse(res.begin(), res.end());return res;}int main(){string a = "1b", b = "2x", c;c = add36Strings(a, b);cout << c << endl;}
Java版
public String reverse(String s){char[]arr = new char[s.length()];int i = 0,j = s.length()-1;while(i <=j){arr[i] = s.charAt(j);arr[j] = s.charAt(i);i++;j--;}return new String(arr);}public char getchar(int n){if(n<=9)return (char) (n+'0');else return (char) (n+'a'-10);}public int getint(char ch){if(ch<='9')return ch-'0';elsereturn ch-'a'+10;}public String add36(String a,String b){String ans="";int len1=a.length()-1,len2=b.length()-1;int carry=0;while(len1>=0||len2>=0){int x=len1>=0?getint(a.charAt(len1)):0;int y = len2>=0?getint(b.charAt(len2)):0;int result = (x+y+carry)%36;carry = (x+y+carry)/36;ans+=getchar(result);len1--;len2--;}ans = reverse(ans);return ans;}
add36("1de0","8f88")//输出9sm8