algorithm - 数字金字塔算法 : Numbers 1-15 in a pyramid where each number is the difference of the subjacent numbers

Question

首先:抱歉标题太长了，但我发现很难用一句话来解释这个问题；)。是的，我也四处搜索(这里和谷歌)，但找不到合适的答案。

所以，问题是这样的:

数字 1-15 将像这样放在金字塔中(由数组表示):

       1
     2   3
   4   5   6
  7  8   9   10
11 12  13  14  15

...除非真的不是这样，因为这个金字塔是错误的。

每个数字“a”都应该由其下方的两个数字“b”和“c”定义:a = |b - c|。所以前两行是正确的，因为 |2-3| = 1。但是第三行当然是错误的，因为|4-5| = 1，但在这些数字之上有一个 2。一开始，金字塔是空的，任务是寻找一个算法来填充这个金字塔。

对我来说，这似乎是一个可以使用某种 Backtracking 解决的问题。算法，虽然我还不太确定递归的基本情况是什么。

尽管如此，我正在努力帮助我的侄子，在他学校的类里面，他们还没有听说过任何关于递归的事情——更不用说回溯了。所以我目前正在尝试找到一种方法来使用某种嵌套的 for 循环或其他东西来解决这个金字塔，但老实说......我目前正在碰壁，我只是想不出一个合适的解决方案。

有人有什么想法吗？

干杯，

/tehK

P.s:哦，我忘了...他们应该使用的语言是 C#(金字塔应该是一个数组)，但我也可以处理任何其他语言、伪代码或你有什么。这与编码无关，而与算法有关。

Answer 1

最后一行有 15*14*13*12*11=360360 种可能。一旦你有了底行，金字塔的其余部分就确定了。所以简单地遍历每一种可能性，看看它是否不包含重复的数字。可以通过回溯对其进行优化，但您要求不进行回溯。

示例代码:

import itertools

def pyramid():
    for b in itertools.combinations(range(1, 16), 5):
        for xs in itertools.permutations(b):
            rows = [xs]
            while len(rows[-1]) != 1:
                rows.append(tuple(abs(a-b) for a, b in zip(rows[-1], rows[-1][1:])))
            used = sum(rows, ())
            if all(1 <= i <= 15 for i in used) and len(set(used)) == 15:
                yield rows

for p in pyramid():
    for row in p[::-1]:
        print ' ' * 2*(5-len(row)) + '  '.join('% 2d' % n for n in row)
    print

输出:

         5
       4   9
     7   11   2
   8   1   12   10
 6   14   15   3   13

         5
       9   4
     2   11   7
   10   12   1   8
 13   3   15   14   6

找到的两个解本质上是一样的(一个是另一个的镜像)