Visual Basic FAQ

Найти геометрическую прогрессию

Входные данные:
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

Запись опубликована on 15.01.2011 at 12:44 и размещена в рубрике: Арифметика. Вы можете читать комментарии, используя RSS-ленту. Вы можете оставить комментарий, или отправить трекбек с Вашего сайта.