正在加载图片...
选择适当的枚举量 92.3质数方阵 递推关系式 右下图表示了一个方阵,沿 R0=RI/2*3+2 行、沿列及两个对角线的5个11351 ◆RI=R2 数字均组成一个5位的质数 33203 R2=R3/2*3+2 拥蕉互貧 对于行,自左向右读数;对于30323 R3=R4/4*5+1 列,自上向下读数;对于对角 R4=R5/4*5+1 线,两个对角线均自左向右读 33311 R5=R6/4*5+ 数 R6=R7/4*5+1 R7=R8/4*5+1 质数方阵 所有位置的可能取值情况 ◆现在给定两个数和A,编程 个确定矩阵中 按以下要求构成方阵 不能是11351 每个元素: 零,例如0000是位质数 33203 最左一列、最上一行元9101010 每个质数的各位之和均为s(右30323 14033 根据质数的限制,最右 ·方阵左上角中的数字为A(右图33311 不能是 数,也不能是5 个5位质数在同一方阵中可以 则每个位量的可能取值 被使用多次 的情况如右图 若存在多个解,必须全部给出 策略:选择适当的枚举顺序 质数的判断 ◆减少枚举次数 质数的判断:如何提高判断的效率? ·某些元囊可以由已知元素直 接确定〔和为S) ·方法1;sqrt(100000=316,小于316 适当选择每个元章确定的顺 的质数有65个,事先记录在数组中。 序,可以减少枚举次数 如果这个五位数不能被这65个质微中 的任何一个整除则必为质数 ·顺序确定原则:尽量由已知 元素确定未知元囊 方法2:事先求出所有和为s的所有五位 右图是一种枚举顺 进套教::6次质数判断用二分法3 选择适当的枚举量 R0 = R1 / 2 * 3 + 2 R1 = R2 / 2 * 3 + 2 R2 = R3 / 2 * 3 + 2 R3 = R4 / 4 * 5 + 1 R4 = R5 / 4 * 5 + 1 R5 = R6 / 4 * 5 + 1 R6 = R7 / 4 * 5 + 1 R7 = R8 / 4 * 5 + 1 递推关系式： R0> R1> …R7>R8 是一组相互依赖 的解向量，只需 枚举其中的一 个，应该选择哪 个量进行枚举？ 2.3 质数方阵 右下图表示了一个方阵，沿 行、沿列及两个对角线的5个 数字均组成一个5位的质数。 对于行，自左向右读数；对于 列，自上向下读数；对于对角 线，两个对角线均自左向右读 数。 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 质数方阵 现在给定两个数S和A，编程 按以下要求构成方阵。 5位质数中的第一个数字不能是 零，例如00003不是5位质数。 每个质数的各位之和均为S（右 图中S = 11）。 方阵左上角中的数字为A（右图 中A = 1）。 一个5位质数在同一方阵中可以 被使用多次。 若存在多个解，必须全部给出。 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 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 策略：选择适当的枚举顺序 减少枚举次数： 某些元素可以由已知元素直 接确定（和为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 (100000) ＝ 316，小于316 的质数有65个，事先记录在数组中。 如果这个五位数不能被这65个质数中 的任何一个整除则必为质数。 方法2：事先求出所有和为S的所有五位 质数（最多757个，S = 23时取到）， 记录在数组中。每次质数判断用二分法 进行查找即可