二进制幂问题求解论.doc

《算法设计与分析》 实验报告 专业： 计算机科学与技术 班级： 0491102 学号： 2011211645、 2011211635、2011211634 姓名： 曹元、齐豫、金晓迎 题目名称： 二进制幂问题求解 指导老师： 于洪 2013/12/19  目录 二进制幂问题求解 1 1、引言............................................................................................................1 2、问题的提出 2 3、问题的解决 2 4、算法描述 4 5、数据结构介绍（定义，描述） 6、分析（实验，理论） 7、心得体会 8 8、参考文献 10 9、附录： 11  二进制幂问题求解 1、引言 为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，算法学得到了飞速发展，动态规划、贪心算法、分治法等一系列运筹学模型纷纷运用到算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得更好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整后，性能仍无法达到要求，这时就必须寻求另外的方法来求解问题。 变治法是基于变换的思想，分为两个阶段：“变”阶段和“治”阶段，“变”即变换问题更容易求解，“治”即对变换后的问题求解。变治法包含了3中基本类型：实例化简、改变表现、问题化简，用框图表示如下： 2、问题的提出 我们经常会遇到这样的问题：已知x,求多项式 的值的问题，以及该问题的一个特例---计算。当用霍纳法则来计算，即当x=a是的值时，霍纳法则实际上就退化成了一种对a自乘的蛮力算法，其中还夹杂着一些无用的加法。为此，我们找到了基于改变表现思想的二进制幂算法。 3、问题的解决 设n是一正整数的二进制串，n=bI…bi…b0，则可用下面的多项式来计算n的值： 我们先应用霍纳法则来计算这个多项式的值： 但是， 因此，把这个累乘器的值初始化为a之后，我们可以扫描表示指数的比特串，并总是对累乘器的必威体育精装版值进行平方。而且，如果当前的比特位是1，还要把存储变量乘以a。这是计算的从左到右的二进制幂算法。 从右到左的二进制幂算法使用了相同的二进制多项式p(2)来表示n的值。但是并不像从左到右二进制幂算法那样对多项式运用霍纳法则，该算法以一种不同的方式来使用这个多项式： 因此，可以用各项 的积来计算，也就是连续项的积，其中跳过了那些二进制位为0的项。此外我们可以简单的对前面项的计算结果进行平方来计算，因为。所以。我们可以从最小值到最大值，计算a的所有这样的乘方，但我们只把那些相应的二进制位为1的项包括在累乘器中。 用从左到右的二进制幂算法计算，这里。因此有下面从左到右填写的表格： 用从右到左的二进制幂算法计算，得到如下从右到左填写的表格： 4、算法描述 (从左到右算法为代码 LeftRightBinaryExponentiation(a,b(n)) //用从左到右的二进制幂算法计算 //输入：一个数字a和二进制位bI,...,b0的列表b(n)，这些位来自于一个正整数n的二进制展开式 //输出：的值 product←a for i←I-1 downto 0 do product←product*product if bi=1 product←product*a return product (从右到左算法为代码 RightLeftBinaryExponentiation(a,b(n)) //用从右到左的二进制幂算法计算 //输入：一个数字a和二进制位bI,...,b0的列表b(n)，这些位来自于一个正整数n的二进制展开式 //输出：的值 term←a //初始化 if b0=1 product←a else product←1 for i←1 to I do term←term*term if bi=1 product←product*term return product 5、数据结构介绍（定义，描述） String s