algorithm - 如何进行 d-平滑序列算法

Question

我真的很努力地设计一种算法来找到 d，它是可以添加或减去(最多)以使给定序列严格递增的最低值。

例如..说seq[] = [2,4,8,3,1,12]

给定该序列，算法应将“5”作为 d 返回，因为您最多可以为每个元素加上或减去 5，以便函数严格递增。

我尝试了几种方法，但似乎无法掌握可靠的技术。

我试过循环遍历 seq.并检查 seq[i] < seq[i+1]。如果不是，它检查是否 d>0.. 如果是，尝试从 seq[i+1] 中添加/减去它。否则，它通过取 seq[i-1] - seq[i] 的差来计算 d。

虽然我无法让它稳定下来，但它就像我一直在添加 if 语句，这些语句对于独特的输入序列来说更“特殊”。人们建议使用二进制搜索方法，但我无法将其应用于此问题。

非常感谢任何提示和建议。谢谢!

---

这是我正在编写的代码 - 使用 Python - v4

def ComputeMaxDelta3(seq):
    # Create a copy to speed up comparison on modified values
    aItems = seq[1:] #copies sequence elements from 1 (ignores seq[0])
    # Will store the fix values for every item
    # this should allocate 'length' times the 0 value
    fixes = [0] * len(aItems)
    print("fixes>>",fixes)

    # Loop until no more fixes get applied
    bNeedFix = True
    while(bNeedFix):
        # Hope will have no fix this turn
        bNeedFix = False

        # loop all subsequent item pairs (i should run from 0 to length - 2)
        for i in range(0,len(aItems)-1):
            # Left item
            item1 = aItems[i]
            # right item
            item2 = aItems[i+1]

            # Compute delta between left and right item
            # We remember that (right >= left + 1
            nDelta = item2 - (item1 + 1)
            if(nDelta < 0):
                # Fix the right item
                fixes[i+1] -= nDelta
                aItems[i+1] -= nDelta
                # Need another loop
                bNeedFix = True

    # Compute the fix size (rounded up)
    # max(s) should be int and the division should produce an int
    nFix = int((max(fixes)+1)/2)
    print("current nFix:",nFix)
    

    # Balance all fixes
    for i in range(len(aItems)):
        fixes[i] -= nFix

    print("final Fixes:",fixes)
    print("d:",nFix)
    print("original sequence:",seq[1:])
    print("result sequence:",aItems)

    return

---

这是显示的内容:

Working with: [6, 2, 4, 8, 3, 1, 12] 
    [0]= 6 So the following numbers are the sequence: 
         aItems = [2, 4, 8, 3, 1, 12] 

fixes>> [0, 0, 0, 0, 0, 0]
current nFix: 6
final Fixes: [-6, -6, -6, 0, 3, -6]
d: 1
original sequence: [2, 4, 8, 3, 1, 12]
result sequence: [2, 4, 8, 9, 10, 12]

d SHOULD be: 5

done!

~注意~

由于第一个元素是键，我从 1 而不是 0 开始

Answer 1

如预期的那样，这是(或应该是)我最初解决方案的 Python 版本:

def ComputeMaxDelta(aItems):
    # Create a copy to speed up comparison on modified values
    aItems = aItems[:]
    # Will store the fix values for every item
    # this should allocate 'length' times the 0 value
    fixes = [0] * len(aItems)

    # Loop until no more fixes get applied
    bNeedFix = True
    while(bNeedFix):
        # Hope will have no fix this turn
        bNeedFix = False

        # loop all subsequent item pairs (i should run from 0 to length - 2)
        for i in range(0,len(aItems)-1):
            # Left item
            item1 = aItems[i]
            # right item
            item2 = aItems[i+1]

            # Compute delta between left and right item
            # We remember that (right >= left + 1
            nDelta = item2 - (item1 + 1)
            if(nDelta < 0):
                # Fix the right item
                fixes[i+1] -= nDelta
                aItems[i+1] -= nDelta
                # Need another loop
                bNeedFix = True

    # Compute the fix size (rounded up)
    # max(s) should be int and the division should produce an int
    nFix = (max(fixes)+1)/2 # corrected from **(max(s)+1)/2**

    # Balance all fixes
    for i in range(len(s)):
        fixes[i] -= nFix

    print("d:",nFix) # corrected from **print("d:",nDelta)**
    print("s:",fixes)

    return

我使用了您的 Python 并进行了修复，以便完全按照我的 C# 解决方案运行。我不懂 Python，但在网上寻找一些引用资料，我应该找到你移植失败的地方。

如果将你的 python 版本与我的进行比较，你应该会发现以下差异:

1. 您将引用 aItems 保存到 s 并将其用作我的修复，但修复 是为了从全 0 开始。
2. 您没有在自身上克隆 aItems，然后对其项目的所有更改都反射(reflect)在方法之外。
3. 您的 for 循环从索引 1 开始，而我的循环从 0(第一个元素)开始。
4. 检查完 nDelta 后，您从 s 和 aItems 中减去了 nDelta，但正如我在第 1 点和第 2 点他们指向相同的项目。
5. 不需要 ceil 指令，因为两个整数之间的除法产生一个整数，就像 C# 一样。

请记住，我仅根据在线文档知识修复了 Python 代码，因为我不使用该语言编写代码，所以我不能 100% 确定某些语法(我的主要疑问是关于 修复声明)。

问候，
丹妮尔。