《算法設(shè)計》中一道探究題的解析

《算法設(shè)計》中一道探究題的解析 崇明中學陳超 一、題目提出 一次聽課時，授課教師用“小明有只密碼鎖的拉竿箱，忘記了密碼，密碼鎖是四位數(shù)字， 只記得這個四位數(shù)前三位為均為1。請問你能幫他解決這個問題嗎？”作為枚舉算法引入的 實例，由于該實例來自于學生身邊，在師生的共同分析研究下，學生較快地理解與掌握了枚 舉算法。 對該實例進行探究后，得到了以下多種算法。 二、算法遞進 1、枚舉法（當時授課教師提供，略作改變） 結(jié)構(gòu)特點：循環(huán)結(jié)構(gòu)嵌套分支結(jié)構(gòu)。 算法分析：循環(huán)結(jié)構(gòu)用于一一列舉；分支結(jié)構(gòu)用于逐一檢驗，并輸出密碼值。 VB代碼如下： Dim key As Integer, i As Integer Randomize Key = Int(10 * Rnd()) i = 0 Do While i <= 9 If i = Key Then Print 1110 + Key End If i = i + 1 Loop 2、改進版枚舉法，消除冗余循環(huán) 結(jié)構(gòu)特點：1、循環(huán)結(jié)構(gòu)嵌套分支結(jié)構(gòu)；2、循環(huán)結(jié)構(gòu)中設(shè)置退出出口。 算法分析：密碼值具有唯一性，所以找到密碼后即可輸出結(jié)果，并退出循環(huán)結(jié)構(gòu)。 (1)、重置循環(huán)變量的值，使循環(huán)的條件不成立，從而實現(xiàn)退出循環(huán)結(jié)構(gòu)。 VB代碼如下: Dim key As Integer, i As Integer Randomize Key = Int(10 * Rnd()) Do While i <= 9 If i = Key Then Print 1110 + Key End If Loop VB代碼如下: Dim key As Integer, i As Integer Randomize Key = Int(10 * Rnd()) Do While i <= 9 If i = Key Then Print 1110 + Key Exit Do End If Loop (1)、當循環(huán)結(jié)構(gòu) VB代碼如下: 3、改變循環(huán)條件的設(shè)置 結(jié)構(gòu)特點：單循環(huán)結(jié)構(gòu)。 算法分析：循環(huán)體為計數(shù)器，循環(huán)條件設(shè)為查找密碼的條件。 VB代碼如下： Dim key As Integer, i As Integer Randomize Key = Int(10 * Rnd()) i = 0 Do While i <> Key i = i + 1 Loop Print 1110 + Key (2)、直到循環(huán)結(jié)構(gòu) Dim key As Integer, i As Integer Randomize Key = Int(10 * Rnd()) i = -1 Do i = i + 1 Loop Until i = Key Print 1110 + key 上述三種算法設(shè)計思路從易到難，而算法結(jié)構(gòu)由繁到簡。通過算法的解析，培養(yǎng)了學生 的探究精神與創(chuàng)新思維。 三、推進與思考 推進題目：“小明有只密碼鎖的拉竿箱，千位數(shù)與十位數(shù)數(shù)字均為1，請設(shè)計算法找到 VB代碼如下： Dim Key As Integer Dim x As Integer Dim i As Integer Key = 1010 + 100 * Int(10 * Rnd()) Key = Key + Int(10 * Rnd()) x = 0 i = 0 Do While x <> Key x = 1010 + i \ 10 * 100 + i Mod 10 i = i + 1 Loop Print x 思考： 1、 教師要有創(chuàng)新觀念和探究精神，不迷信教材與教參，引導學生努力探求算法的多樣化， 誘發(fā)學生的探究精神與創(chuàng)新思維。 2、 教師要呵護學生的創(chuàng)新意識，學生的智慧和潛能是很大的。例如當我提示“密碼值具有 唯一性”后，就有學生給出了 “重置循環(huán)變量的值”的方法，實現(xiàn)消除冗余循環(huán)。給學生提 供自我表現(xiàn)的平臺，讓學生體驗到成功的滿足和喜悅，激發(fā)進一步追求創(chuàng)新的心向。