Visual Basic FAQ

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

Входные данные:
N, T,
a1, a2, a3 …. aN

Найти в массиве подряд идущие элементы, которые образуют геометрическую прогрессию с наибольшим знаменателем (по модулю), количество членов которой не меньше T за линейное время.
Если нет ни одной последовательности, длиной T – выдать 0.
Если найдена – выдать:
№ первого элемента последовательности, Знаменатель, Длину последовательности

Const str = "0 4 0 1 16 32 64 12 1 1 1"
Const T = 3
Dim V As Variant, N#
Dim MaxQ#, MaxL#, MaxI#
Dim TempL#, TempI#
Dim prevQ#, nowQ#, i
Private Sub Form_Load()
On Error Resume Next
V = Split(str, " ")
N = UBound(V)
prevQ = -1
For i = 1 To N
    nowQ = V(i) / V(i - 1)

    If prevQ <> Abs(nowQ) Then
        iNtrue
    Else
        If prevQ = Abs(nowQ) Then
            TempL = TempL + 1
        End If
    End If
    If i = N Then iNtrue
    prevQ = Abs(nowQ)
Next
If MaxQ = 0 Then
    Print "0"
Else
    Print "Number of the first element: " & MaxI & vbCrLf & "Denominator: " & MaxQ & vbCrLf & "Sequence length: " & MaxL
End If
End Sub
Sub iNtrue()
    If TempL >= T Then
        If MaxQ < Abs(prevQ) Then
            MaxQ = Abs(prevQ)
            MaxL = TempL
            MaxI = TempI
        End If
        If i = N And MaxQ < Abs(nowQ) Then
            MaxQ = Abs(nowQ)
            MaxL = TempL
            MaxI = TempI
        End If
    End If
    TempI = i
    TempL = 2
End Sub

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