《彩虹7号》解题报告
   
　　　　　　　　　　　　　　　　　　　　　　福州第三中学 许靖凡
一、 题意简述：

　　本题要求是求X开N次方的M位有效数字值。

二、算法分析：

　　本题采用的算法是穷举逐位推出每一位有效数字的值。设当前计算到S的第i位有效数字，具体流程如下：

　　1. 设S的第i位有效数字为9。
　　2. 计算的值。
　　3. 若小于或者等于X，则继续计算第i+1位有效数字，否则将S的第i位有效数字减1，并返回步骤2。
　　算法较为直观，并无太大难度。但为了求得，每次尝试都需要（N-1）次的高精度乘法运算，因此在N较大时，程序运行的时间难以满足题目的要求。所以我们需要考虑一种方法以较少高精度乘法运算次数的优化方法。
　　当我们得到一个高精度数A的时候，通过1次高精度乘法运算（A*A）可以得到，不难看出，我们可以通过k次高精度乘法得到，所以要计算，只需要k次而不是次的高精度乘法运算。由此我们得到一种启发，可以将以类似的方法计算。
我们将N以若干个的形式表示，流程如下：

　　1． 设 。
　　2． 将记录，将N赋值为N-。
　　3． 若N>0则返回第1步，否则结束。

　　例如，当N=9时，则N表示为，这样只需要4次高精度乘法便可以得到（4次高精度乘法分别是计算以及），远少于原来所需要的9次高精度乘法，算法的效率得到了提高。

　　三、小结：

　　本题采用的优化是一种类似于二分法的方法。因此，在解题过程中，算法的类比与移植尤其重要。


　　　　　　　　　　　　　　　　　　　　　　　　　

    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有