Перебор строк. Пример реализации программы презентация

Строки из трёх символов
Задача: найти все строки, состоящие из латинских букв a, b, c.

Эмпирический алгоритм
Для S1 от a до b
Для S2 от a до b
Для S3 от a до b
Вывести строку: S1S2S3

Рекурсия
Глобальная переменная STR – строка символов
Функция ПЕРЕБОР( Position )
Для S1 от a до b
STR[Position] = S1
ПЕРЕБОР(Position + 1)
Рекурсивный вызов
Рекурсия будет бесконечной!!

Условие выхода из рекурсии
Глобальные переменные:
STR – строка символов
n – количество символов
Функция ПЕРЕБОР( Position )
Если Position > n
Печать строки STR
Возврат
Для S1 от a до b
STR[Position] = S1
ПЕРЕБОР(Position + 1)

Перебор строк, состоящих их цифр
Для большей общности, будем искать строки, состоящие из цифр:
найти все возможные строки длины 3, состоящие из цифр 0, 1, 2.

Пример реализации программы
STR = [0 for i in range(0, 3)]
def perebor(pos):
if pos > 2:
print(*STR)
return
for i in range(0, 3):
STR[pos] = i
perebor(pos + 1)
perebor(0)

Задача для самостоятельного решения
Вывести на печать, в лексикографическом порядке, строки длины m, состоящие из n символов.

Задача для самостоятельного решения
Выведите последовательности в лексикографическом порядке. Каждая последовательность должна выводиться в отдельной строке, числа в последовательности должны быть разделены одиночными пробелами.
Пример входных данных
2 2
Пример выходных данных
1 1
1 2
2 1
2 2
В качестве ответа на задание выберите последовательность для n = 6, m = 5, имеющую номер 6659 в лексикографическом порядке.
Например, последовательность с номером 3 имеет вид “2 1”.

Генерация перестановок
Задача: вывести все последовательности чисел длины n: в которых каждая цифра встречается ровно один раз.
Такие последовательности называются перестановками.
Например, последовательности, состоящие из трех цифр:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Генерация перестановок
Глобальные переменные:
STR – строка символов
n – количество символов
USED – признаки использования символа (в начале вектор заполнен нулями)
Функция ПЕРЕБОР( Position )
Если Position > n
Печать строки STR
Возврат
Для i от 0 до n
ЕСЛИ USED[i] == 1
переход к следующему i
USED[i] = 1
STR[Position] = i
ПЕРЕБОР(Position + 1)
USED[i] = 0

Задача для самостоятельного решения
Выведите перестановки в лексикографическом порядке, каждую перестановку - в отдельной строке. Числа в перестановках должны разделяться одиночными пробелами.
Пример входных данных
3
Пример выходных данных
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
В качестве ответа на задание выберите перестановку для n = 7 с номером 4468 .
Например, перестановка с номером 4 имеет вид “2 3 1”.

Правильные скобочные последовательности
Правильные скобочные последовательности
(1 + 1) + (1 + 1) ? ()()
((1 + 1) + 1) + (1 + 1) ? (())()
((1 + 1) + (1 + 1)) ? (()())
Неправильные скобочные последовательности
)(
(()((
())(()

Правильные скобочные последовательности
На любом отрезке последовательности число открывающихся скобок не меньше числа закрывающихся скобок.
)( - нарушение правила на первом символе.

Правильные скобочные последовательности
Проверка на правильность:
На вход подается строка S
bal = 0
Для всех символов в S
если символ равен (
bal = bal + 1
если символ равен )
bal = bal – 1
Если bal = 0
Последовательность правильная

Правильные скобочные последоватедльности
Генерация скобочной последовательности:
n – количество пар скобок
ind = 0
Если ind = 2*n
если bal = 0
вывести последовательность
возврат