二进制幂问题求解论

《二进制幂问题求解论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》实验报告专业：计算机科学与技术班级：0491102学号：2011211645、2011211635、2011211634姓名：曹元、齐豫、金晓迎题目名称：二进制幂问题求解指导老师：于洪2013/12/19目录二进制幂问题求解11、引言............................................................................................................12、问题的提出23、问题的解决24、算法描述45、数据

2、结构介绍（定义，描述）66、分析（实验，理论）67、心得体会：88、参考文献109、附录：11二进制幂问题求解1、引言为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，算法学得到了飞速发展，动态规划、贪心算法、分治法等一系列运筹学模型纷纷运用到算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得更好的性能，必须对算法进行细致的调整。但

3、是在某些情况下，算法经过调整后，性能仍无法达到要求，这时就必须寻求另外的方法来求解问题。变治法是基于变换的思想，分为两个阶段：“变”阶段和“治”阶段，“变”即变换问题更容易求解，“治”即对变换后的问题求解。变治法包含了3中基本类型：实例化简、改变表现、问题化简，用框图表示如下：132、问题的提出我们经常会遇到这样的问题：已知x,求多项式的值的问题，以及该问题的一个特例---计算。当用霍纳法则来计算，即当x=a是的值时，霍纳法则实际上就退化成了一种对a自乘的蛮力算法，其中还夹杂着一些无用的加法。为此，我们找到了基于改变表

4、现思想的二进制幂算法。3、问题的解决设n是一正整数的二进制串，n=bI…bi…b0，则可用下面的多项式来计算n的值：我们先应用霍纳法则来计算这个多项式的值：但是，13因此，把这个累乘器的值初始化为a之后，我们可以扫描表示指数的比特串，并总是对累乘器的最新值进行平方。而且，如果当前的比特位是1，还要把存储变量乘以a。这是计算的从左到右的二进制幂算法。从右到左的二进制幂算法使用了相同的二进制多项式p(2)来表示n的值。但是并不像从左到右二进制幂算法那样对多项式运用霍纳法则，该算法以一种不同的方式来使用这个多项式：因此，可以

5、用各项的积来计算，也就是连续项的积，其中跳过了那些二进制位为0的项。此外我们可以简单的对前面项的计算结果进行平方来计算，因为。所以。我们可以从最小值到最大值，计算a的所有这样的乘方，但我们只把那些相应的二进制位为1的项包括在累乘器中。13用从左到右的二进制幂算法计算，这里。因此有下面从左到右填写的表格：用从右到左的二进制幂算法计算，得到如下从右到左填写的表格：4、算法描述从左到右算法为代码LeftRightBinaryExponentiation(a,b(n))//用从左到右的二进制幂算法计算//输入：一个数字a和二

6、进制位bI,...,b0的列表b(n)，这些位来自于一个正整数n的二进制展开式13//输出：的值product←afori←I-1downto0doproduct←product*productifbi=1product←product*areturnproduct从右到左算法为代码RightLeftBinaryExponentiation(a,b(n))//用从右到左的二进制幂算法计算//输入：一个数字a和二进制位bI,...,b0的列表b(n)，这些位来自于一个正整数n的二进制展开式//输出：的值term←a//

7、初始化ifb0=1product←aelseproduct←1fori←1toIdoterm←term*termifbi=1product←product*termreturnproduct135、数据结构介绍（定义，描述）在代码中定义的数据变量有：Strings;inta;//（底数a）intn;//（指数n）intres;intproduct;其中值得注意的是，变量s定义的是字符串类型，存放的是指数n的二进制表示。字符串是来自于字母表中的字符序列，并以一个特殊字符来标识字符串的结束。在二进制幂算法中，一个算法从左到

8、右处理这个二进制串，而另一个从右到左进行处理。6、分析（实验，理论）从左至右二进制幂算法在每次重复它唯一循环的时候都要做一到两次乘法，所以它在就算时总的乘法次数M（n）：（b-1）≤M(n)≤2(b-1)其中，b是代表指数n的比特串的长度。考虑b-1=13，我们可以下结论：从左至右二进制幂算法的效率是对数级的。因此，该算法比蛮力幂