商城网站除了域名备案还要,电商网站如何做,吴川手机网站建设公司,台州响应式建站一、引子
高精度乘法相较于高精度加法和减法有更多的不同#xff0c;加法和减法是一位对应一位进行操作的#xff0c;而乘法是一个数的每一位对另一个数的每一位进行操作#xff0c;需要的计算步骤更多。 二、核心算法
void Calculate(int num1[], int num2[], int numres…一、引子
高精度乘法相较于高精度加法和减法有更多的不同加法和减法是一位对应一位进行操作的而乘法是一个数的每一位对另一个数的每一位进行操作需要的计算步骤更多。 二、核心算法
void Calculate(int num1[], int num2[], int numres[], int len1, int len2)
{// 核心乘法算法for (int i 0; i len1; i){for (int j 0; j len2; j){numres[i j] num1[i] * num2[j];numres[i j 1] numres[i j] / 10;numres[i j] numres[i j] % 10;}}
}
这一段代码是高精度乘法核心算法的实现它模拟了我们手工进行多位数乘法的过程。这里我们有两个数n1和n2它们分别以字符串的形式存储并被转换成整数数组num1和num2其中低位在前高位在后即字符串“123”会被存储成整数数组{3, 2, 1}。然后我们对这两个数组执行乘法。
对于乘法我们对于num1的每一位由外层循环 i 控制与num2的每一位由内层循环 j 控制相乘。由于我们是按位计算所以需要考虑结果的位数res数组的下标 i j 。这里考虑结果的位数是最低位数由于数组的特性两个数字的最低位在数组中是作为第零位的而且在数组中两个数的每一位相当于之前都是减少了一位如果是10 * 10两个两位数相乘理论上结果是三位但是如果将两数字的位数相加作为结果的位数那结果就是四(2 2)位数这样就不对了但是由于数组的特性将两数字位数相加改成两数字当前索引相加就可以了10 * 10索引相加是(1 1) 2而二作为索引是3位数结果是三位数这样就对了。在这里的原理是转换的过程两个数的位数转成索引要减一两个数就是减二而结果的索引转成位数又要加一这是就相当于减一在前面直接用位数运算的版本中结果是四位这里的就相当于结果的位数减一结果的位数就变成了三就对了。
假设两个两位数相乘结果的位数最低可能是三位最高是四位这里是按最低算的。如果放到了最高位就会导致这一步的结果扩大了十倍对比上面的解释我们发现数组是可以直接实现将每一步结果存到正确的位上的。也就是num1[i] * num2[j]的结果可以直接放到res[i j]里的这样是正确的。
如果不使用数组而使用数字位数的话也就是假设 i 和 j 不是索引而是数位那就不能将(num1的 i 位的数字) * (num2的 j 位的数字)的结果放到res的(i j)位上而要把结果放到res的(i j - 1)位上。
假设是10 * 10 100结果是三位
num1[0] * num2[0]是0 * 0 0res[0 0] 0,res[0] 0
num1[1] * num2[0] 0,res[1 0] 0,res[1] 0
num1[0] * num2[1] 0,res[0 1] 0,res[1] 0
num1[1] * num[1] 1,res[1 1] 1,res[2] 1
这是结果就是100
这个乘法的过程是
1. res[i j] n1[i] * n2[j]这里我们将num1的第i位和num2的第 j 位相乘然后加到结果的相应位置。由于n1和n2的下标为 i 和 j 那么对应的结果应该是res[i j]。这里的结果为res[i j]就是我们上面解释的体现用数组的特性使得这样做是正确的。
2. res[i j 1] res[i j] / 10这里我们处理进位。如果res[i j]的结果是两位数即大于或等于10我们需要将十位上的数字进位到结果的下一个位置res[i j 1]。
3. res[i j] res[i j] % 10保证结果数组res的每一位都是个位数即进行模10操作。进位已经在上一步处理过了这里确保数组res中存储的是当前位的正确数字。
这个过程会一直重复直到num1和num2中的每一位都相乘。由于进位可能影响到最终结果的位数结果数组res的实际使用长度可能会比num1和num2的长度总和还要大。所以我们在定义res数组的时候要确保它有足够的空间来存储可能的最大结果即num1长度和num2长度的和。
在乘法完成后结果数组res中存储的是乘法结果的每一位数字但是顺序是反的即最低位在数组的第0个位置。在最后我们需要将结果数组转换回字符串并且反转回正确的顺序来输出最终的乘积。
三、处理正负
我们同时还要考虑结果的正负对结果的正负进行判断影响结果正负的因素是乘数的正负这里就是同正异负可以判断好结果的正负然后将负号在最后打印。
在输入乘数时会有负号所以要判断乘数是否为负数然后还要将乘数前的负号去除防止对之后的计算产生影响。
同时在处理正负前不能将字符数组反转或者转成整型数组。
int JudgePorN(char arrch1[], char arrch2[])//1代表负0代表正
{if (arrch1[0] - arrch2[0] ! -){arrch1[0] 0;//将 - (负号)替换为符号0防止对后面的计算有影响符号0在后面的计算中不会有影响因为零会在后面作为前导零去除。注意是0如果写成数字0就不对了数字0是\0的ASIIC码写成数字0会被转换成\0\0是字符串的结束符return 1;}else if (arrch1[0] ! - arrch2[0] -){arrch2[0] 0;return 1;}else if (arrch1[0] - arrch2[0] -){arrch1[0] 0;arrch2[0] 0;return 0;}return 0;
}
所以处理正负函数要在字符数组反转函数和转成整型数组函数之前调用。
四、代码实现
#include stdio.h
#include string.hvoid DigitReverse(char arr[])//反转字符串以便后续计算
{int length (int)strlen(arr);for (int i 0; i length / 2; i){int temp arr[i];arr[i] arr[length - i - 1];arr[length - i - 1] temp;}
}void StringTranstoNumber(char arrchar[],int arrnum[])//将字符数组转换为数字数组
{int length (int)strlen(arrchar);for (int i 0; i length; i){arrnum[i] arrchar[i] - 0;}
}void Calculate(int num1[], int num2[], int numres[], int len1, int len2)
{// 核心乘法算法for (int i 0; i len1; i){for (int j 0; j len2; j){numres[i j] num1[i] * num2[j];numres[i j 1] numres[i j] / 10;numres[i j] numres[i j] % 10;}}
}void BigNumMul(char arrch1[], char arrch2[], int res[],int len1,int len2)
{DigitReverse(arrch1);DigitReverse(arrch2);int num1[505] {0};int num2[505] {0};StringTranstoNumber(arrch1,num1);StringTranstoNumber(arrch1,num2);Calculate(num1,num2,res,len1,len2);//计算结果
}void Print(int resnum[],int lengthmax)//打印函数
{int i lengthmax;while (i 0 resnum[i] 0)//去除前导零因为是按最大位数算的可能有前导零{i--;}for (; i 0; i--){printf(%d,resnum[i]);}
} int JudgePorN(char arrch1[], char arrch2[])//1代表负0代表正
{if (arrch1[0] - arrch2[0] ! -){arrch1[0] 0;//将 - (负号)替换为符号0防止对后面的计算有影响符号0在后面的计算中不会有影响因为零会在后面作为前导零去除。注意是0如果写成数字0就不对了数字0是\0的ASIIC码写成数字0会被转换成\0\0是字符串的结束符return 1;}else if (arrch1[0] ! - arrch2[0] -){arrch2[0] 0;return 1;}else if (arrch1[0] - arrch2[0] -){arrch1[0] 0;arrch2[0] 0;return 0;}return 0;
}int main()
{char ch1[505] 0;char ch2[505] 0;scanf(%s,ch1);scanf(%s,ch2);int res[1010] {0};int len1 (int)strlen(ch1);int len2 (int)strlen(ch2);if (len1 1 ch1[0] 0){printf(0);}else if (len2 1 ch2[0] 0){printf(0);}else if (len1 1 len2 1 ch1[0] 0 ch2[0] 0){printf(0);}else//非零情况{int judgevalue JudgePorN(ch1, ch2);//判断结果正负并去除字符串前面的 - (负号)BigNumMul(ch1, ch2, res, len1, len2);int lengthmax len1 len2;//乘法结果最大可能是两个乘数的位数和if (judgevalue 1)//结果为负{printf(-);Print(res, lengthmax);}else//结果为正{Print(res, lengthmax);}}
}
