как найти, если массив содержит арифметическую прогрессию (последовательность)

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_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. Алгоритм работает в O (n ^ 3), предполагая, что добавление и получение последнего элемента множества S. происходит в постоянное время.

Хотя я чувствую, что может быть более эффективное решение...

Answer 3

Во-первых, я предполагаю, что вам нужны только арифметические последовательности из трех или более слагаемых.

Я бы предложил проверять каждое число a[i] как начало арифметической последовательности, а a[i+n] как следующее.

Теперь, когда у вас есть первые два термина в вашей серии, вы можете найти следующий. В общем, если x - это ваш первый член, а y - ваш второй, ваши термины будут x + i*(y-x), а первый член будет i = 0. Следующий член будет x + 2 * (y-x). Найдите в вашем массиве это значение. Если это значение находится в вашем массиве, у вас есть арифметическая последовательность из трех или более элементов!

Вы можете продолжить с i = 3, i = 4 и т. Д., Пока не достигнете того, который не найден в вашем массиве.

Если l - размер вашего массива, сделайте это для всех i от 0 до l-2 и всех n от 0 до l-i-1

Единственное важное предостережение заключается в том, что в этом примере будут найдены обе последовательности 4,6,8, а также 6,8. Технически, оба они являются арифметическими последовательностями в вашей серии. Вам нужно будет более конкретно определить, что вы хотите там. В вашем случае, может быть тривиально просто проверить и устранить все прогрессии, которые полностью содержатся внутри других.

Answer 4

Конечно, не оптимальный способ решить вашу проблему, но вы можете сделать следующее:

Итерация по всем парам чисел в вашем массиве - каждые 2 числа полностью определяют арифметическую последовательность, если мы предположим, что они 1-й и 2-й члены прогрессии. Поэтому, зная эти 2 числа, вы можете создать дополнительные элементы прогрессии и проверить, есть ли они в вашем массиве.

Если вы хотите просто найти 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]]

Answer 6

Что я пытаюсь сделать, это найти все комбинации из 3 чисел, которые находятся в этом массиве.

и найти расстояние между ними, если оно равно, мы нашли

, как:

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