代码之家  ›  专栏  ›  技术社区  ›  asterix

网格中的组合数学

  •  -1
  • asterix  · 技术社区  · 7 年前

    我们有一个13列3行的网格。 在第二行,我们有任何顺序的相同整数。 在第三行,我们写下每列两个整数之差的绝对值。 设N为填充第二行的方式数,以便第三行上有13个不同的整数。 设N(k)为第1行和第2行的整数k出现在同一列中的解数。

    从1到13的k的k x N(k)之和是多少?

    Row 1   1  2  3  4  5  6  7  8  9 10 11 12 13
    Row 2   5 13 12 11 10  7  9  8  6  4  3  2  1 
    Row 3   4 11  9  7  5  1  2  0  3  6  8 10 12
    

    N(8) ,我要补充一点 8 * N(8) 作为要求总和中的该项。

    1 回复  |  直到 4 年前
        1
  •  1
  •   Prune    7 年前

    让我们来看一下问题第一阶段的单个解决方案。我们会让 k=8 对于本例:

    Row 1   1  2  3  4  5  6  7  8  9 10 11 12 13
    Row 2   5 13 12 11 10  7  9  8  6  4  3  2  1 
    Row 3   4 11  9  7  5  1  2  0  3  6  8 10 12
    

    因为每个解决方案 必须 如果第3行包含整数0-12,则 总是 在第1行和第2行的同一列中正好是一个元素。

    现在,假设有两个解决方案 8 是那个元素;你会包括 8 * 2 在你的总数中。

    我会通过蛮力(带回溯的递归放置函数)来解决这个问题。找到所有的解,然后简单地将每个解中的“稳定”元素求和。这是你的最终答案。