谈一道日本高考题的算法优化

开篇：润墨网以专业的文秘视角，为您筛选了一篇谈一道日本高考题的算法优化范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：本文是对2004年一道日本高考题“求x的p次方除以n后的余数”的算法优化，指出原算法的理论可行性与实际操作的不可性之间的矛盾，并采用scilab语言描述了优化后的算法．

关键词：算法优化；循环

自1999年3月日本文部省颁布新的《学习指导要领》后，高考试卷数学Ⅱ•B中经常出现程序设计题，其中2004年的第六题涉及的知识点有循环语句、常用对数和位数等． 编程的内容涉及整数、余数和位数等． 试题中体现了对算法的优化思想．本文在此基础上，提出一种更为优化的算法．

原题：制作这样一个程序，输入自然数x，p和n，输出计算除以n后的余数．

注意：当计算机在执行此程序时，不能处理263以上的数值． 这里，INT（x）表示不超过x的最大整数的函数．另外lg2=0.3010，需要时可用．

【程序1】

（1）程序1中，从120行到140行时语句，FOR…NEXT…用来求xp的．

A可从下列提供的7个选项中选择其一．

①P；②2?鄢P；③P?鄢P；④P?鄢X；⑤A；⑥N；⑦X.

另外，150行是表示求xp除以n后的余数．

B可从下列提供的6个选项中选择其一．

①INT（A/N）； ②INT（A/N）?鄢N； ③A-INT（A/N）； ④A+INT（A/N）；⑤A-INT（A/N）?鄢N；⑥A+INT（A/N）?鄢N.

（2）在10进制中是 位数，当x=4，p≥ 时；当x=8，p≥ 时，分别使得xp≥263，而据程序1的计算，此计算机不能处理．

注意：在 、 中分别填上符合条件的最小的自然数．

（3）对程序1，（2）中已经谈到的关于改善x和p的大小范围，利用下列性质改变程序（设为S，T自然数，S，T除以的余数分别为s，t，这时s

【程序2】

程序2中的110行是计算x除以n后的余数． I

可从下列提供的6个选项中选择其一．

①INT（X/N）； ②INT（X/N）?鄢N； ③X-INT（X/N）； ④X+INT（X/N）；⑤X-INT（X/N）?鄢N；⑥X+INT（X/N）?鄢N.

执行程序2，在变量x，p，n中分别输入数据8、25、5，这是110行的B的值为 J． 从130句到160句是FOR…NEXT…语句，其中140句中A?鄢B的所有值中其最大值为 ．

执行一次循环语句（从130句到160句）所需时间是10-8秒，忽略计算机处理其他行的时间． 当p=262时，设计算机执行程序2所需的时间为s秒，则10≤s＜10+1．

分析：程序2的算法明显比程序1的算法优化，能够处理的数据突破界限，但是当p=262时，从最后程序执行的时间看，需要1010～1011秒，即317年～3170年左右的时间，说明理论上确实对算法进行了优化，但实际操作时耗时太多，有点不切实际．借助算论的知识（设为S，T自然数，S，T除以的余数分别为s、t，这时s

程序设计主要分为这样两大步：

（1）拆分数P． 输入的正整数P（大于1）如果是偶数，则拆分为两个相等的整数，如果是奇数，则拆分为两个相邻的自然数，依此循环执行，直到P＝1，把得到的数据存储在一维数组a中，且随着下标i的增加，ai的值在递减． 如图2，当数P是18时，数组a中的元素对应关系如图3．

图2

（2）计算余数． 先算x1（相当于xai-1）除以n所得的余数，把它记为s，再算xai-2除以n所得的余数，把它记为t，然后令u=i－3，当u>0时执行循环，每执行一次循环，先计算新的s，再根据au-1和au是否相等计算新的t，同时u值减2，因为i的初值为奇数，所以u的初值为偶数，当u=0时，退出循环．最后的余数yushu就是xa2乘以xa1除以n所得的余数（因为a1+a2=P）．

说明：

（1）程序3算法的优越性主要体现在大大减少循环执行的次数． 如当x，p，n的值分别为9、262、7时，程序1、2需运算262次循环，按照执行一次循环需要10-8秒，总共需花费时间约为1.28×107小时），而用程序3只需运算不到100次循环，所需时间不足1秒，由此足以看出它比程序1、2的优越性．

（2）程序3用的算法有点类似“折半法”，拆分指数P时一分为“二”，计算余数时合二为“一”．

（3）在进行算法教学时，可以进行（最）优化教学的案例有很多：如求质数问题，求最大公约数问题、求多项式的值的问题，过河问题等等． 如果我们在平时多积累，多思考，让学生在学习算法部分的内容时，敢于挑战自我，向最优化的目标靠拢． 那么，思维的逻辑性、严密性、发散性等都将在此得到很好的训练．