算法设计技术是设计算法的一般方法，可用于解决不同计算领域的各 种问题。有下列的一般方法： •蛮力法。采用一定的策略依次处理待求解问题的所有元素，从而找 出问题的解。时间性能最差。 •基于问题分解（求解时间与问题规模有关）的思想：
•分治法。将复杂问题分解成若干独立的子问题，通过求解子问题 并将解合并得到原问题的解。 •减治法。同样分解问题，但只需求解某个子问题，也无须合并解， 退化的分治法。 •动态规划。将复杂问题分解成若干相互重叠的子问题，通过保存 和重复利用重叠的子问题的解来减少计算量。 •贪心法。把复杂问题分解为一系列较为简单的局部最优选择，每 一步选择都是对当前解的扩展，直到获得问题的完备解。 •基于搜索的思想：回溯法、分支限界法
算法设计与分析—本科生课程
Design and Analysis of Algorithm
第3章 蛮力法
Brute force method
海南大学信息科学技术学院 College of Information Science and Technology, Hainan University
基本的算法设计技术
2. {
3. int a,b,c;
4. k = 0;
5. for (a=0;a<=n;a++)
6.
for (b=0;b<=n;b++)
7.
for (c=0;c<=n;c++) {
8.
if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) {
9.
g[k] = a;
10.
2
第3章 蛮力法
本章要点：
3.1 概述：蛮力法的设计思想 3.2 查找问题中的蛮力法（顺序查找、串匹配问题） 3.3 排序问题中的蛮力法（选择排序、起泡排序） 3.4 组合问题中的蛮力法（0/1背包、任务分配） 3.5 图问题中的蛮力法（哈密尔顿回路、TSP问题） 3.6 几何问题中的蛮力法（最近对、凸包问题） 阅读材料——KMP算法中next值的计算
m[k] = b;
11.
s[k] = c;
12.
k++;
13.
}
14. } } }
17. }
2020/3/7
Chapter 3 Brute force method
11
蛮力法的设计思想
6
蛮力法的设计思想
蛮力法所依赖的基本技术——遍历（扫描）技术 关键——依次处理所有元素 遍历技术：可确保处理过的元素不再被处理）
（1）集合的遍历：按集合中元素序号的顺序处理各元素 （2）线性表的遍历：以数组形式存储，按下标顺序处理 （3）树的遍历：对二叉树，包括前序、中序、后序和层序 （4）图的遍历：深度优先、广度优先
2020/3/7
Chapter 3 Brute force method
3
第3章 蛮力法
教学重点
蛮力法的设计思想，各种经典问题的蛮力思想
教学难点
串匹配问题，凸包问题
教学内容及目 知识点 标
了解
蛮力法设计思想
顺序查找
串匹配问题
选择排序和起泡排序
0/1背包问题
任务分配问题
哈密尔顿回路
TSP问题 最近对问题 凸包问题
a+b+c=n
(4)
5a+3b+c/3=n
(5)
输入：所购买的三种鸡的总数目n
输出：满足问题的解的数目k,公鸡,母鸡,小鸡的 只数g[ ], m[ ], s[ ]
2020/3/7
Chapter 3 Brute force method
10
蛮力法的设计思想
1. void chicken_question(int n,int &k,int g[],int m[],int s[])
如已知：公钥为：KU={e, n}，私钥为： KR={d, n}，则 对明文m的加密/解密算法如下：
加密 明文： M<n 密文： C=Me (mod n)
密文： 明文：
解密 C M=Cd (mod n)
注：计算an算法的效率直接影响到RSA算法的性能
2020/3/7
Chapter 3 Brute force method
例：计算an
an=a×a×…×a
n次 注：最简单的想法就是把 a 和 a 相乘 n 次。
2020/3/7
Chapter 3 Brute force method
5
蛮力法的设计思想
一个RSA算法应用实例
a n 值的计算是非对称加密算法RSA的重要组成部分。RSA 的加密/解密过程都需要求一个整数的的整数次幂再取模。
2020/3/7
Chapter 3 Brute force method
7
蛮力法的设计思想
因要穷举待处理的元素，故蛮力法的时间性能往往最低， 但基于以下原因，蛮力法也是一种重要的算法设计技术：
（1）理论上，蛮力法可以解决可计算领域的各种问题。 （2）蛮力法经常用来解决一些较小规模的问题。 （3）对于一些重要的问题（例如排序、查找等）蛮力法 可以产生一些合理的算法，他们具备一些实用价值，而且 不受问题规模的限制。 （4）蛮力法可以作为某类问题时间性能（不是复杂性， 两者恰好相反）的下界，来衡量同样问题的更高效算法。
2020/3/7
Chapter 3 Brute force method
8Байду номын сангаас
蛮力法的设计思想
例 百鸡问题。
“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱 一。百钱买百鸡，问鸡翁、母、雏各几何？”
a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程：
a+b+c=100
(1)
5a+3b+c/3=100
(2)
C%3=0
(3)
2020/3/7
Chapter 3 Brute force method
9
蛮力法的设计思想
解法1：
a、b、c的可能取值范围：0 ~ 100，对在此范 围内的，a、b、c的所有组合进行测试，凡是满 足上述三个约束方程的组合，都是问题的解。
把问题转化为用n元钱买n只鸡，n为任意正整数， 则方程（1）与（2）转换为：
2020/3/7
Chapter 3 Brute force method
教学要求 理解 掌握
√
√ √ √
√ √ √
熟练掌握 √ √
√
4
3.1 概述：蛮力法的设计思想
蛮力法中“力”是指计算机的“计算能 力”，不是人的智“力”。
蛮力法的设计思想：直接基于问题的描述， 从有限集合中，逐一列举集合的所有元素， 对每一个元素逐一判断和处理，从而找出 问题的解。