基于枚舉算法的問題解決課件2024-2025學(xué)年高一上學(xué)期高中信息技術(shù)必修1第2章人教中圖版

2.4.2基于枚舉算法的問題解決年級(jí)：高一年級(jí)學(xué)科：信息技術(shù)（人教/中圖版）復(fù)習(xí)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)解析算法根據(jù)問題的前提條件與所求結(jié)果之間的關(guān)系，找出求解問題的數(shù)學(xué)表達(dá)式，并通過表達(dá)式的計(jì)算來實(shí)現(xiàn)問題的求解生活中的枚舉在一筐水果中找出壞掉的水果扔掉在一串鑰匙中找出所有能打開這把鎖的鑰匙忘記了三位數(shù)密碼箱的密碼一個(gè)一個(gè)查看，然后去除壞的水果一把一把地試，找到然后取出從000開始，001，002…………找到正確密碼后記下來共同點(diǎn)？一一列舉逐一檢驗(yàn)概念：枚舉法是依據(jù)問題的已知條件，確定答案的大致范圍，在此范圍內(nèi)列舉出它所有可能情況的方法。不遺漏不重復(fù)檢驗(yàn)條件（一）枚舉算法的概念及特征一一列舉循環(huán)結(jié)構(gòu)（for語句、while語句）逐一檢驗(yàn)分支結(jié)構(gòu)（if判斷語句）（二）枚舉算法實(shí)現(xiàn)方法for（列舉所有可能解）:if(判斷條件）：

輸出解也可以使用while語句實(shí)現(xiàn)（二）枚舉算法實(shí)現(xiàn)方法枚舉算法基本框架：票據(jù)上有一個(gè)4位數(shù)字組成的編號(hào)：甲說：數(shù)字編號(hào)的前兩位數(shù)字相同，但都不是零；乙說：數(shù)字編號(hào)的后兩位數(shù)字是相同的，但與前兩位不同；丙說：數(shù)字編號(hào)是一個(gè)整數(shù)的平方。

根據(jù)以上線索推斷出編號(hào)。活動(dòng)一（三）如何設(shè)計(jì)枚舉算法例：票據(jù)中模糊數(shù)字推斷問題。1.分析問題已知條件：假設(shè)4位數(shù)字的編號(hào)是AABB，其中A≠0，A≠B，且AABB是一個(gè)整數(shù)的二次方；求解目標(biāo)：票據(jù)中的數(shù)字變量A變量B變量k變量c枚舉對(duì)象枚舉范圍檢驗(yàn)條件AB1—9之間的整數(shù)0—9之間的整數(shù)A≠Bc*c=k（三）如何設(shè)計(jì)枚舉算法一一列舉逐一檢驗(yàn)枚舉對(duì)象枚舉范圍檢驗(yàn)條件AB1—9之間的整數(shù)0—9之間的整數(shù)A≠Bc*c=k2.設(shè)計(jì)算法importmathforAinrange(1,10):forBinrange(0,10):ifA!=B:k=A*1000+A*100+B*10+Bc=int(math.sqrt(k))#求票據(jù)中數(shù)字的平方根并取其整數(shù)部分

ifc*c==k:#若k是完全平方數(shù)，則找到該票據(jù)編號(hào)

print("票據(jù)編號(hào)是：",k)3.編程調(diào)試（三）如何設(shè)計(jì)枚舉算法4.保存文件，運(yùn)行程序（四）枚舉算法應(yīng)用

活動(dòng)二今有雉兔同籠，上有三十五頭，下有九十四足，問雉兔各幾何？（雉兔至少有一只）分析問題雞兔頭的數(shù)量腳的數(shù)量111+1=21*2+1*4=6121+2=31*2+2*4=10131+3=41*2+3*

4

=14…………34134+1=3534*2+1*4=7213雞兔腳的數(shù)量1341*2+34*4=1382332*2+33*4=1363323*2+32*

4

=1344314*2+31*4=132………34134*2+1*4=72我們發(fā)現(xiàn)雞和兔子頭數(shù)量和為35方案總數(shù)瞬間少了很多14一一列舉可能的解，即枚舉范圍是多少？雞的數(shù)量：1~34逐一檢驗(yàn)可能的解，判斷條件是什么？雞與兔共94只腳2*chicken+4*rabbit==94分析問題15設(shè)計(jì)算法16一一列舉逐一檢驗(yàn)循環(huán)執(zhí)行34*34次編寫程序17一一列舉逐一檢驗(yàn)循環(huán)執(zhí)行34次算法優(yōu)化枚舉算法要注意的問題不能遺漏任何一個(gè)正確解盡可能地縮小解的列舉范圍，提高算法的效率可以用枚舉算法解決嗎破解密碼求方程2x+y=9的整數(shù)解尋找1000以內(nèi)的所有素?cái)?shù)求方程2x+y=9的正整數(shù)解求方程2x+y=9的實(shí)數(shù)解一名警察抓獲了4個(gè)盜竊嫌疑犯A、B、C、D，他們的供詞如下：A說：“不是我偷的”；B說：“是A偷的”；C說：“不是我”；D說：“是B偷的”。他們4個(gè)人中只有一個(gè)人說了真話，小偷是誰？（四）枚舉算法應(yīng)用（五）小結(jié)23編寫程序解決以下問題：1：從2000年到2050年，哪些年份是閏年？能夠被4整除但不能被100整除的是閏年能夠被400整除的也是閏年2：尋找1000以內(nèi)的所