首页 > 代码库 > C#实现突破位数限制,用字符串对较大的数进行运算

C#实现突破位数限制,用字符串对较大的数进行运算

 

有时会碰到数字太大无法用int运算的情况,比如1000的阶乘。

解决方法是用char、string代替int进行竖式计算,可进行加、减、乘、除、阶乘、组合、比较大小,下面的方法都测试过

  1         #region 运算方法
  2         // 计算组合数
  3         public string GetCombination(int total, int num)
  4         {
  5             string result = "";
  6             string dividend = GetStringMultiply(GetFactorial(num), GetFactorial(total - num));
  7             string divisor = GetFactorial(total);
  8             result = GetStringDivide(divisor, dividend);
  9             return result;
 10         }
 11         // 计算num的阶乘
 12         public string GetFactorial(int num)
 13         {
 14             string result = "";
 15             result = num > 0 ? GetStringMultiply(num.ToString(), GetFactorial(num - 1)) : "1";
 16             return result;
 17         }
 18         // 两个string数字相除
 19         public string GetStringDivide(string divisor, string dividend)
 20         {
 21             string result = "";
 22             List<char> cDivisor= divisor.ToCharArray().ToList<char>();
 23             List<char> cDividend = dividend.ToCharArray().ToList<char>();
 24             List<char> temp = new List<char>();
 25             List<char> cResult = new List<char>();
 26             int indexResult = -1;
 27             int indexDivisor = 0;
 28 
 29             // 除法的竖式计算
 30             while (indexDivisor != cDivisor.Count)
 31             {
 32                 // 从前往后分离除数大于被除数的部分,结果存入temp
 33                 try
 34                 {
 35                     for (; CompareTwoStringNum(GetListToString(temp), GetListToString(cDividend)) < 0; indexDivisor++)
 36                     {
 37                         temp.Add(cDivisor[indexDivisor]);
 38                         cResult.Add(0);
 39                         indexResult++;
 40                     }
 41                 }
 42                 catch
 43                 {
 44                     ;
 45                 }
 46                 // 得到一位结果,存入cResult
 47                 for (int i = 1; CompareTwoStringNum(GetListToString(temp), GetStringMultiply(dividend, i.ToString())) >= 0; i++)
 48                 {
 49                     cResult[indexResult] = Convert.ToChar(i.ToString());
 50                 }
 51 
 52                 temp = GetStringSub(GetListToString(temp), GetStringMultiply(GetListToString(cDividend), cResult[indexResult].ToString())).ToList<char>();
 53             }
 54 
 55             // 去除多余的0
 56             while (cResult[0] == 0 && cResult.Count > 1)
 57                 cResult.RemoveAt(0);
 58 
 59             result = string.Join("", cResult);
 60             return result;
 61         }
 62         // 转换成string
 63         public string GetListToString(List<char> cNum)
 64         {
 65             if (cNum.Count == 0)
 66                 return "0";
 67 
 68             while (cNum[0] == 0 && cNum.Count > 1)
 69                 cNum.RemoveAt(0);
 70             return string.Join("", cNum);
 71         }
 72         // 多个string数字相乘
 73         public string GetStringMultiply(List<string> nums, bool isRecursion = false)
 74         {
 75             string result = "";
 76             if (isRecursion)
 77                 nums.RemoveAt(0);
 78 
 79             if (nums.Count > 0)
 80                 result = GetStringMultiply(nums[0], GetStringMultiply(nums, true));
 81             else
 82                 return "1";
 83             return result;
 84         }
 85         // 两个string数字相乘
 86         public string GetStringMultiply(string num1, string num2)
 87         {
 88             string result = "";
 89             List<string> temp = new List<string>();
 90             char[] Char1 = num1.ToCharArray();
 91             char[] Char2 = num2.ToCharArray();
 92             int index1 = Char1.Length - 1, index2 = Char2.Length-1;
 93             int flag = 0;
 94 
 95             // 得到第一级相乘后的字符串数组
 96             for (int i = index2; i >= 0; i--)
 97             {
 98                 List<char> c = new List<char>();
 99                 for (int z = i; z < Char2.Length-1; z++)
100                 {
101                     c.Add(0);
102                 }
103                 // 进行第一级相乘(倒序存放)
104                 for (int j = index1; j >= 0; j--)
105                 {
106                     int n = Convert.ToInt32(Char1[j].ToString()) * Convert.ToInt32(Char2[i].ToString()) + flag;
107                     flag = n > 9 ? n / 10 : 0;
108                     c.Add(n > 9 ? Convert.ToChar((n % 10).ToString()) : Convert.ToChar(n.ToString()));
109                 }
110                 // 组合成第一级相乘的字符串
111                 StringBuilder sb = new StringBuilder();
112                 if (flag > 0)
113                     sb.Append(flag.ToString());     // 最高位进位
114                 for (int k = c.Count - 1; k >= 0; k--)
115                 {
116                     sb.Append(c[k]);
117                 }
118                 temp.Add(sb.ToString());
119                 flag = 0;
120             }
121 
122             // 字符串相加
123             result = GetStringAdd(temp);
124 
125             return result;
126         }
127         // 多个string数字相加
128         public string GetStringAdd(List<string> num)
129         {
130             string result = "";
131             List<char[]> nChar = new List<char[]>();
132 
133             foreach (string s in num)
134             {
135                 nChar.Add(s.ToCharArray());
136             }
137 
138             int flag = 0;   // 进位
139             int index = 1;  // 从后向前的索引
140             bool continus;
141             List<string> addResult = new List<string>();
142             StringBuilder sb = new StringBuilder();
143             do
144             {
145                 int addNum = 0;
146                 continus = false;
147 
148                 // 从后向前单列相加
149                 for (int i = 0; i < num.Count; i++)
150                 {
151                     int lastIndex = nChar[i].Length - index;
152                     addNum += lastIndex < 0 ? 0 : Convert.ToInt32(nChar[i][lastIndex].ToString());
153                     continus |= (lastIndex > 0);
154                 }
155                 index++;
156 
157                 addResult.Add(((addNum + flag) % 10).ToString());
158                 flag = (addNum + flag) / 10;
159                 if (flag > 0 && !continus)
160                     addResult.Add(flag.ToString());
161             } while (continus);
162             for (int i = addResult.Count - 1; i >= 0; i--)
163             {
164                 sb.Append(addResult[i]);
165             }
166             result = sb.ToString();
167 
168             List<char> cResult = result.ToCharArray().ToList<char>();
169             // 去除多余的0
170             while (cResult[0] == 0 && cResult.Count > 1)
171                 cResult.RemoveAt(0);
172             result = string.Join("", cResult);
173 
174             return result;
175         }
176         // 两个string数字相减
177         public string GetStringSub(string num1, string num2)
178         {
179             string result = "";
180             int flag = 0;
181             if (num1.Length < num2.Length)
182                 return null;
183             num2 = num2.PadLeft(num1.Length, 0);
184             char[] cNum1 = num1.ToCharArray();
185             char[] cNum2 = num2.ToCharArray();
186             if (Convert.ToInt32(cNum1[0].ToString()) < Convert.ToInt32(cNum2[0].ToString()))
187                 return null;
188 
189             List<char> temp = new List<char>();
190             for (int i = cNum1.Length - 1; i >= 0; i--)
191             {
192                 if ((Convert.ToInt32(cNum1[i].ToString()) - flag) >= Convert.ToInt32(cNum2[i].ToString()))
193                 {
194                     temp.Add(Convert.ToChar((Convert.ToInt32(cNum1[i].ToString()) - flag - Convert.ToInt32(cNum2[i].ToString())).ToString()));
195                     flag = 0;
196                 }
197                 else
198                 {
199                     temp.Add(Convert.ToChar((Convert.ToInt32(cNum1[i].ToString()) - flag + 10 - Convert.ToInt32(cNum2[i].ToString())).ToString()));
200                     flag = 1;
201                 }
202             }
203             // 去除多余的0
204             while (temp[temp.Count - 1] == 0 && temp.Count > 1)
205                 temp.RemoveAt(temp.Count - 1);
206 
207             StringBuilder sb = new StringBuilder();
208             for (int i = temp.Count - 1; i >= 0; i--)
209             {
210                 sb.Append(temp[i]);
211             }
212             result = sb.ToString();
213             return result;
214         }
215         // 两个string数字比较大小,前面的大返回1
216         public int CompareTwoStringNum(string num1, string num2)
217         {
218             int result = 0;
219             List<char> cNum1 = num1.ToCharArray().ToList<char>();
220             List<char> cNum2 = num2.ToCharArray().ToList<char>();
221             // 去除多余的0
222             while (cNum1[0] == 0 && cNum1.Count > 1)
223                 cNum1.RemoveAt(0);
224             while (cNum2[0] == 0 && cNum2.Count > 1)
225                 cNum2.RemoveAt(0);
226 
227             if (cNum1.Count > cNum2.Count)
228                 result = 1;
229             else if (cNum1.Count < cNum2.Count)
230                 result = -1;
231             else
232             {
233                 for (int i = 0; i < cNum2.Count; i++)
234                 {
235                     if (cNum1[i] != cNum2[i])
236                     {
237                         result = cNum1[i] > cNum2[i] ? 1 : -1;
238                         break;
239                     }
240                 }
241             }
242 
243             return result;
244         }
245         #endregion