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