如果数组包含算术级数(sequence),如何查找

你可以递归地解决这个问题,把它分解成更小的问题,这些问题是:

• 识别对{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

高温高压

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

a[i] 作为一个算术序列的开始 a[i+n] 作为下一个。

现在您已经在您的系列中有了前两个术语,您可以找到下一个。一般来说,如果x是你的第一个学期,y是你的第二个学期,你的学期将是 x + i*(y-x)

可以继续使用i=3、i=4等,直到到达数组中找不到的值为止。

如果 l 是你的数组的大小,为所有的 i l-2 ,以及所有 n 0 到 l-i-1

4,6,8 6,8 . 从技术上讲,它们都是序列中的算术序列。你必须更明确地定义你想要什么。在您的例子中,检查并消除完全包含在其他进程中的所有进程可能很简单。

一般的想法是选择一个元素作为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

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

虽然我觉得也许有一个更有效的解决方案。。。

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

遍历数组中的所有数字对-如果我们假设每两个数字是一级和二级成员,则它们完全定义了算术序列。因此,知道这两个数字,你就可以构造进一步的级数元素,并检查它们是否在你的数组中。

如果你只想找到构成算术级数的3个数,那么你可以遍历所有非相邻数对a[i]和a[j],j>i+1,并检查它们的算术平均值是否属于数组-你可以在区间]i,j[上使用二进制搜索。

如果它们之间的距离相等,我们发现

比如:

for ($i = 1; $i <= $countArray - 2; $i++) {
     for ($j = $i+1; $j <= $countArray - 1; $j++) {         
    for ($k = $j+1; $k <= $countArray; $k++) {
            if($array[$j]-$array[$i] == $array[$k]-$array[$j]){
             # found 
            }
        }
   }
 }

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]]