fer*_*ith 13 java algorithm primes functional-programming
|---|---|---|---|---|
| 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 - The Primes做一个问题.
我已经构建了大部分辅助函数......
问题:问题是我不知道如何填充数组或使用回溯功能继续检查:(.任何人都可以帮我吗？如何填写2D数组以便它包含来自素数表的值各方面的总和是否正确？
*NB:生成5位数素数的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
根据您所写的内容，我假设您已经有了一个 5 位数素数列表。过滤列表，使其仅包含数字总和正确的素数。
您需要一个 valid 函数来检查一个有效的方块，给定列中的 1 到 5 个数字。（很明显，列号决定了其他行和对角线。因此，如果第一列的第 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、an 和 c3 的情况，valid() 将检查第 3 行。它采用 c1、c2 和 c3 的第 3 位数字，我们可以将它们解释为必须出现的数字的前 3 位数字在第 3 行中。我们只需要用零填充它，然后可以检查我们是否知道大于该数字的质数，但差值必须小于 100（以便保留前导数字）。但是，如果我们有一个候选素数的排序数组，则只需要在该数组中进行二分搜索即可。