2022/12/2 算法设计与分析-蛮力法 1第3章蛮力法3.1概述3.2查找问题中的蛮力法3.3排序问题中的蛮力法3.4组合问题中的蛮力法3.5图问题中的蛮力法3.6几何问题中的蛮力法2022/12/2 算法设计与分析-蛮力法 23.1概述蛮力法(穷举法)，是一种简单而直接地解决问题的方法。设计思想：直接基于问题的描述。n次an= a a a例：计算an3.1.1蛮力法的设计思想2022/12/2 算法设计与分析-蛮力法 3应用实例: 计算an的值是RSA算法的主要组成部分。 RSA算法的加密和解密过程都需要一个整数的整数次幂再取模。n 例如，设公钥为(5,119)，私钥为(77,119)，明文m=19，则加密得密文c为：n c=195 mod 119=2 476 099 mod 119=66n 解密得明文m为：n m=6677 mod 119=19n 计算an算法的效率直接影响到RSA算法的性能。2022/12/2 算法设计与分析-蛮力法 4n蛮力法所依赖的基本技术扫描技术n关键依次处理所有元素 n基本的扫描技术遍历（1）集合的遍历（2）线性表的遍历（3）树的遍历（4）图的遍历 2
