分治法-大整数相乘.docx
22 浏览量
2023-06-28
10:35:23
上传
评论
收藏 31KB DOCX 举报
分治法——⼤整数相乘
⼤整数相乘：A、B两个整数，A有n位（123456……n），B有m位（123456……m
），⼀般的思路是像最初学习乘法时⼀样逐位相乘后相加，但是这样做算法的
复杂度过⾼，但这仍然是解题的基本思想。
既然提到分治，那么如何分，怎么治？
分：
能够找到⼀个⼤问题划分为⼩问题⽅法的重要技巧是能够看到⼤问题的规模和
所谓规模的单位。在⼤整数相乘中⼤问题的规模就是⼀个n位的整数要乘以⼀个
m位的整数，所谓规模的单位就是“位”。⽽“分”的⽬的就是把⼤规模拆分为⼩规
模，把⼩单位转变为⼤单位，这两句是⼀个意思，也就是说我们可以把规模n变
成n/2和n/2（把以1位为单位规模为n的问题 变成
以n/2为单位的规模为2的问题），把规模m
变成m/2和m/2（把以1位为单位规模为m的问题 变成
以m/2为单位的规模为2的问题），如此，原来的⼤整数相乘就变成了两个2位
数相乘，只不过低位向⾼位的进制不再是10，⽽是和。更⼀般地，我们把整数A
由规模n分为n1和n2，把整数B由规模m 分为m1和m2，如下图：
则A分为n1位的A1和n2位，B分为m1位的B1和m2位的B2，如下式所⽰：
；
;
以此类推，我们可以把A1、A2、B1、B2继续划分，直⾄最⼩单位。（这⾥在编
程时需要⽤递归来实现）
治：
上⾯讲的很清楚了，那么A和B的相乘就可以表⽰为：
现在是要计算四个⼤整数相乘，我们可以通过变换使得上式变成三个⼤整数相
乘，如下式：（从上式到下式的思路没想到，可能是缺乏经验吧，待⼤神指点
。）
*上述讲解纯属个⼈见解，欢迎提出问题。
C++实现代码：
下⾯实现的是输⼊两个⼤数，A和B，输出AxB的解。
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
string multi(string A, string B); //计算⼤整数相乘
string Plus(string q, string w, string e, string r); //计算⼤整数相加
资源评论
