SGOI5《彩虹7号》解题报告

大榕树 \ 信息学奥赛 \ 解题报告

SGOI5《彩虹7号》解题报告

原文链接：http://www.mydrs.org/program/list.asp?id=251
B>一、题意简述： 　　本题要求是求X开N次方的M位有效数字值。 二、算法分析： 　　本题采用的算法是穷举逐位推出每一位有效数字的值。设当前计算到S的第i位有效数字，具体流程如下： 　　1. 设S的第i位有效数字为9。 　　2. 计算<IMG height=16 src="http://www.chinaschool.org/aosai/lwjl/images/1012-01.gif" width=13>的值。 　　3. 若<IMG height=16 src="http://www.chinaschool.org/aosai/lwjl/images/1012-01.gif" width=13>小于或者等于X，则继续计算第i+1位有效数字，否则将S的第i位有效数字减1，并返回步骤2。 　　算法较为直观，并无太大难度。但为了求得<IMG height=16 src="http://www.chinaschool.org/aosai/lwjl/images/1012-01.gif" width=13>，每次尝试都需要（N-1）次的高精度乘法运算，因此在N较大时，程序运行的时间难以满足题目的要求。所以我们需要考虑一种方法以较少高精度乘法运算次数的优化方法。 　　当我们得到一个高精度数A的时候，通过1次高精度乘法运算（A*A）可以得到<IMG height=17 src="http://www.chinaschool.org/aosai/lwjl/images/1012-02.gif" width=17>，不难看出，我们可以通过k次高精度乘法得到<IMG height=18 src="http://www.chinaschool.org/aosai/lwjl/images/1012-03.gif" width=141>，所以要计算<IMG height=18 src="http://www.chinaschool.org/aosai/lwjl/images/1012-10.gif" width=48>，只需要k次而不是<IMG height=18 src="http://www.chinaschool.org/aosai/lwjl/images/1012-04.gif" width=29>次的高精度乘法运算。由此我们得到一种启发，可以将<IMG height=16 src="http://www.chinaschool.org/aosai/lwjl/images/1012-01.gif" width=13>以类似的方法计算。 我们将N以若干个<IMG height=19 src="http://www.chinaschool.org/aosai/lwjl/images/1012-05.gif" width=19>的形式表示，流程如下：
　　1．设<IMG height=30 src="http://www.chinaschool.org/aosai/lwjl/images/1012-06.gif" width=78 align=absBottom> 。 　　2．将<IMG height=19 src="http://www.chinaschool.org/aosai/lwjl/images/1012-05.gif" width=19>记录，将N赋值为N-<IMG height=19 src="http://www.chinaschool.org/aosai/lwjl/images/1012-05.gif" width=19 align=absBottom>。 　　3．若N>0则返回第1步，否则结束。
　　例如，当N=9时，则N表示为<IMG height=18 src="http://www.chinaschool.org/aosai/lwjl/images/1012-07.gif" width=37>，这样只需要4次高精度乘法便可以得到<IMG height=16 src="http://www.chinaschool.org/aosai/lwjl/images/1012-01.gif" width=13>（4次高精度乘法分别是计算<IMG height=20 src="http://www.chinaschool.org/aosai/lwjl/images/1012-08.gif" width=83>以及<IMG height=19 src="http://www.chinaschool.org/aosai/lwjl/images/1012-09.gif" width=17>），远少于原来所需要的9次高精度乘法，算法的效率得到了提高。
　　三、小结： 　　本题采用的优化是一种类似于二分法的方法。因此，在解题过程中，算法的类比与移植尤其重要。

作者：许靖凡
来源：福州第三中学
时间：2001-10-17

上一篇：动态规划的PASCAL程序
下一篇：SGOI5《足球赛》解题报告