计算机算法设计的基本方法(1)

频道:六六互联 日期: 浏览:723

计算机算法设计基本方法(1)

穷举法:

定义:又称枚举法或称为暴力破解法,列举出它的所有可能的情况,逐个判断有哪些是符合问题所要求的条件,从而得到问题的解。

思想:通过采用搜索方法,根据题目的部分条件确定答案的大致搜索范围,在此范围内对所有可能的情况逐一验证。若某个情况符合题目的条件,则为本题的一个解;若全部情况验证完后均不符合题目的条件,则问题无解。

基本步骤

例3-1:求满足表达式A+B=C的所有整数解,其中A,B,C为1-3之间的整数。

分析:

第一步:确定A,B和C为三个解变量

第二步:A,B和C的取值范围分别为A∈{1,2,3}, B∈{1,2,3}和C∈{1,2,3}。

     第三步:穷举各种情况,用判断语句找出满足条件的解。

例3-1的N-S图:

例3-2:百钱百鸡问题。假定小鸡每1元3只,公鸡每只5元,母鸡每只3元。现在有100元钱要求买100只鸡,列出所有可能的购鸡方案

分析:

例3-2的N-S图