查找数组是否包含算术级数（序列）的方法是什么

Question

我已经对数字数组进行了排序，例如

1, 4, 5 , 6, 8

如何找出该数组是否包含算术级数（序列）？

就像这个例子

4,6,8

或

 4,5,6

备注：序列中的最小数字是 3

Answer 1

您可以通过将其分解为更小的问题来递归地解决此问题，这些问题是：

• 识别对 {1,4},{1,5}...{6,8}
• 查找具有相同间隔的序列

对于每对，首先 创建脚手架来运行问题：

Dim number(7) As Integer
Dim result() As Integer
Dim numbers As Integer
Sub FindThem()
number(1) = 1
number(2) = 4
number(3) = 5
number(4) = 6
number(5) = 8
number(6) = 10
number(7) = 15
numbers = UBound(number)
ReDim result(numbers)
Dim i As Integer
For i = 1 To numbers - 2
    FindPairs i
Next
End Sub

现在迭代这些对 边走边

Sub FindPairs(start As Integer)
    Dim delta As Integer
    Dim j As Integer
    result(1) = number(start)
    For j = start + 1 To numbers
        result(2) = number(j)
        delta = result(2) - result(1)
        FindMore j, 2, delta
    Next
End Sub

查找序列

Sub FindMore(start As Integer, count As Integer, delta As Integer)
    Dim k As Integer
    For k = start + 1 To numbers
        step = number(k) - result(count)
        result(count + 1) = number(k) ' should be after the if statement
                                      ' but here makes debugging easier
        If step = delta Then
            PrintSeq "Found ", count + 1
            FindMore k, count + 1, delta
        ElseIf step > delta Then ' Pointless to search further
            Exit Sub
        End If
    Next
End Sub

这只是为了显示结果

Sub PrintSeq(text As String, count As Integer)
    ans = ""
    For t = 1 To count
        ans = ans & "," & result(t)
    Next
    ans = text & " " & Mid(ans, 2)
    Debug.Print ans
End Sub

结果

findthem
Found  1,8,15
Found  4,5,6
Found  4,6,8
Found  4,6,8,10
Found  5,10,15
Found  6,8,10

编辑：哦，当然，数组必须排序！

华泰

Answer 2

首先，我假设您只需要三项或更多项的算术序列。

我建议检查每个数字 a[i] 作为算术序列的开头，并将 a[i+n] 作为下一个数字。

现在您已经有了系列中的前两个术语，您可以找到下一个术语。一般来说，如果 x 是第一项，y 是第二项，则您的项将为 x + i*(yx)，第一项为 i = 0。下一项将为 x + 2*(yx)。在数组中搜索该值。如果该值在您的数组中，则您有一个包含三个或更多项目的算术序列！

您可以继续使用 i=3、i=4 等，直到到达数组中未找到的那个。

如果 l 是数组的大小，请对从 0 到 l-2 的所有 i 以及所有 n 执行此操作code> 从 0 到 li-1

唯一需要注意的是，在示例中，这将找到两个序列 4,6,8以及6,8。从技术上讲，它们都是系列中的算术序列。您必须更具体地定义您想要的内容。就您而言，仅检查并消除完全包含在其他进程中的所有进程可能是微不足道的。

Answer 3

总体思路是选择一个元素作为 a_1，然后选择该元素之后的任何元素作为 a_2，计算差异，然后查看之后是否有任何其他元素与该差异匹配。只要有至少3个元素具有相同的差异，我们就认为它是一个级数。

progression (A, n)
   for i = 1 ... n - 2
      a_1 = A[i]
      for j = i + 1 ... n - 1
         a_2 = A[j]
         d = a_2 - a_1
         S = [ i, j ]
         for k = j + 1 ... n
            if ( d == ( a[k] - a[S.last] ) )
               /* Append the element index to the sequence so far. */
               S += k
         if ( |s| > 2 )
            /* We define a progression to have at least 3 numbers. */
            return true
   return false

您可以修改算法以在丢失之前存储每个集合 S，以计算给定数组 A 的所有级数。假设追加并获取集合 S 的最后一个元素，该算法的运行时间为 O(n^3)恒定时间。

虽然我觉得可能有更有效的解决方案......

Answer 4

当然不是解决问题的最佳方法，但您可以执行以下操作：

迭代数组中的所有数字对 - 如果我们假设它们是第一和第二级数成员，则每两个数字都完全定义算术序列。因此，了解这两个数字，您可以构建进一步的级数元素并检查它们是否在您的数组中。

如果你只想找到 3 个形成算术级数的数字，那么你可以迭代所有非相邻数字对 a[i] 和 a[j]，j > 。 i+1 并检查它们的算术平均值是否属于数组 - 您可以使用区间 ]i,j[ 上的二分搜索来做到这一点。

Answer 5

这是 Swift 4 中的代码：

extension Array where Element == Int {

    var isArithmeticSequence: Bool {
        let difference = self[1] - self[0]
        for (index, _) in self.enumerated() {
            if index < self.count-1 {
                if self[index + 1] - self[index] != difference {
                    return false
                }
            }
        }
        return true
    }

    var arithmeticSlices: [[Int]] {

        var arithmeticSlices = [[Int]]()
        var sliceSize = 3
        while sliceSize < self.count+1 {

            for (index, _) in self.enumerated() {

                if (index + sliceSize-1) <= self.count - 1 {

                    let currentSlice = Array(self[index...index + sliceSize-1])
                    if currentSlice.isArithmeticSequence {
                        arithmeticSlices.append(currentSlice)
                    }
                }
            }
            sliceSize+=1
        }
        return arithmeticSlices
    }
}


let A = [23, 24, 98, 1, 2, 5]
print(A.arithmeticSlices) // []

let B = [4, 7, 10, 4,5]
print(B.arithmeticSlices) //[[1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4], [2, 3, 4, 5], [1, 2, 3, 4, 5]]

let C = [4, 7, 10, 23, 11, 12, 13]
print(C.arithmeticSlices) // [[4, 7, 10], [11, 12, 13]]