談一道日本高考題的算法優(yōu)化

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