巧用列表法解決循環(huán)結(jié)構(gòu)問題

李鵬

算法中主要涉及三種基本邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，其中循環(huán)結(jié)構(gòu)是這三者中最重要的一種結(jié)構(gòu).很多同學(xué)對循環(huán)結(jié)構(gòu)中變量的變化情況的掌握存在比較大的困難，具體表現(xiàn)在隨著循環(huán)次數(shù)的增加，對某些變量的變化情況逐漸變得模糊、混淆，進(jìn)而對循環(huán)的起點(diǎn)條件、循環(huán)次數(shù)、循環(huán)終止條件、最終結(jié)果、循環(huán)功能等無法準(zhǔn)確把握.

如何才能突破循環(huán)結(jié)構(gòu)問題的難點(diǎn)呢？建議同學(xué)們利用列舉法，通過列舉去追蹤循環(huán)結(jié)構(gòu)中的變量，明確各個變量在進(jìn)入循環(huán)體后的值，觀察和歸納出變量在退出循環(huán)時應(yīng)輸出的值，進(jìn)而得到問題的答案.本文將針對不同的題型，通過列表法追蹤變量的變化，來揭示列表法對解決循環(huán)結(jié)構(gòu)問題的作用.

一、求輸出結(jié)果

例1 執(zhí)行如圖1所示的偽代碼，輸出的值為

解 偽代碼的程序語句執(zhí)行中的數(shù)據(jù)變化如表1所示，當(dāng)S<20時可執(zhí)行循環(huán)體，當(dāng)S≥20時退出循環(huán)，此時輸出i=11.

點(diǎn)評 本題主要考查“當(dāng)型”循環(huán)語句，通過對程序語言的讀取，再根據(jù)所給循環(huán)結(jié)構(gòu)，判斷出S≥20時的輸出結(jié)果.由程序運(yùn)行過程看，這是一個累加的問題.解題時，可通過對條件S<20的判斷，逐步演算S的結(jié)果，通過判斷，可知該程序演算過程需運(yùn)行5次，i的值變?yōu)?1，此時程序不再進(jìn)入循環(huán)體，繼而輸出.

總結(jié) ①無論是“直到型”還是“當(dāng)型”循環(huán)結(jié)構(gòu)，列表時均以判斷框或判斷語句作為計(jì)算每一組變量值的起始；

②列表時，表中的變量白左至有的順序應(yīng)與循環(huán)體中各變量發(fā)生變化的先后順序保持一致，便于明確每個變量的當(dāng)前值是哪次循環(huán)得到的.例2 執(zhí)行圖2的程序框圖，如果輸入的x=0，y=l，n=l，則輸出x，y的值滿足（

）A.y=2x

B.V=3xC.V=4x

D.V=5x

解 由表2可得，當(dāng)x=3/2，y=6時，程序框圖退出循環(huán)，故滿足y=4x的關(guān)系式，選C.

點(diǎn)評 本題的循環(huán)結(jié)構(gòu)中，循環(huán)體看起來好像被判斷框分成了兩部分：x，y在判斷框前開始第一次變化，而n在判斷框后才開始第一次變化.當(dāng)抓住了“判斷框作為計(jì)算每一組變量值的起始”這個關(guān)鍵點(diǎn)，第一組變量的值就不難確定為n=2，x=1/2，y=2”，而不是“x=0，y=1，n=2”；同時也不難確定，列表中變量的先后順序是”在前，而x，y在后.

二、求循環(huán)初值

例3 某算法流程圖如圖3所示，該程序運(yùn)行后，若輸出的x=15，則實(shí)數(shù)a等于

解 如表3所示，第一次循環(huán)x=2a+1，n=2，第二次循環(huán)x=4a+3，n=3，第三次循環(huán)x=8a+7，n=4>3，結(jié)束循環(huán)輸出x=8a+7=15，a=1.

點(diǎn)評 本題根據(jù)判斷框內(nèi)的條件，通過列表法列舉出循環(huán)結(jié)束時所輸出的x，再令其結(jié)果8a+7=15，解出所求的a的值.特別注意，如果列舉時次數(shù)過多，可以采用部分列舉，再尋求規(guī)律，進(jìn)而歸納出結(jié)果.

例4程序的框圖如圖4，如果上述程序運(yùn)行的結(jié)果為S=132，那么判斷框中橫線上應(yīng)填入的數(shù)字是

解 由流程圖可知，此程序目的是求幾個數(shù)的連乘積，第一次乘入的數(shù)是12，以后所乘的數(shù)依次減少1，由于132=11×12，如表所示，可知一共循環(huán)兩次，當(dāng)k=11時，要滿足循環(huán)條件，而當(dāng)k=10時退出循環(huán)，故判斷框中可填k≤10.

點(diǎn)評 本題要求寫出循環(huán)條件，只要用列表法得到與輸出的S值對應(yīng)的k值，判斷框內(nèi)的條件便可確定.

四、求循環(huán)次數(shù)

例5 如圖5所示的程序框圖中循環(huán)體執(zhí)行的次數(shù)是______.

解 如流程圖所示，首先執(zhí)行循環(huán)體，再進(jìn)行條件判斷.根據(jù)列表不難發(fā)現(xiàn)，最后一次執(zhí)行循環(huán)體是當(dāng)“i=98+2 =100”時，然后退出循環(huán)并輸出S，所以循環(huán)體執(zhí)行次數(shù)為49次.

點(diǎn)評 本題是根據(jù)循環(huán)結(jié)構(gòu)求循環(huán)體執(zhí)行次數(shù)的問題，一般來說此類題型中流程圖循環(huán)體執(zhí)行次數(shù)比較多，可以通過列表法分析得到計(jì)數(shù)變量i和求和變量S的變化規(guī)律，再判斷循環(huán)體執(zhí)行的次數(shù).

含循環(huán)結(jié)構(gòu)的流程圖、偽代碼問題是算法學(xué)習(xí)中的重點(diǎn)和難點(diǎn)，將其表格化進(jìn)行列舉，尋找規(guī)律，是一個簡單、有效的方法.對循環(huán)結(jié)構(gòu)本質(zhì)的理解始終是解決這類問題的基礎(chǔ)，列表法用來追蹤循環(huán)語句中的變量，記錄其變化情況.列表不僅條理清晰、易于觀察，而且可以幫助同學(xué)們更容易理解循環(huán)結(jié)構(gòu)，化繁為簡.endprint