如果可能的话，请制作一个序列。

Question

如果可能的话，请制作一个序列。

4

如果一个整数序列中，任意相邻两个数之差为 -1 或 1，并且第一个元素是 0，那么这个序列被称作“一序列”。

更具体地说，a1，a2，......，an 是一个一序列��当且仅当：

For any k (1 ≤  k < n): |a[k] - a[k+1]|=1, 
a[1]=0

给定n和s ─ a中所有元素的总和。我们需要构造一个具有给定参数的一序列。

例如，如果n=8且s=4，则这样的一序列之一是[0 1 2 1 0 -1 0 1]。

请注意，如果对于给定的n和s，我们无法形成这样的序列，那么我们也需要告诉它不可能。否则，我们需要告诉任何这样的一序列。如何解决这个问题？请帮忙。

- typedef

1

你尝试过自己解决吗？ - aioobe

@aioobe 嗯，我尝试使用1、0、-1、2来解决问题，并尝试在每个位置放置四个数字中的一个。但问题是我们需要使总和等于S。 - typedef

@GreenAsJade 我不需要任何代码，我只需要一个正确的算法或提示来完成它。 - typedef

提示：使用动态规划和记忆化。 - Kevin

@Kevin，我认为这甚至都不必要。 - aioobe

显示剩余8条评论

2个回答

2

首先，决定是否可以解决问题可以在前期完成。由于每一步只能向上或向下移动1，你将从偶数到奇数再到偶数再到奇数......因此n为奇数时，你只能到达偶数，而当n为偶数时，你只能到达奇数。可达范围也很简单：±(1+2+3+...+n)。

其次，如果你画出每一步该往上(+1)或往下(-1)的“决策树”，并在每个节点中绘制累积和，你会发现你可以进行一种二分搜索，以找到树的一个叶子上的总和。

如果你要欠射，就往上(+1)，如果你要过度射击，就往下(-1)。棘手的部分是确定你是否要欠射/过度射击。您当前的“状态”应该由“我目前所拥有的”+“我将在这个级别停留其余数组的免费内容”计算得出。

你在这个级别上“免费获得”的东西是stepsLeft * previousValue。

以下是一些伪代码。

solve(stepsLeft, prev, acc) {
    if stepsLeft == 0, return empty list  // base case
    ifIStayHere = acc + prev*stepsLeft
    step = ifIstayHere > s ? prev-1 : prev+1
    return [step] concatenated by solve(stepsLeft-1, step, acc+step)
}

请注意，此解决方案不包括初始的0，因此请使用 stepsLeft = n-1 调用它。

正如你所看到的，这是θ(n)的时间复杂度，并且我已经测试了所有情况。（使用Java实现。）

- aioobe

对于N<=10000，因此最多可能有2^n个叶子节点，我认为这相当低效。 - typedef

1

我能看看你的Java代码吗？因为我对它的复杂性有些怀疑。 - typedef

1

如果你即将低估，就加1；如果你即将高估，就减1。这样做听起来不太对。这种方式会选择所有可能序列的任意子集。 - Shoe

1

@Sofffia，给我一个反例。 “超调/欠调”解释是该算法的非正式描述。但我保证它有效。 - aioobe

1

该序列无法由我的程序生成。任务不是识别所有有效的序列，而是生成一个有效的序列。 - aioobe

显示剩余13条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

这里提供了另一种aioobe算法的实现方式，并附带一个正确性的正式证明。

给定一个序列a(k)，定义差分序列d(k) = a(k+1) - a(k)，观察到a(1) + a(2) + ... + a(n) = (n-1)d(1) + (n-2)d(2) + ... + 1d(n-1)。 定理：对于参数n和s，当且仅当(1) n(n-1)/2 mod 2 = s mod 2且(2) |s| ≤ n(n-1)/2时，存在一个长度为n的序列总和为s。 证明：通过对n进行归纳证明。基本情况，n = 1，是显然成立的。对于归纳情况，由于d(k) ∈ {±1}，我们观察到(1)和(2)都是必要条件，因为n-1 + n-2 + ... + 1 = n(n-1)/2且-1 mod 2 = 1 mod 2。反之，假设(1)和(2)均满足。如果s ≥ 0，则构造一个长度为(n-1)的序列，使其总和为s - (n-1)。如果s < 0，则构造一个长度为(n-1)的序列，使其总和为s + (n-1)。这些构造都满足(1)和(2)（省略了一些繁琐的情况分析），因此根据归纳假设，它们将成功。根据s ≥ 0/s < 0将这个序列的元素增加/减少1，并在开头放置0。

由于定理的证明是具有构造性的，我们可以在Python中实现它。

def oneseq(n, s):
    assert isinstance(n, int)
    assert isinstance(s, int)
    nchoose2 = n*(n-1)//2
    abss = abs(s)
    if n < 1 or abss%2 != nchoose2%2 or abss > nchoose2: return None
    a = [0]
    for k in range(n-1, 0, -1):  # n-1, n-2, ..., 1
        d = 1 if s >= 0 else -1
        a.append(a[-1] + d)  # a[-1] equivalent to a[len(a) - 1]
        s -= k*d
    return a