Палиндромы и VB

[Экселенц]

Здравствуйте форумчане!

Если кто-то из вас по доброй воле может мне помочь, то мой вопрос о алгоритме на VB:
есть палиндром(строка, к-я читается одинаково справа и слева, например АВВА) изл латинских букв А и В. Число N - это кол-во букв в палиндроме, 1=< N =<100. Есть запрещенная строка (S) , длинной не более 5 символов, например "ВАВ". Надо подсчитать, сколько есть палиндомов, длинной N не содержащих запрещенную строку S.
Мой первый алгоритм перебирал все допустимые комбинации А и В и выбирал из них допустимые палиндромы. Но это очень долго и комп повесился - возьмите двоичное число из ста единичек, перевидите его в двоичное, и получите биллиарды комбинаций, которые можно перебирать часами.
Сдесь я представлю модифицированный алгоритм, который делает работу в 2 раза быстрее, но и этого недостаточно - комп тормозит уже при 30 символов в строке. Алгоритм перебирает комбинации А и В в подстроке HalfStr, длинна к-й в 2 раза меньше N, потом к строке Stroka добавляется HalfStr и StrReverce(HalfStr) - перевернутый HalfStr. Таким образом генерируются заведомо палиндромные строки.

Stroka =HalfStr & StrReverce(HalfStr).

Если N - нечетное, то между HalfStr и StrReverce(HalfStr) ставится сначало А потом В.

Stroka =HalfStr & "A" & StrReverce(HalfStr)
Stroka =HalfStr & "B" & StrReverce(HalfStr)

Уже потом, если Stroka не содержит S то счетчик повышается на 1.
Но и этот алгоритм тормозит. Если у кого-нибудь есть идеи на счет того, как этот алгоритм выполнить быстрее, и если Вы захотите поделится своими идеями, то я буду очень благодарен )

[alibek]

Что-то не очень понял.
Текст палиндрома может быть произвольным или осмысленным?
Если произвольным и нужно знать только количество вариантов (а не сами варианты), то я бы делал наоборот -- посчитал бы количество всех вариантов и отнял бы количество вариантов с запрещенной строкой.

[GAGArin]

Кажется число палиндромов из n буков это
2^int(n/2)*(1+(n/2-int(n/2))*2)
--
Add:
Проще так 2^int(n/2)*(1 + n mod 2)
--
Но надо проверить...

возьмите двоичное число из ста единичек, перевидите его в двоичное

Эээ...

ЗЫ Кстати 2*30 это всего 10^9 а 2^16 и того меньше... Комп не должен вешаться даже на рассчете всех палиндромов и их запоминании. Точнее должен, но не так уж сильно )) По крайне мере, 30-40 символов ИМХО должен спокойно просчитывать меньше чем за минуту (хотя я не проверял конечно)

[GAGArin]

Поторопился я однако, думал запрещенная строка может только в центре быть. (ты просто в качестве примера привел тоже палиндром) Выводить формулу для "запрещенных" не буду, скажу только что она зависит от того палиндром S или нет. А думать что-то лениво...

[GSerg]

Хм...

У меня получилось тождественная, но другая формула - 2 ^ (Int(N / 2) + (N Mod 2))

Что же касается этого перебора, то... то сегодня я пойду спать

[vvs_adm]

Кажется число палиндромов из n буков это
2^int(n/2)*(1+(n/2-int(n/2))*2)
--
Add:
Проще так 2^int(n/2)*(1 + n mod 2)
--
Но надо проверить...

а по моему число палиндромов из n символов равно:
2 ^ ((n+1)\2)

[GAGArin]

vvs_adm
Ню, ню ) Каждому свое конечно А вообще просто я не помнил как округляет "\" а смотреть лениво было.

[Экселенц]

Что-то не очень понял.
Текст палиндрома может быть произвольным или осмысленным?
Если произвольным и нужно знать только количество вариантов (а не сами варианты), то я бы делал наоборот -- посчитал бы количество всех вариантов и отнял бы количество вариантов с запрещенной строкой.

Палиндром неосмысленный, просто набор из N символов, а сделать так, как вы хотите я думал, но проблема в расчете количества вариантов С запрещенной строкой. (общее количествово - то палиндромов можно подсчитать)

[alibek]

но проблема в расчете количества вариантов С запрещенной строкой. (общее количествово - то палиндромов можно подсчитать)

И в чем же эта проблема?
Допустим, S=3 (три символа в запрещенной строке), а N=7 (семь символов в палиндроме). Если "палиндромные" символы отмечать, как +, а запрещенные, как *, то получаться следующие варианты:
***++++
+***+++
++***++
+++***+
++++***
Т.е. число вариантов равно числу вариантов, умноженному на (N-S-1).

[GAGArin]

Одну формулу тут не вывести, но все же писать полный перебор тоже не стоит.

Строим массив строк с запрещенной строкой (как сказал alibek) Проверяем его на дополнимость до палиндромов и по возможности или дополняем или выкидываем строку.
"++АА.Б+++" - выбрасываем т.к. он недополним
"+++А.АБ++" - дополняем до "++БА.АБ++"
Пробегаемся по массиву и ищем одинаковые варианты, если находим, оставляем один из двух (больше двух одинаковых вроде получиться не должно)

Теперь просто пускаем нашу формулу от числа плюсиков в каждой строке и складываем. Получаем все запрещенные палиндромы.

ЗЫ Кстати формулу числа палиндромов надо дополнить вариантом
F(0)=0

[Экселенц]

но проблема в расчете количества вариантов С запрещенной строкой. (общее количествово - то палиндромов можно подсчитать)

И в чем же эта проблема?
Допустим, S=3 (три символа в запрещенной строке), а N=7 (семь символов в палиндроме). Если "палиндромные" символы отмечать, как +, а запрещенные, как *, то получаться следующие варианты:
***++++
+***+++
++***++
+++***+
++++***
Т.е. число вариантов равно числу вариантов, умноженному на (N-S-1).

Но может быть и
***+***
+***+++
++***++
+++***+
***+***

а если N=10, то
***++++***
***+***+++
*** ***+***
+++***+***
***+*** +++
т.е. запрещенная сторка будет встечатся более 1 раза, => запрещенных палиндромов будет гораздо больше.

Простите, в предыдущем посте я не уточнил, что это неосмысленный набор из N символов "A" и "B", латинских.

[alibek]

Но может быть и

В этом нет смысла.
Если будут исключены ***++++, то в это множество будет также входить и ***+***.

[GAGArin]

Экселенц
Тогда только полный перебор. Сейчас посижу, посмотрю что там можно сделать для оптимизации...

alibek
Если найдешь другое решение, потесть его и поймешь что оно не подходит. Для начала скажи сколько запрещенных палиндромов для N=7 и S="ABB" Просто по формулам.

[Экселенц]

Эээ...

ЗЫ Кстати 2*30 это всего 10^9 а 2^16 и того меньше... Комп не должен вешаться даже на рассчете всех палиндромов и их запоминании. Точнее должен, но не так уж сильно )) По крайне мере, 30-40 символов ИМХО должен спокойно просчитывать меньше чем за минуту (хотя я не проверял конечно)

1111111111111111111111111111111111111111111111111111111111111111
(66 единичек)в двоичной равно
18446744073709551615
в десятичной.

[GSerg]

Максимум 100.
Поскольку это палиндром, он определяется своей первой половиной, то есть реальный максимум - 50.

[GAGArin]

Вобщем где-то 50 символов перебирает за 30-40 секунд, больше еще не ставил. Просто полный перебор с отсечениями причем не в лучшем исполнении (т.к. в моем, а я в VB не силен)

Можно чисто теоретически сделать это передавая не строку, а байт, но мне не хотелось колупаться.

Код: Выделить всё

Public intN As Integer
Public intK As Integer
Public IntHalf As Integer
Public strS As String
Public lngCount As Long
Public boolChet As Boolean

Private Function strZerro(intCount As Integer) As String
For intT = 1 To intCount
  strZerro = strZerro + "*"
Next intT
End Function

Private Function strMirror(strWord As String) As String
strLeft = strWord + strZerro(IntHalf - Len(strWord))
strMirror = strLeft
If boolChet Then
  For intT = 1 To IntHalf
    strMirror = strMirror + Mid(strLeft, IntHalf - intT + 1, 1)
  Next intT
Else
  For intT = 1 To IntHalf - 1
    strMirror = strMirror + Mid(strLeft, IntHalf - intT, 1)
  Next intT
End If
End Function

Private Function boolPoisk(strWord As String) As Boolean
strnow = strMirror(strWord)
For intT = 1 To intN - intK + 1
  If Mid(strnow, intT, intK) = strS Then
    boolPoisk = True
    Exit Function
  End If
Next intT
End Function

Private Sub Pali(strWord As String)
If Not boolPoisk(strWord) Then
  If Len(strWord) = IntHalf Then
    lngCount = lngCount + 1
  Else
    Pali (strWord + "A")
    Pali (strWord + "B")
  End If 
End If
End Sub


Private Sub Command1_Click()
strS = "ABB"
intN = 50
IntHalf = (intN + 1) \ 2
intK = Len(strS)
If intN / 2 = intN \ 2 Then boolChet = True

Pali ("")
MsgBox (lngCount)
End Sub


PS А так хотелось решить задачу математически

Ах да, комментов не будет (по крайней мере сегодня) strS - запретная строка, intN - нужная длинна. Остальное потом.

[GAGArin]

За 2 часа, сотню прога не вытянула, ушла в астрал. Но сотню я и не обещал )