資源描述：
《枚舉法解決百元買百雞.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、枚舉法實(shí)例信息工程學(xué)院主講教師：門瑞什么是枚舉法信息工程學(xué)院基本思想枚舉也稱窮舉，指的是從問(wèn)題可能的解的集合中一一列舉各元素。用題目給定的條件判定哪些是無(wú)用的，哪些是有用的。能使命題成立，即為其解。本質(zhì)上屬于搜索算法什么是枚舉法信息工程學(xué)院特點(diǎn)容易理解，步驟單一。得到的結(jié)果肯定是正確的。通常會(huì)涉及到求極值（如最大，最小等）。數(shù)據(jù)量大的話，可能會(huì)造成時(shí)間崩潰。引子信息工程學(xué)院【例1】以下式子中的每個(gè)漢字代表一個(gè)數(shù)字，求出這些漢字代表的數(shù)字分別是多少？慕課制作組X慕組組組組組組枚舉法信息工程學(xué)院計(jì)算
2、機(jī)解決枚舉問(wèn)題算法簡(jiǎn)單、精確度高。常用多重循環(huán)解決枚舉問(wèn)題(while循環(huán)、for循環(huán))。效率低——當(dāng)問(wèn)題的規(guī)模變大，循環(huán)的階數(shù)增加，執(zhí)行的速度嚴(yán)重變慢。百元買百雞問(wèn)題【例2】雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一。百錢買百雞，問(wèn)雞翁、母、雛各幾何？解題思路：設(shè)雞翁、雞母、雞雛的數(shù)量分別為x，y，z，則有以下方程x+y+z=1005x+3y+z/3=100此三元一次方程有多個(gè)解，可用枚舉法求解。信息工程學(xué)院百元買百雞問(wèn)題C語(yǔ)言解法一：main(){intx,y,z;for(x=1;x<=
3、100;x++)for(y=1;y<=100;y++)for(z=1;z<=100;z++)if((z%3==0)&&(x+y+z==100)&&(5*x+3*y+z/3==100))printf(“雞翁%d只，雞母%d只，雞雛%d只",x,y,z);}信息工程學(xué)院百元買百雞問(wèn)題C語(yǔ)言解法一：信息工程學(xué)院main(){intx,y,z;for(x=1;x<=100;x++)for(y=1;y<=100;y++)for(z=1;z<=100;z++)if((z%3==0)&&(x+y+z==1
4、00)&&(5*x+3*y+z/3==100))printf(“雞翁%d只，雞母%d只，雞雛%d只",x,y,z);}枚舉次數(shù)：100*100*100=100萬(wàn)次！百元買百雞問(wèn)題限定變量的取值范圍x的取值范圍是1<=x<=20y的取值范圍是1<=y<=33減少循環(huán)的層數(shù)、判斷時(shí)間z=100-x-y信息工程學(xué)院有沒(méi)有更好的解法呢？百元買百雞問(wèn)題C語(yǔ)言解法二：main(){intx,y,z;for(x=1;x<=20;x++)for(y=1;y<=33;y++)if(((100-x-y)%3==
5、0)&&(5*x+3*y+(100-x-y)/3==100)){z=100-x-y;printf(“雞翁%d只，雞母%d只，雞雛%d只",x,y,z);}}枚舉次數(shù)：20*33=660次！百元買百雞問(wèn)題有沒(méi)有更好的解法呢？信息工程學(xué)院百元買百雞問(wèn)題x+y+z=1005x+3y+z/3=100y=25-7/4*xz=75+3/4*xx=4ky=25-7kz=75+3k化簡(jiǎn)令x=4k分析題意可知：k只能取1,2,3信息工程學(xué)院百元買百雞問(wèn)題C語(yǔ)言解法三：main(){intk;for(k=1;k
6、<=3;k++)printf(“雞翁%d只，雞母%d只，雞雛%d只",4k,25-7k,z);}枚舉次數(shù)：3次！信息工程學(xué)院枚舉法信息工程學(xué)院優(yōu)化策略對(duì)問(wèn)題多加分析，減少循環(huán)重?cái)?shù)和次數(shù)。合理選擇用于枚舉的變量。減少每種情況的判斷時(shí)間。是否有其他更好的方法。知識(shí)拓展信息工程學(xué)院試用枚舉法解決以下兩個(gè)問(wèn)題從1—10的10個(gè)數(shù)中，每次取2個(gè)數(shù)，要使它們的和大于10，一共有多少種取法？從學(xué)校到少年宮有4條東西走向的馬路和3條南北走向的馬路，小明從學(xué)校步行到少年宮（只許向東或向南行走），最多有多少種走
7、法？謝謝觀看信息工程學(xué)院主講教師：門瑞
