《3.2.1穷举法分析》优质课教案下载

《3.2.1穷举法分析》优质课教案下载

设1分有x个，2分有y个，5分有z个，则有：x+2y+5z=100（其中0≤x≤100,0≤y≤50,0≤z≤20），求满足该条件的方案总数。可以借助计数循环穷举所有可能，找出满足条件的解即可。

【伪代码】

置计数器tot初值为零；

枚举所有的1分的情况

枚举所有2分的情况

枚举所有5分的情况

满足兑换条件（x+2y+5z=100）则计数器增加1；

输出计数器的值即可。

【参考程序片段】

int tot=0;

for(int x=0;x<=100;x++)

for(int y=0;y<=50;y++)

for(int z=0;z<=20;z++)

if (x+2y+5z==100)tot++;

cout<

【算法反思】

该程序执行效率为1015121=108171，即循环要做108171次。由题意知x+2y+5z=100，可以得到x=100-2y-5z，只要满足x大于等于零即可，由此可以减少一个循环，程序的执行效率变为5121=1071次，程序效率大大提升。

【伪代码】

置计数器tot初值为零；

枚举所有2分的情况

枚举所有5分的情况

满足兑换条件（100-2y-5z>=0）则计数器增加1；

输出计数器的值即可。

【参考程序片段】

int tot=0;