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

1. Перебор строк

2. Строки из трёх символов

Задача: найти все строки, состоящие из латинских букв a, b, c.
aaa
aab
aac
baa
bab
bac
caa
cab
cac
aba
abb
abc
bba
bbb
bbc
cba
cbb
cbc
aca
acb
acc
bca
bcb
bcc
cca
ccb
ccc

3. Эмпирический алгоритм

Для S1 от a до b
Для S2 от a до b
Для S3 от a до b
Вывести строку: S1S2S3

4. Рекурсия

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

5. Условие выхода из рекурсии

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

6. Перебор строк, состоящих их цифр

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

7. Пример реализации программы

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)

8. Задача для самостоятельного решения

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

9. Задача для самостоятельного решения

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

10. Генерация перестановок

• Задача: вывести все последовательности чисел длины n: в которых
каждая цифра встречается ровно один раз.
• Такие последовательности называются перестановками.
• Например, последовательности, состоящие из трех цифр:
• 123
• 132
• 213
• 231
• 312
• 321

11. Генерация перестановок

Глобальные переменные:
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

12. Задача для самостоятельного решения

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

13. Правильные скобочные последовательности

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

14. Правильные скобочные последовательности

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

15. Правильные скобочные последовательности

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

16. Правильные скобочные последоватедльности

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

17. Домашняя работа

Расстановка фишек. Имеется полоса размера n1×n, разбитая на единичные клетки. Нужно расставить в
клетках полосы m фишек, чтобы никакие две фишки не стояли в соседних клетках. Выведите все
возможные расстановки.
Входные данные
Натуральные числа n и m.
Выходные данные
Выведите все корректные расстановки фишек. Каждая расстановка должна быть выведена в отдельной
строке. Клетки, занятые фишками, обозначаются символами ‘*’, свободные клетки - точками ‘.’. Выводите
расстановки в лексикографическом порядке, считая, что ‘*’ < ‘.’.