摘 要：本文是對(duì)2004年一道日本高考題“求x的p次方除以n后的余數(shù)”的算法優(yōu)化，指出原算法的理論可行性與實(shí)際操作的不可性之間的矛盾，并采用scilab語(yǔ)言描述了優(yōu)化后的算法．
　　關(guān)鍵詞：算法優(yōu)化；循環(huán)
　　
　　自1999年3月日本文部省頒布新的《學(xué)習(xí)指導(dǎo)要領(lǐng)》后，高考試卷數(shù)學(xué)Ⅱ?B中經(jīng)常出現(xiàn)程序設(shè)計(jì)題，其中2004年的第六題涉及的知識(shí)點(diǎn)有循環(huán)語(yǔ)句、常用對(duì)數(shù)和位數(shù)等． 編程的內(nèi)容涉及整數(shù)、余數(shù)和位數(shù)等． 試題中體現(xiàn)了對(duì)算法的優(yōu)化思想．本文在此基礎(chǔ)上，提出一種更為優(yōu)化的算法．
　　原題：制作這樣一個(gè)程序，輸入自然數(shù)x，p和n，輸出計(jì)算除以n后的余數(shù)．
　　注意：當(dāng)計(jì)算機(jī)在執(zhí)行此程序時(shí)，不能處理263以上的數(shù)值． 這里，INT（x）表示不超過x的最大整數(shù)的函數(shù)．另外lg2=0.3010，需要時(shí)可用．
　　【程序1】
　?。?）程序1中，從120行到140行時(shí)語(yǔ)句，F(xiàn)OR…NEXT…用來求xp的．
　　A可從下列提供的7個(gè)選項(xiàng)中選擇其一．
　?、貾；②2?鄢P；③P?鄢P；④P?鄢X；⑤A；⑥N；⑦X.
　　另外，150行是表示求xp除以n后的余數(shù)．
　　B可從下列提供的6個(gè)選項(xiàng)中選擇其一．
　　①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.
　?。?）在10進(jìn)制中是 位數(shù)，當(dāng)x=4，p≥ 時(shí)；當(dāng)x=8，p≥ 時(shí)，分別使得xp≥263，而據(jù)程序1的計(jì)算，此計(jì)算機(jī)不能處理．
　　注意：在 、 中分別填上符合條件的最小的自然數(shù)．
　?。?）對(duì)程序1，（2）中已經(jīng)談到的關(guān)于改善x和p的大小范圍，利用下列性質(zhì)改變程序（設(shè)為S，T自然數(shù)，S，T除以的余數(shù)分別為s，t，這時(shí)s　　【程序2】
　　程序2中的110行是計(jì)算x除以n后的余數(shù)． I
　　可從下列提供的6個(gè)選項(xiàng)中選擇其一．
　?、買NT（X/N）； ②INT（X/N）?鄢N； ③X-INT（X/N）； ④X+INT（X/N）；⑤X-INT（X/N）?鄢N；⑥X+INT（X/N）?鄢N.
　　執(zhí)行程序2，在變量x，p，n中分別輸入數(shù)據(jù)8、25、5，這是110行的B的值為 J． 從130句到160句是FOR…NEXT…語(yǔ)句，其中140句中A?鄢B的所有值中其最大值為 ．
　　執(zhí)行一次循環(huán)語(yǔ)句（從130句到160句）所需時(shí)間是10-8秒，忽略計(jì)算機(jī)處理其他行的時(shí)間． 當(dāng)p=262時(shí)，設(shè)計(jì)算機(jī)執(zhí)行程序2所需的時(shí)間為s秒，則10≤s＜10+1．
　　分析：程序2的算法明顯比程序1的算法優(yōu)化，能夠處理的數(shù)據(jù)突破界限，但是當(dāng)p=262時(shí)，從最后程序執(zhí)行的時(shí)間看，需要1010～1011秒，即317年～3170年左右的時(shí)間，說明理論上確實(shí)對(duì)算法進(jìn)行了優(yōu)化，但實(shí)際操作時(shí)耗時(shí)太多，有點(diǎn)不切實(shí)際．借助算論的知識(shí)（設(shè)為S，T自然數(shù)，S，T除以的余數(shù)分別為s、t，這時(shí)s　　程序設(shè)計(jì)主要分為這樣兩大步：
　?。?）拆分?jǐn)?shù)P． 輸入的正整數(shù)P（大于1）如果是偶數(shù)，則拆分為兩個(gè)相等的整數(shù)，如果是奇數(shù)，則拆分為兩個(gè)相鄰的自然數(shù)，依此循環(huán)執(zhí)行，直到P＝1，把得到的數(shù)據(jù)存儲(chǔ)在一維數(shù)組a中，且隨著下標(biāo)i的增加，ai的值在遞減． 如圖2，當(dāng)數(shù)P是18時(shí)，數(shù)組a中的元素對(duì)應(yīng)關(guān)系如圖3．
　　
　　圖2
　?。?）計(jì)算余數(shù)． 先算x1（相當(dāng)于xai-1）除以n所得的余數(shù)，把它記為s，再算xai-2除以n所得的余數(shù)，把它記為t，然后令u=i－3，當(dāng)u>0時(shí)執(zhí)行循環(huán)，每執(zhí)行一次循環(huán)，先計(jì)算新的s，再根據(jù)au-1和au是否相等計(jì)算新的t，同時(shí)u值減2，因?yàn)閕的初值為奇數(shù)，所以u(píng)的初值為偶數(shù)，當(dāng)u=0時(shí)，退出循環(huán)．最后的余數(shù)yushu就是xa2乘以xa1除以n所得的余數(shù)（因?yàn)閍1+a2=P）．
　　說明：
　?。?）程序3算法的優(yōu)越性主要體現(xiàn)在大大減少循環(huán)執(zhí)行的次數(shù)． 如當(dāng)x，p，n的值分別為9、262、7時(shí)，程序1、2需運(yùn)算262次循環(huán)，按照?qǐng)?zhí)行一次循環(huán)需要10-8秒，總共需花費(fèi)時(shí)間約為1.28×107小時(shí)），而用程序3只需運(yùn)算不到100次循環(huán)，所需時(shí)間不足1秒，由此足以看出它比程序1、2的優(yōu)越性．
　?。?）程序3用的算法有點(diǎn)類似“折半法”，拆分指數(shù)P時(shí)一分為“二”，計(jì)算余數(shù)時(shí)合二為“一”．
　?。?）在進(jìn)行算法教學(xué)時(shí)，可以進(jìn)行（最）優(yōu)化教學(xué)的案例有很多：如求質(zhì)數(shù)問題，求最大公約數(shù)問題、求多項(xiàng)式的值的問題，過河問題等等． 如果我們?cè)谄綍r(shí)多積累，多思考，讓學(xué)生在學(xué)習(xí)算法部分的內(nèi)容時(shí)，敢于挑戰(zhàn)自我，向最優(yōu)化的目標(biāo)靠攏． 那么，思維的邏輯性、嚴(yán)密性、發(fā)散性等都將在此得到很好的訓(xùn)練．