主页 / 问题 / 717724
Accepted
Родион Поляков
Asked:2020-09-13 10:47:06 +0000 UTC2020-09-13 10:47:06 +0000 UTC

表格单元格中单词的分布

  • 772

我有一个多维数组。

var array = [
    [
        'один',
        'два',
        'три',
        'четыре'

        // всего 16 букв
    ]
];

来自的单词列表array[0]必须放在一个表格中，每个字母是表格的一个单独的单元格。表中单词的位置无关紧要。主要任务是让它们在一侧可读。

|о|д|и|н|     |ч|е|т|ы|
|ч|е|р|т|     |т|д|о|р|
|е|т|ы|р|     |р|в|д|е|
|д|в|а|и| или |и|а|и|н|

在我看来，不分青红皂白地将它们插入字母是不现实的。整个问题是有些词可以“扭曲”（我不知道如何正确地说出来）。例子：

| | | | |     |ч|е|т|ы|
|ч|е|р| |     | | | |р|
|е|т|ы| |     | | | |е|
| | | | | или | | | | |

将单词解析为字母：

for(var value = 0; value < array[0].length; value++) { 
    for (var index = 0; index < array[0][value].length; index++) { 
        // console.log(array[0][value][index]);
    } 
}

重要的细微差别：

  1. 字母总数可以超过 16 个。
  2. 横向可以有4个以上的单元格，按计划，它们的数量是可选的var cells = 4;。
  3. 垂直方向上可以有多少个单元格来容纳所有单词。
  4. 不应有空单元格。

例子：

cells = 4     cells = 4
| | | | |     | | | | |
| | | | |     | | | | |
| | | | |     | | | | |
| | | | | или | | | | |
16 букв       | | | | |
              20 букв

第 3 天，从 10:00 到 23:00，我一直在做这个任务。对我来说是一个非常复杂的算法。我很乐意为任何有关实施的理事会提供帮助。

javascript

1 个回答

  1. Best Answer

    问题不够具体。我猜作者的意思如下：

    给定N中的一组单词：

    在此处输入图像描述

    让数字M (== 16)给定。有必要找到总长度等于M的单词数。

    解决方案 1

    请注意，作为对象的词，我们并不感兴趣。我们只对它们的长度感兴趣。我们用 表示它们的长度l_i。那些。现在我们有了一个词长序列（我们甚至应该称它们为一个集合）：

    <code>X = {l_0, l_1, ..., l_N}</code>

    让我们从数学上严格地陈述这个问题（它与解决方案间接相关）。

    A_k在这种情况下，我们需要了解在我们的集合上是否存在至少一个方程的解X：

    <code>A_k: x_0 + x_1 + x_2 + ... + x_k = M</code>

    那些。方程有解吗

    <code>x0 = M</code>

    或者

    <code>x_0 + x_1 = M</code>

    等等

    x_i可以从集合中X取值的次数有限。

    继续作出决定

    我们需要找到一个l_i加起来为的组合M。

    对序列进行排序

    <code>l_0, ..., l_i, ..., l_N</code>

    按降序排列并丢弃所有那些：

    <code>l_i>M</code>,

    因为他们将无法参与最终总和。排序后我们有：

    <code>s_0, s_1, ..., s_p</code>,

    在哪里

    <code>s_i <= M, s_i >= s_{i+1}</code>.

    现在我们需要遍历所有的解决方案（因为M=16，即很小，那么我们将完全适合枚举）。对于枚举，我们将使用DFS。

    我们要怎么做

    1. 让我们来吧s_0。让我们检查一下s_0 != M。如果是，则已找到解决方案。
    2. 让我们尝试为它找到一个数字，s_i这样s_0 + s_i <= M。将不考虑所有选项i。s_0 + s_i > M由于对象是排序的，我们只需要按顺序遍历它们。
    3. 如果s_0 + s_i = M，则找到解决方案。如果没有，那么我们继续搜索。
    4. 那些。选择s_i这样（s_j (j >= i)类似于s_0 + s_i + s_j <= M第 2 项）。

    在某个步骤它可能会变成这样s_0 + s_i + s_{i+1} >= M。在这种情况下，进一步枚举没有意义。这是真的，因为所有元素都已排序。

    您需要返回上一步并找到s_k (k > j). 那些。拿起s_0 + s_i + s_k <= M。如果我们遍历了所有可能的选项，但没有找到等于 的总和M，那么就没有解决方案。

    为了更好地理解如何组织搜索，我将给出伪代码：

    def dfs(s, sum):
    for number in get_next_number(s):
        new_sum = sum + number
        answ = False
        if new_sum == m: # Если нашли решение, то выходим из перебора
            return True
        elif new_sum < m: # Если решение не нашли, то пытаемся взять следующее число и повторить итерацию
            answ = dfs(number, new_sum)
        if answ:
            return True
    return False # Если ни в одном случае не удалось подобрать сумму, то выходим

    dfs您需要从每个可用的号码开始运行s。

    我不能准确地评价难度，但我会给它最高的评价。她绝对不会O(N^3)超时。但应该理解，这是高估了。最有可能的是，实际工作时间将接近O(N^2)甚至O(N log N)

    我还认为可以为动态规划提供更智能的解决方案，特别是将这个问题简化为背包问题。

    另一种解决方案

    对于这个决定，为每个单词分配一个标签1或就足够了0，这将指示该单词是否应作为响应。因此，我们有一个由0和组成的位掩码1。我们需要遍历所有可能的组合（它们2^N），为每个组合计算所选单词的总长度。

    我举个例子：

    один// 长度 4

    два_ // 长度 4

    пять // 长度 4

    три // 长度 3

    четыре // 长度 6

    让M = 12.

    掩码将由 5 位组成。让我们从面具开始00000：

    10000. 话：один。总长度4 != M

    01000. 话：два_。总长度4 != M

    11000. 词语：один, два_. 总长度8 != M

    00100. 话：пять。总长度4 != M

    10100. 词语：один, пять. 总长度8 != M

    11100. 词语：один, два_, пять. 总长度12 == M

    答案可能包括以下词语：[ один, два_, пять]

    我赶紧注意到，算法的计算复杂度很大：O(2^N)。那些。已经有 30 个单词，您将获得足够长的运行算法（一分钟或更长时间）。

    设置网格大小

    至于网格，要设置其尺寸，您可以设置A, B-- 其边的尺寸。根据这些值，您可以生成网格本身。A * B = M

    伪代码

    要排列单词，根据上述算法，您可以使用“zeika”。您按顺序浏览单元格，一次输入一个字母。首先，当然，你应该一个接一个地排列所有的单词：

    words = 'одиндватричетыре'
letters_count = 0
for x in range(0, A):
   if x % 2 == 0:
      line = range(0, B)
   else: 
      line = range(B, 0, -1)
   for y in line:
      matrix[y][x] = words[letters_count]
      letters_count += 1
    • 11

相关问题