高精度算法 (加减乘除-四则)
前言
int b = 2 + 3;
这样的常规操作谁都会,你竟然单独写一篇博客教我这个,哈哈哈,笑死我了
😃😃😃 其实不然,我让你算一下这个试试:
1
| int c = 99999999999999999999999999999999999999 + 99999999999999999999999999999999999999;
|
这时,你就会发现,这个运算量已经超过 int 类型 -2,147,483,648 到 2,147,483,647 的范围了,怎么办呢?
别急,往下看 😁
前期准备
自然我们需要做一些防错措施
例如:判断拿到的数据是否满足要求,所以下面的代码是接下来每个算法(加减乘除…)必须的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
public static bool Check_IsAllNum(string p) { char[] arr = p.ToCharArray(); for (int i = 0; i < arr.Length; i++) { int unmatchNum = 0; for (int q = 0; q < TextHelper.Text.Numbers.Length; q++) { if (arr[i] != TextHelper.Text.Numbers[q]) { unmatchNum++; } } if (unmatchNum == 10) { return false; } } return true; }
public static int[] CharArrayToIntArray(char[] u) { int[] rst = new int[u.Length]; for (int i = 0; i < rst.Length; i++) { rst[i] = Convert.ToInt32(u[i]); } return rst; }
public static int[] StringToIntArray(string p) { char[] t = p.ToCharArray(); int[] rst = new int[t.Length]; for (int i = 0; i < rst.Length; i++) { rst[i] = Convert.ToInt32(t[i].ToString()); } return rst; }
|
高精度加法
自写,不支持小数点
思路
啊,首先我们要先思考一个问题: 既然 int 类型(包括其他大部分能直接运算的类型)装不下这么大的数,选用类型来装呢?
嘿,这么长的数字其实对于字符串而言就是一句话的事情,所以 string 类型不正好吗
那么拿到要运算的 string 类型的数据,接下来怎么办呢?
你可能会理所当然地想到小学学过的竖式
就像这样
那么如果我们把两个加数像竖式那样逐位相加,那么问题就被转化成了每上下两位之间10之内的加法,再把最后计算的结果当作一个 string 返回
这样就解决了前言中所说的问题。
再来理一遍思路:
- 拿到string类型的两个加数
- 逐位拆解两个加数
- 逐位相加两个加数,并把计算结果存到一个临时数组里
- 把临时数组装回一个string并返回
好,现在理清了思路,接下来就是实现这个算法
注:在实际的编写中,得到的两个加数的位数不一定相等,于是你要把两个加数补成长度相等的再进行运算,对应下面代码的 FillPosition() 方法
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
|
public static string[] FillPosition(char[] m, char[] n) { char[][] rst = new char[2][];
int big_length = ((m.Length - n.Length) >= 0) ? m.Length : n.Length; char[] m1 = new char[big_length]; char[] n1 = new char[big_length]; if (big_length == m.Length) { for (int i = 0; i < m.Length; i++) { m1[i] = m[i]; } int delta = m.Length - n.Length; for (int i = 0; i < big_length; i++) { if (i < delta) { n1[i] = '0'; } else { n1[i] = n[i - delta]; } } } else { for (int i = 0; i < n.Length; i++) { n1[i] = n[i]; } int delta = n.Length - m.Length; for (int i = 0; i < big_length; i++) { if (i < delta) { m1[i] = '0'; } else { m1[i] = m[i - delta]; } } } rst[0] = m1; rst[1] = n1;
string[] result = new string[2]; string r1 = ""; for (int i = 0; i < rst[0].Length; i++) { r1 += rst[0][i]; } string r2 = ""; for (int i = 0; i < rst[1].Length; i++) { r2 += rst[1][i]; } result[0] = r1; result[1] = r2; return result; }
public static string[] FillPosition(string m, string n) => FillPosition(m.ToCharArray(), n.ToCharArray());
public static int GetUnit(int num) => Convert.ToInt32(num.ToString().ToCharArray()[num.ToString().ToCharArray().Length - 1].ToString());
public static string Sum(string a, string b) { if (Check_IsAllNum(a) && Check_IsAllNum(b)) { string result = ""; string[] coverd = FillPosition(a, b);
int[] a1 = StringToIntArray(coverd[0]), b1 = StringToIntArray(coverd[1]);
int[] tmp = new int[a1.Length + 1];
bool cb = false; for (int i = a1.Length - 1; i >= 0; i--) { int l = a1[i], r = b1[i]; tmp[i + 1] = cb ? GetUnit(l + r) + 1 : GetUnit(l + r); cb = l + r > 9; } if (cb) { tmp[0] = 1; }
for (int i = 0; i < tmp.Length; i++) { result += tmp[i].ToString(); }
return result; } else { return null; } }
|
支持小数点的算法
因为这个不是我自己写的,所以没有思路
从 52342534 - MSDN 转载
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| static void Main(string[] args) { string change; string num1 = Console.ReadLine(); string num2 = Console.ReadLine(); int[] n1 = new int[num1.Length]; int[] n2 = new int[num2.Length]; for (int i = 0; i < num1.Length; i++) { change = num1[i].ToString(); n1[i] = int.Parse(change); } for (int i = 0; i < num2.Length; i++) { change = num2[i].ToString(); n2[i] = int.Parse(change); } if (num1.Length > num2.Length) { for (int i = 0; i < num2.Length; i++) { n1[num1.Length - i-1] += n2[num2.Length - i-1]; } for (int i = n1.Length-1; i > 0; i--) { if (n1[i] >= 10) { n1[i - 1]++; n1[i] %= 10; } } foreach (int x in n1) { Console.Write(x); } } else { for (int i = 0; i < num1.Length; i++) { n2[num2.Length - i - 1] += n1[num1.Length - i - 1]; } for (int i = n2.Length-1; i > 0; i--) { if (n2[i] >= 10) { n2[i - 1]++; n2[i] %= 10; } } foreach (int x in n2) { Console.Write(x); } }
Console.Read(); }
|
高精度减法
思路
暂时没有,等更新吧
高精度乘法
思路
所谓乘法,例如 a × b 其实就是 a 个 b 相加
那么问题就明确了,我们只需循环 a 次 并利用上面已经写好的高精度加法来累加 b
但是这样就有一个问题,循环该怎么处理呢,毕竟如果 a 也是一个极大的数,for 循环就不可用了,那么我们只能回归基础的 while 循环
代码
还没写好 QAQ 😂
高精度除法
完
觉得写的好的,打个赏呗 😘