IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Помогите студентке с нахождением сложности алгорит
сообщение
Сообщение #1


Гость






1. Генерирование всех последовательностейв антилексикографичеком порядке.Данные: n
Результат: Пеоследовательность перестановок множества {1,…,n} в антилексикографическом порядке.
(я очент извиняюсь, но сама прога написана на VB, но смысл тот же :smile.gif)
Цитата
Private Sub REVERSE(m As Integer)
Dim i, j, tmp As Integer
    i = 1
    j = m
    While i < j
        tmp = P(i)
        P(i) = P(j)
        P(j) = tmp
        i = i + 1
        j = j - 1
    Wend
End Sub
----------------------------------------------------
Private Sub ANTYLEX(m As Integer)
Dim i, tmp, k As Integer
Dim A As String

    If m = 1 Then
            A = ""
            For k = 1 To n
                A = A + Str(P(k))
            Next k
            lstAntylex.AddItem A
     Else
            For i = 1 To m
                  ANTYLEX (m - 1)
            If i < m Then
                            tmp = P(i)
                P(i) = P(m)
                      P(m) = tmp
               REVERSE (m - 1)
                  End If
Next i
     End If
End Sub
----------------------------------------------------
Private Sub cmdBegin_Click()  ' вводится число n заполняется массив начальными значениями,
    lstAntylex.Clear              '  последовательность будет выводится в ListBox - lstAntylex     
    n = txtN.Text
    ReDim P(n)
   
    For i = 1 To n
        tmp = P(i)
        P(i) = i
        i = tmp
    Next
ANTYLEX (n)
End Sub


2.Генерирование всех перестановок за минимальное число транспозиций.
Цитата
Function B(m As Integer, j As Integer) As Integer
Dim tmp As Integer
   
    If (m Mod 2 = 0) And (m > 2) Then
        If j < m - 1 Then B = j Else B = m - 2
    Else
        B = m - 1
    End If
End Function
------------------------------------------------------------
Private Sub PERM(m As Integer)
Dim tmp, k, i As Integer
Dim A As String

    If m = 1 Then
            A = ""
            For k = 1 To n
                A = A + Str(P(k))
            Next k
            lstAntylex.AddItem A
    Else
        For i = 1 To m
            PERM (m - 1)
            If i < m Then
                tmp = P(B(m, i))
                P(B(m, i)) = P(m)
                P(m) = tmp
            End If
        Next i
     End If
       End Sub
------------------------------------------------------------
Private Sub cmdBegin_Click()
    lstAntylex.Clear
    n = txtN.Text
    ReDim P(n)
   
    For i = 1 To n
        tmp = P(i)
        P(i) = i
        i = tmp
    Next
    PERM (n)
End Sub


3.Генерирование всех перестановок с минимальным числом транспозиций соседних элементов.

Цитата
Private Sub cmdBegin_Click()
Dim i, k, tmp, j As Integer

    lstAntylex.Clear
    n = txtN.Text
    ReDim P(n), C(n), PR(n)

    For i = 1 To n
        P(i) = i
       C(i) = 1
       PR(i) = True
    Next i
    C(n) = 0
    A = ""
    For j = 1 To n
        A = A + Str(P(j))
    Next j
   lstAntylex.AddItem A
    i = 1
    While i < n
     m = m + 1
        i = 1
        x = 0
        While C(i) = n - i + 1
            If PR(i) = True Then PR(i) = False Else PR(i) = True
            C(i) = 1
            If PR(i) Then x = x + 1
            i = i + 1
        Wend

        If i < n Then
            If PR(i) Then k = C(i) + x Else k = n - i + 1 - C(i) + x
            tmp = P(k)
            P(k) = P(k + 1)
            P(k + 1) = tmp
                A = ""
                For j = 1 To n
                    A = A + Str(P(j))
                Next j
               lstAntylex.AddItem A
            C(i) = C(i) + 1
        End If
    Wend
End Sub
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


Специально для Lenochka. Детально и без размахивания регистрами ответить на ентот вопрос не смогу т. к. в универе не учился. Здесь нужно копать в том направлении, что сложность алгоритма ависит от скорости его выполнения, следовательно, чем больше в нём рекурсий (типа чем больше он тормозит) тем он сложнее. А чем он оптимизированнее тем менее сложен. Зайди на mail.ru и загони в поисковик фразу "нахождение сложности алгоритма"
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:30
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name