5x5 网格中的五位数素数

algorithm functional-programming java primes

2022-09-04 23:15:24

|---|---|---|---|---|
| 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 |
|---|---|---|---|---|

（图1）

图 1 显示了一个正方形。每行、每列和两个对角线都可以读作一个五位数的素数。行从左到右读取。列从上到下读取。两个对角线都是从左到右读取的。使用 INPUT.TXT 文件中的数据，编写一个构造此类正方形的程序。

质数必须具有相同的数字总和（示例中为 11）。正方形左上角的数字是预先确定的（示例中为 1）。

一个素数可以在同一个平方中多次使用。

如果有多个解决方案，则必须提供所有解决方案。五位数素数不能以零开头，即00003不是五位数素数。

输入数据

11 1

我试图从IOI'94竞赛 - 问题3 - Primes中做一个问题。

我已经构建了大部分的帮助程序函数...

使用Eratosthenes的Sieve生成5位素数（在9999和100000之间）
构建了一个函数来计算数字总和（12345 = 1+2+3+4+5 = 15）
构建了一个函数来检查数组，如果数字总和在整个过程中相同
构建了一个函数来检查数字是否开始使用指定的数字（startWith（12345，1）返回 true）

问：问题是我不知道如何填满阵列或使用回溯功能来继续检查:(。任何人都可以帮我吗？我如何填充2D数组，以便它包含来自素数表的值，并且总和在所有角度上都是正确的？

*注意：生成5位素数的Eratosthenes的Sieve of Eratosthenes方法，也作为过滤以X开头的值并且值的总和为M *的能力

完整问题： http://olympiads.win.tue.nl/ioi/ioi94/contest/day1prb3/problem.html

增加价值的预期顺序，只是不知道如何:(。

 1  2  3  4  5
 6 13 14 12 15
 7 16 11 18 19
 8 10 20 22 23
 9 17 21 24 25

答案 1

从你写的东西来看，我假设你已经有了一个5位数素数的列表。筛选列表，使其仅包含具有正确数字总和的素数。

您需要一个有效的函数来检查有效的平方，给定列中的 1 到 5 个数字。（很明显，列号决定了其他行和对角线。因此，如果第 1 列的第 3 位数字是 7，但没有以 7 开头的素数，我们知道我们不能在第一列中使用这个素数。如果不查看所有其他数字，这将提前修剪搜索树。

您需要另一个函数来获取在位置 n （1..5）处具有特定数字的所有有效素数的集合。也许你想预先计算它并将其存储在某个树或数组中。

主要工作在 valid 中完成，这必须检查行和对角线是否存在素数，其中数字位于到目前为止由列中的素数确定的位置。

然后解决方案列表是：

[ (c1, c2, c3, c4, c5) | c1 <- primes, valid [c1], 
      c2 <- primes, valid [c1,c2],
      c3 <- primes, valid [c1,c2,c3],
      c4 <- primes, valid [c1,c2,c3,c4],
      c5 <- primes, valid [c1,c2,c3,c4,c5] ]

或者，命令式地：

 for each c1 in primes
    if valid(c1) then foreach c2 in primes
        if valid(c1,c2) then foreach c3 in primes
            if valid(c1,c2,c3) then foreach c4 in primes
                 if valid(c1,c2,c3,c4) then foreach c5 in primes
                      if valid(c1,c2,c3,c4,c5) then print solution

附录：由于我们只需要查找以某些数字的连续数开头的数字，因此解决方案可以更加有效。考虑这样一种情况：给出了 c1，c2，annd c3，并且 valid（）即将检查第 3 行。它采用 c1、c2 和 c3 的第 3 位数字，我们可以将它们解释为必须出现在第 3 行中的数字的前 3 位。我们只需要用零填充它，然后就可以检查我们是否知道一个大于这个数字的素数，但差值必须小于100（以便保留前导数字）。但是，如果我们有一个候选素数的排序数组，这只需要在该数组中进行二进制搜索。

答案 2