15
Январь
2011
Найти геометрическую прогрессию
Найти геометрическую прогрессию
Входные данные:
N, T,
a1, a2, a3 …. aN
Найти в массиве подряд идущие элементы, которые образуют геометрическую прогрессию с наибольшим знаменателем (по модулю), количество членов которой не меньше T за линейное время.
Если нет ни одной последовательности, длиной T – выдать 0.
Если найдена – выдать:
№ первого элемента последовательности, Знаменатель, Длину последовательности
Option Explicit Public Qmax As Single, StartSequence As Integer, LengthSequence As Integer Dim N As Integer, T As Integer, A() As Single Private Sub LoadData() Dim i As Integer, S As String, Inp As String Open "E:\VBProjects\Pirit\Progress.Geo\PgressGe.txt" For Input As #1 Input #1, N, T ReDim A(N - 1) For i = 0 To N - 1 Input #1, A(i) S = S & Str$(A(i)) Next i Close #1 End Sub Private Sub FindSequence() Dim i As Integer, l As Integer, Q As Single, Resu As Boolean For i = 0 To N - T Q = A(i + 1) / A(i) If Abs(Q) > Abs(Qmax) Then l = 2 'Длинна минус 1 Do While A(i + l) = A(i + l - 1) * Q l = l + 1 If i + l = N Then Exit Do Loop If l >= T Then Qmax = Q: StartSequence = i: LengthSequence = l i = i + l - 2 End If Next i End Sub Public Sub Main() LoadData FindSequence Open "E:\VBProjects\Pirit\Progress.Geo\RessGe.txt" For Output As #1 Print #1, Str$(StartSequence); Str$(Qmax); Str$(LengthSequence) Close #1 End Sub
16 4
12 1 5 15 45 135 256 2 4 8 16 1011 45 12 3 69