所有位置的可能取值情况 ◆枚举逐个确定矩阵中的 每个元素: 9999 ■最左一列、最上一行元 91010104 素不为0。 ■根据质数的限制,最右 91010104 列、最下一行不能是 91010104 偶数,也不能是5 m则每个位置的可能取值94444 的情况如右图:
4 4 9 9 所有位置的可能取值情况 枚举逐个确定矩阵中的 每个元素： 最左一列、最上一行元 素不为0。 根据质数的限制，最右 一列、最下一行不能是 偶数，也不能是5。 则每个位置的可能取值 的情况如右图： 9 9 10 9 10 10 10 10 10 4 4 4 9 10 10 9 10 9 4 4 4 4
策略:选择适当的枚举顺序 ◆减少枚举次数: 某些元素可以由已知元素直[ abc d e 接确定(和为S) 适当选择每个元素确定的顺 序,可以减少枚举次数。 g pk 顺序确定原则:尽量由已知「h 元素确定未知元素。 右图是一种枚举顺序: y
策略：选择适当的枚举顺序 减少枚举次数： 某些元素可以由已知元素直 接确定（和为 S ）。 适当选择每个元素确定的顺 序，可以减少枚举次数。 顺序确定原则：尽量由已知 元素确定未知元素。 右图是一种枚举顺序： a b c d e f m n l o g p k r s h j t v w i q u x y
质数的判断 ◆质数的判断:如何提高判断的效率? ◆方法1:sqrt(100000316,小于316 的质数有65个,事先记录在数组中。 如果这个五位数不能被这65个质数中 的任何一个整除则必为质数。 ◆方法2:事先求出所有和为S的所有五位 质数(最多757个,S=23时取到), 记录在数组中。每次质数判断用二分法 进行查找即可
质数的判断 质数的判断：如何提高判断的效率？ 方法1：sqrt (100000) ＝ 316，小于316 的质数有65个，事先记录在数组中。 如果这个五位数不能被这65个质数中 的任何一个整除则必为质数。 方法2：事先求出所有和为S的所有五位 质数（最多757个，S = 23时取到）， 记录在数组中。每次质数判断用二分法 进行查找即可
质数方阵题小结 ◆算法效率分析: 减少枚举次数 ◆现在的方法需要枚举多少次?还能不能更快? 减少判断每种情况的时间 ◆质数判断的两种优化方法各最多需要几次判断? ◆小试牛刀 http://acm.pku.edu.cn/judgeonline/showproblEm?problemid=1l 65
质数方阵题小结 算法效率分析 ： http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1 1 65 小试牛刀 减少枚举次数 减少判断每种情况的时间 现在的方法需要枚举多少次？还能不能更快？ 质数判断的两种优化方法各最多需要几次判断？
24宴会上的彩灯☆ 在举行宴会的房间的一面墙上,30盏 彩灯排成5行6列,每盏灯带有1个开 左右的灯都会转变状态。它和它上下 关。按动某盏灯的开关 开关的状态 有230种可 宴会之后,这些彩灯有开有关,愁煞 管理员。如何才能将这些彩灯统统 关上呢? 关灯游戏 Turnofflight swf
2.4 宴会上的彩灯 在举行宴会的房间的一面墙上，30盏 彩灯排成5行6列，每盏灯带有1个开 关。按动某盏灯的开关，它和它上下 左右的灯都会转变状态。 宴会之后，这些彩灯有开有关，愁煞 了管理员。如何才能将这些彩灯统统 关上呢？ 关灯游戏 TurnoffLight.swf 开关的状态 有230种可能