i have sorted array of numbers like
1, 4, 5 , 6, 8
如何确定此数组是否包含等差数列？
例如：
4,6,8
或者
4,5,6
备注：序列中的最小数字为3。
5个回答
2
您可以通过递归解决此问题，将其分解为更小的问题，包括：
现在遍历这些对。
- 识别一对一对的数字{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
编辑：当然，数组必须是排序的！
希望有所帮助。
- smirkingman
1
一般的想法是选择一个元素作为你的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)。
虽然我觉得可能有更有效率的解决方案...
- Kirk Fernandes
1
这并不是解决问题的最佳方式，但您可以尝试以下方法：
遍历数组中所有数字对 - 如果我们假设它们是等差数列的第一和第二个元素，那么每两个数字就完全定义了一个等差数列。因此，知道这两个数字，您可以构造出更多的等差数列元素，并检查它们是否在您的数组中。
如果您只想找到三个形成等差数列的数字，则可以遍历所有非相邻数字a[i]和a[j]的数字对，其中j > i+1，并检查它们的算术平均值是否属于数组 - 您可以使用区间]i,j[上的二分搜索来实现。
- Vladimir
1
首先，我假设您只想要三个或更多项的等差数列。
我建议检查每个数字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。从技术上讲，在您的系列中，它们都是算术序列。您必须更具体地定义您想要的内容。在您的情况下，仅检查并消除完全包含在其他进展中的所有进展可能是微不足道的。- Justin L.
0
这是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]]
- Eric
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
4,6,8还是4,5,6？为什么？ - Matt Ellen