談一道日本高考題的算法優化

　　摘 要：本文是對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）在進行算法教學時，可以進行（最）優化教學的案例有很多：如求質數問題，求最大公約數問題、求多項式的值的問題，過河問題等等． 如果我們在平時多積累，多思考，讓學生在學習算法部分的內容時，敢于挑戰自我，向最優化的目標靠攏． 那么，思維的邏輯性、嚴密性、發散性等都將在此得到很好的訓練．