今天部门面试一个人，面试官给来面试的人除了一道题：大整数乘法；面试结果弄得我们术面试官有点怀疑人生了，顺手就抓到我，来你看看这道题，一个小时之内给我做出来。。。
一开始，其实我是，是拒绝的。。。算了，不废话了，看题:
两个若干位（超过10位）的整数相乘，请写出正确的结果，例如
99999999999*99999999999 = 9***************1（我懒的去数了）
要求：
1.利用OO思想完成代码
2.支持20位以内的大数乘法
3.尽可能提高效率
加分项
1.代码调理结构清晰
2.支持任意位数相乘
3支持加减乘除
提示：
1.做乘法=做加法
2.累加器原理
3.乘法分配律
4.字符串做存储
简单说一句，让你手工计算你估计花点儿时间也能计算出来，计算机能干嘛？模拟手工计算嘛！想到这里思路就清晰一半了！分析下我们手工计算的时候最关键的是什么：列个竖式计算，你可以知道，最关键是进位，而且竖式计算方法中我们会在计算不同位数时放置在不同的地方，给个图
我们计算的顺序是3*3-》2*3-》6*3，然后该进位的地方进位；2*3，由于2在十位，计算结果为20*3=60，计算机模拟需要补1位，6在百位，计算是600*3=1800，需要补两位，并进一位；这些通过我们代码模拟就是两个东西，补位和进位；于是，在代码中，我们可以分别计算两个数字字符串每个位置上面的结果，并记录补位和进位的情况，最后累加就可以得到一个完整的字符串了；
下面具体分析，有什么已有的数据结构能很好的表示位数的情况？对就是数组，比如计算的结果是1800，我们用一个长度为4的int数组就可以存储intarr[4]{1,8,0,0}
接下来是进位，就拿最上面的例子来说，两个字符串最后一位，9*9，需要进一位，于是我们的存储结构是intArr[2]{8,1},再取第一个字符串倒数第二个数字和第二个字符串最后一个数字，也就是90*9，进一位，在累加到原数组上面就是int[3]{8,9,1},，这样一次将两个字符串所有位数上的数字都乘一遍，得到以下结果int[15]{1,12,1,12,12,5,6,14,68,12,12,3,45,1,1}(这个结果只是列子，不是真实计算结果)，我们看到，不同位数上面有可能大于了10，这是因为在计算的过程中，只是记录累加了每个位置的数字，并没有在计算的时候进行进位操作，最后只要遍历下数组，进下位就行了，比如45，就像百位是45，就进个4到千位，留个5在百位；那么需要多长的数组去计算两个字符串呢？两个字符串长度总和就是了啦！
分析到此，上代码（自己随意写的，没有按照啥OO思想啊啥的写）
public static string caculate(string number1Str,string number2Str)
{
//跳过数字检测
int num1Length = number1Str.Length;
int num2Length = number2Str.Length;
var arrCaculate = new int[num2Length + num1Length ];
for (int i = 0; i < num1Length; i++)
{
for (int j = 0; j < num2Length; j++)
{
int num1 = GetStringNum(i, number1Str);
int num2 = GetStringNum(j,number2Str);
int sum1 = num1 * num2;
int zeroCount = i + j;//补位的数量
int jinNum = sum1 / 10;//进位的数字
int yuNum = sum1 % 10;//余数
arrCaculate[zeroCount] += yuNum;//存到相应的位置中去
arrCaculate[zeroCount + 1]+= jinNum;
}
}
return CaculateArr(arrCaculate);
}
private static string CaculateArr(int[] arr)
{
for (int i = 0; i
{
int num = arr[i];//统一计算进位的问题
arr[i] = num % 10;
arr[i + 1] += num / 10;
}
string result = string.Empty;
for (int i = arr.Length-1; i >=0; i--)//依次输出字符串
{
result += arr[i].ToString();
}
return result;
}
///
/// 倒序
///
///
private static int GetStringNum(int i,string num)
{
string lastCa = num.Substring(num.Length-i-1,1);//获取正在计算的一位，倒数开始，i=0，获取最后一位数字
return Convert.ToInt32(lastCa);
}
}
代码并不多，来看看效果吧
文章写得少，估计有些地方没说清楚。。。。客官见谅
网友评论