目录
(2)时间复杂度分析：上式一共需要进行2次xn0的乘法（AC、AD各一次）、2次yn0的乘法（AC、BC各一次）和3次加法，因而该算法的时间复杂度为
实验1 利用减治法和分治法来处理同一个问题
一、实验目的
1. 掌握减治法和分治法的思想，熟练掌握顺序表基本算法的实现。
2. 掌握利用利用减治法和分治法解决同一问题的思路。
3. 分析核心代码的时间复杂度和空间复杂度。
二、实验内容和要求
编写一个程序实现任意大整数（没有上限）之间的四则运算，并必须使用第四章的俄式乘法和第五章的大整数乘法来完成。
【俄式乘法函数原型及功能说明】
俄式乘法，又被称为俄国农夫法，是我们考虑对两个数相乘的非主流算法，假设n和m是两个正整数，我们要计算它们的乘积，同时我们用n的值作为实例规模度量标准。如果n是偶数，则n x m=n/2 x 2m，如果n是奇数，则需对公式做轻微的调整：
n x m= (n-1)/2 x 2m +m。 并且以1 x m=m作为算法结束条件。在n等于奇数时依次加上m的结果一直到m等于1时，最后的值即为最开始相乘的值
【核心函数实现代码及时间复杂度与空间复杂度分析】
（1）俄式乘法实现代码
int Russia(int n, int m)
{
int sum = 0,a=0;
while (n != 1){
//n为偶数
if (n % 2 == 0)
{
n = n / 2;
m *= 2;
printf("%d %d\n", n, m);
}
//n为奇数
else{
n = (n - 1) / 2;
a += m;
m = m * 2;
printf("%d %d\n", n, m);
}
}
sum=m + a;
return sum;
}
（2）时间复杂度：O（log（底数为2）n）
（3）空间复杂度：无递归算法，为S（1）
完整代码
#include "stdio.h"
int Russia(int n, int m)
{
int sum = 0,a=0;
while (n != 1){
if (n % 2 == 0)//n为偶数
{
n = n / 2;
m *= 2;
printf("%d %d\n", n, m);
}
else{//n为奇数
n = (n - 1) / 2;
a += m;
m = m * 2;
printf("%d %d\n", n, m);
}
}
sum=m + a;
return sum;
}
int main()
{
int n, m,mul;
printf("请输入要相乘的两个数：");
scanf("%d%d", &n, &m);
mul=Russia(n, m);
printf("最后结果为:%d\n", mul);
}【大整数乘法函数原型及功能说明】
- 两个大整数在理想状态下：就是两个大整数的位数相同
现在有两个大整数X,Y;
设X, Y是n位十进制整数，即 X=A*10^(n/2)+B, Y=C*10^(n/2)+D 则:
本来可以直接算AD+BC，但是这样效率变低了，所以对AD+BC进行分解优化后得：
- 两个大整数在非理想状态下：就是两个大整数的位数不相同
我们还是假设有两个大整数X、Y，它们的位数不相同，现在要求X*Y的乘法，我们采用分治的算法，将X、Y分别拆分为A与B、C与D，
【核心函数实现代码及时间复杂度与空间复杂度分析】
文章评论