小菜问大整数乘法有关问题
小菜问大整数乘法问题
最近在看左飞的《数据结构原理与经典问题求解》,看了大整数乘法问题,跟着敲了一遍代码,发现有一个问题不解。
#include<iostream>
#include <memory>
using namespace std;
int *multi(int *num1,int size1,int *num2,int size2)
{
int size = size1 + size2;//两大数相乘后加1的大小
int* ret = new int[size];
int i = 0;
memset(ret,0,sizeof(int)*size);//把ret全部初始化为0
for (i ; i < size2; ++i)//测试下和i++的在这里区别
{
int k = i;
for (int j = 0; j < size1; ++j)
{
ret[k++] += num2[i] * num1[j];
}
}
for (i = 0; i < size; ++i)
{
if(ret[i] >= 10)
{
ret[i+1] += ret[i] / 10;//进位
ret[i] = ret[i] %10;
}
}
return ret;
}
int main()
{
int num1[] = {1,2,3,4,5,6,7,8,9,1,1,1,1,1};//第一个大整数11111987654321
int num2[] = {1,1,1,2,2,2,3,3,3,4,4,4,5,5};//第二个大整数55444333222111
int *ret = multi(num1,14,num2,14);
for(int i = 27; i >= 0; i--)
cout << ret[i];
cout << endl;
delete[] ret;//释放内存
return 0;
}
不解的地方是,为什么int main()里,int num1[] = {1,2,3,4,5,6,7,8,9,1,1,1,1,1};//第一个大整数11111987654321,
int num2[] = {1,1,1,2,2,2,3,3,3,4,4,4,5,5};//第二个大整数55444333222111
要倒着写,运算结果才对?
算法小白,请教了!
------解决方案--------------------
类似于人类思考乘法时的步骤一样,我们做乘法时是从低位到高位的
在multi()函数里,处理乘法时数组处理方向是从左向右而我们写数字的时候习惯性写法是低位在右高位在左,所以要先颠倒下数字序列才正确。
其实也可以改函数里面的运算序列的,从右往左运算就可以了。
最近在看左飞的《数据结构原理与经典问题求解》,看了大整数乘法问题,跟着敲了一遍代码,发现有一个问题不解。
#include<iostream>
#include <memory>
using namespace std;
int *multi(int *num1,int size1,int *num2,int size2)
{
int size = size1 + size2;//两大数相乘后加1的大小
int* ret = new int[size];
int i = 0;
memset(ret,0,sizeof(int)*size);//把ret全部初始化为0
for (i ; i < size2; ++i)//测试下和i++的在这里区别
{
int k = i;
for (int j = 0; j < size1; ++j)
{
ret[k++] += num2[i] * num1[j];
}
}
for (i = 0; i < size; ++i)
{
if(ret[i] >= 10)
{
ret[i+1] += ret[i] / 10;//进位
ret[i] = ret[i] %10;
}
}
return ret;
}
int main()
{
int num1[] = {1,2,3,4,5,6,7,8,9,1,1,1,1,1};//第一个大整数11111987654321
int num2[] = {1,1,1,2,2,2,3,3,3,4,4,4,5,5};//第二个大整数55444333222111
int *ret = multi(num1,14,num2,14);
for(int i = 27; i >= 0; i--)
cout << ret[i];
cout << endl;
delete[] ret;//释放内存
return 0;
}
不解的地方是,为什么int main()里,int num1[] = {1,2,3,4,5,6,7,8,9,1,1,1,1,1};//第一个大整数11111987654321,
int num2[] = {1,1,1,2,2,2,3,3,3,4,4,4,5,5};//第二个大整数55444333222111
要倒着写,运算结果才对?
算法小白,请教了!
------解决方案--------------------
类似于人类思考乘法时的步骤一样,我们做乘法时是从低位到高位的
在multi()函数里,处理乘法时数组处理方向是从左向右而我们写数字的时候习惯性写法是低位在右高位在左,所以要先颠倒下数字序列才正确。
其实也可以改函数里面的运算序列的,从右往左运算就可以了。