1

我们如何将一组数字划分为序列?并找到通用术语?

1 - 数字总是有序的

2 - 如果我们有 n 个数字 n/2 数字总是存在

例如我们有:

Input: 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30
Output--> 2*X, x=[0..15]

或者

Input: 0,2,4,5,6,8,10,12,14,15,16,18,20,22,24,26,28,30

分成两组

A: 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30

B: 5,10,15,20

Output--> 2*X, x=[0..15] AND 5*X, x=[1..4]

我觉得这很难,有什么意见吗?

什么计算机领域或算法可以帮助我?

4

1 回答 1

0

据我了解,问题是这样的:给定一个数字序列,找到从零开始并以覆盖该集合的常数倍数增加的序列集。

这是我将要做的事情的大致轮廓:

我将列出集合中的所有数字,并从前两个元素开始迭代以生成满足您的标准的所有可能集合。如果您在列表中遇到一个元素,您可以将其从作为生成数字的考虑中删除,因为任何将该数字作为常数倍数的列表都是您之前遇到的列表的子集。完成后,您将获得一个可能的集合列表,您可以使用它来覆盖该集合。例如:

0,2,4,5,6,8,10,12,14,15,16,18,20,22,24,26,28,30

我们将从 0 和 2 开始。我们将查找连续大 2 的元素,并将它们从将被视为可能的倍数的元素列表中删除。一旦我们找到不在此列表中的 2 的倍数,我们将停止生成。开始了:

s(2) = [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30]

留下:

[5,15] 

作为两个潜在的其他候选人。您是否看到任何可被 2 整除的元素(例如 4)将成为该列表的子集,因此不需要考虑?

集合中的剩余列表将从 0 开始并增加 5,这是我们最小的元素:

[0,5,10,15,20]

(请记住,我们正在检查这些倍数的原始列表而不是截断列表 - 截断列表只是剩余候选者的列表。当候选者列表为空时,我们知道我们将找到包含在该集合中的所有集合谁没有超集。

对于更复杂的示例:

[0 2 3 4 5 6 7 8 9 10 12 13 14 15]

我们将从:

[0 2 4 6 8 10 12 14]

留下 [3 5 7 9 13 15]

作为候选人,这反过来会产生:

[0 3 6 9 12 15]

离开

[5 7 13]

这会产生

[0 5 10 15]

离开

[7 13]

这会产生

[0 7 14]

离开

[13]

这会产生

[0 13].

集合的总组合是:

[0 2 4 6 8 10 12 14]
[0 3 6 9 12 15]
[0 5 10 15]
[0 7 14]
[0 13].

此时,您拥有覆盖您的集合所需的所有集合的最小列表。从这里生成正确的 [0,1...n]/a*n 描述符应该很简单。

于 2013-02-15T17:28:53.750 回答