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

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

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

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

Если вы хотите просто найти 3 цифры, формирующие арифметическую прогрессию, то вы можете выполнить итерацию по всем парам несмежных чисел a [i] и [j], j> i + 1 и проверить, принадлежит ли их среднее арифметическое к массиву - вы можете сделать это, используя двоичный поиск по интервалу] i, j [.

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

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

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

как:

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

Answer 5

Общая идея заключается в том, чтобы выбрать элемент в качестве 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 6

Вот код в 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]]