算法设计与分析实验：研究减治法和分治法以解决同一类问题

目录

实验1 采用减治策略与分治策略解决相同问题

一、实验目标

二、实验内容与具体要求

【俄式乘法函数定义及其功能描述

实验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）俄式