枚舉法解決百元買百雞

1、LOGO枚舉法實例信息工程學(xué)院主講教師：門瑞LOGO什么是枚舉法信息工程學(xué)院信息工程學(xué)院v基本思想 枚舉也稱窮舉，指的是從問題可能的解的集合中一一列舉各元素。 用題目給定的條件判定哪些是無用的，哪些是有用的。能使命題成立，即為其解。 本質(zhì)上屬于搜索算法LOGO什么是枚舉法信息工程學(xué)院信息工程學(xué)院v特點 容易理解，步驟單一。 得到的結(jié)果肯定是正確的。 通常會涉及到求極值（如最大，最小等）。 數(shù)據(jù)量大的話，可能會造成時間崩潰。LOGO引子信息工程學(xué)院信息工程學(xué)院【例1】以下式子中的每個漢字代表一個數(shù)字，求出這些漢字代表的數(shù)字分別是多少？ 慕課制作組X 慕組組組組組組LOGO枚舉法信息工程學(xué)院信息工

2、程學(xué)院v計算機解決枚舉問題 算法簡單、精確度高。 常用多重循環(huán)解決枚舉問題(while循環(huán)、for循環(huán))。 效率低當問題的規(guī)模變大，循環(huán)的階數(shù)增加，執(zhí)行的速度嚴重變慢。LOGO百元買百雞問題【例2】雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾何？解題思路：設(shè)雞翁、雞母、雞雛的數(shù)量分別為x，y，z，則有以下方程x+y+z=1005x+3y+z/3=100此三元一次方程有多個解，可用枚舉法求解。信息工程學(xué)院信息工程學(xué)院LOGO百元買百雞問題C語言解法一：main() int x, y, z; for(x=1;x=100;x+) for(y=1;y=100;y+)

3、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只n,x,y,z);信息工程學(xué)院信息工程學(xué)院LOGO百元買百雞問題C語言解法一：信息工程學(xué)院信息工程學(xué)院main() int x, 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=100)&(5*x+3*y+z/3=100) printf(“雞翁%d只，雞母%d只，雞雛%d只n,x,y,z);枚舉

4、次數(shù)：100*100*100=100萬次！LOGO百元買百雞問題限定變量的取值范圍x的取值范圍是1=x=20y的取值范圍是1=y=33減少循環(huán)的層數(shù)、判斷時間z=100-x-y信息工程學(xué)院信息工程學(xué)院有沒有更好的解法呢？ LOGO百元買百雞問題C語言解法二：main() int x,y,z; for(x=1;x=20;x+) for(y=1;y=33;y+) if(100-x-y)%3=0)&(5*x+3*y+(100-x-y)/3=100) z=100-x-y; printf(“雞翁%d只，雞母%d只，雞雛%d只n,x,y,z); 枚舉次數(shù)：20*33=660次！LOGO百元買百雞問

5、題有沒有更好的解法呢？ 信息工程學(xué)院信息工程學(xué)院LOGO百元買百雞問題x+y+z=1005x+3y+z/3=100y=25-7/4*xz=75+3/4*x x=4k y=25-7k z=75+3k化簡令x=4k 分析題意可知：k只能取1,2,3信息工程學(xué)院信息工程學(xué)院LOGO百元買百雞問題C語言解法三：main() int k; for(k=1;k=3;k+) printf(“雞翁%d只，雞母%d只，雞雛%d只n,4k,25-7k,z);枚舉次數(shù)： 3次！信息工程學(xué)院信息工程學(xué)院LOGO枚舉法信息工程學(xué)院信息工程學(xué)院v優(yōu)化策略 對問題多加分析，減少循環(huán)重數(shù)和次數(shù)。 合理選擇用于枚舉的變量。 減少每種情況的判斷時間。 是否有其他更好的方法。LOGO知識拓展信息工程學(xué)院信息工程學(xué)院v試用枚舉法解決以下兩個問題 從110的10個數(shù)中，每次取2個數(shù)，要使它們的和大于10，一共有多