算法评价穷举算法评价穷举一个问题？算法评价算法评价信息学夏令营倪震祥信息学夏令营倪震祥算法复杂度表格信息学夏令营倪震祥举例子举例子信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥算法评价穷举一、穷举法信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥穷举法的优点：⑴由于穷举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；⑵由于穷举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。穷举法的缺点：穷举算法的效率取决于穷举状态的数量以及单个状态穷举的代价，因此效率比较低。信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥排列信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥五、如何优化穷举算法信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥信息学夏令营倪震祥回溯的概念回溯的概念回溯的一般描述回溯的一般描述回溯的一般描述回溯的代码框架n皇后问题n皇后问题n皇后问题回溯与穷举回溯与递归回溯与递归n皇后问题--递归近年竞赛题分析火柴棒等式（noip2008)Hankson的趣味题（noip2009）问题1：火柴棒等式【问题描述】给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1.加号与等号各自需要两根火柴棍2.如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）3.n根火柴棍必须全部用上。【输入】输入文件matches.in共一行，又一个整数n（n<=24）。【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。问题分析：本题选自noip2008提高组试题。设等式三个变量为A、B、C，如果已知A和B，则C=A+B。由于题目给出的火柴数目范围很小，选择枚举算法，枚举A、B值，求得C值，累计满足等式A+B=C所用的火柴数目为输入值即获得问题的解。对于本题，我们能否从细节上提高枚举算法的效率呢？1．根据n<=24条件，确定枚举A和B的范围。即如果都使用最少火柴的数字（如数字1）构造表达式中的数，得到最大的数是多少，可以算出该数<1000，因此A和B的范围为0~1000；2、在枚举表达式过程中，需要反复计算每个数所用的火柴数目，即相同的数有可能重复计算许多次的火柴数目，显然，需要想办法减少重复计算。先进行预处理，将估算范围内的数所用的火柴数目算出；3、枚举过程中如果当前数的火柴数目超过输入限制做剪枝处理。算法描述：预处理：求0~2000数对应的火柴数目；使用循环枚举A值0~1000，执行下列操作：判断A值的火柴数目是否超过限制值，是的，剪枝，跳过该数的处理；否，使用循环枚举B值0~1000，执行下列操作：①判断A和B值的火柴数目和是否超过限制值，是的，剪枝，跳过该数的处理；②否，求C值，若A、B、C值火柴数目和等于限制值，计数方案数；3．输出方案数。3、枚举A和B，判断累计最后输出。程序框架：readln(n);f[0]:=6;f[1]:=2;f[2]:=5;f[3]:=5;f[4]:=4;//0~9需要的火柴棒数f[5]:=5;f[6]:=6;f[7]:=3;f[8]:=7;f[9]:=6;fori:=10tomaxn*2do//预处理0~2000每个数需要的火柴棒数beginx:=i;whilex>0dobeginf[i]:=f[i]+f[xmod10];x:=xdiv10;end;end;ans:=0;n:=n-4;//总火柴棒数减去'+'和'='所需的火柴棒数fori:=0tomaxndo//枚举Abeginiff[i]>=nthencontinue;//剪枝，继续i循环forj:=0tomaxndo//枚举Bbeginiff[i]+f[j]>=nthencontinue;//剪枝，继续j循环k:=i+j;i