Рекурсивный перебор. Алгоритмизация и программирование, язык Python

Рекурсивный перебор
перебор L символов
w[0]="Ы"
# перебор последних L-1 символов
w[0]="Ш"
# перебор последних L-1 символов
w[0]="Ч"
# перебор последних L-1 символов
w[0]="О"
# перебор последних L-1 символов

Рекурсивный перебор
# основная программа
TumbaWords ( "ЫШЧО", "", 3 );
def TumbaWords ( A, w, L ):
if len(w) == L:
print ( w )
return
for c in A:
TumbaWords ( A, w + c, L )
нужная длина слова
слово полной длины
по всем символам алфавита
алфавит
слово

Задачи
«A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов.
«B»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов.
Программа не должна строить другие слова, не соответствующие условию.

Сравнение строк
Сравнение по кодам символов:

Сравнение строк
5STEAM < STEAM < Steam < steam
steam < ПАР < Пар < пАр < пар < парк

Сортировка строк
aS = [] # пустой список строк
print ( "Введите строки для сортировки:" )
while True:
s1 = input()
if s1 == "": break
aS.append ( s1 ) # добавить в список
aS.sort() # сортировка
print ( aS )

Задачи
«A»: Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем – слово. Вывести слова в алфавитном порядке.
Пример:
Введите 5 строк:
1. тепловоз
2. арбуз
3. бурундук
4. кефир
5. урядник
Список слов в алфавитном порядке:
арбуз, бурундук, кефир, тепловоз, урядник

Задачи
«B»: Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке.
Пример:
Введите слова:
1. тепловоз
2. арбуз
Список слов в алфавитном порядке:
арбуз, тепловоз

Программирование на языке Python
§ 67. Матрицы

Что такое матрица?
Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца.
нет знака
нолик
крестик
строка 1, столбец 2

Создание матриц
A = [[-1, 0, 1],
[-1, 0, 1],
[0, 1, -1]]
перенос на другую строку внутри скобок
A = [[-1, 0, 1], [-1, 0, 1], [0, 1, -1]]
или так:

Создание матриц
N = 3
M = 2
row = [0]*M
A = [row]*N
Нулевая матрица:
row
A
A[0][0] = 1
а правильно так:
A = []
for i in range(N):
A.append ( [0]*M )
A
A[0][0] = 1

Вывод матриц
print ( A )
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
def printMatrix ( A ):
for row in A:
for x in row:
print ( "{:4d}".format(x), end = "" )
print ()
1 2 3
4 5 6
7 8 9

Простые алгоритмы
Заполнение случайными числами:
import random
for i in range(N):
for j in range(M): A[i][j] = random.randint ( 20, 80 )
print ( "{:4d}".format(A[i][j]),
end = "" )
print()
Суммирование:
s = 0
for i in range(N):
for j in range(M):
s += A[i][j]
print ( s )
s = 0
for row in A:
s += sum(row)
print ( s )

Задачи
«A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный и минимальный элементы в матрице и их индексы.
Пример:
Матрица А:
12 14 67 45
32 87 45 63
69 45 14 11
40 12 35 15
Максимальный элемент A[2,2]=87
Минимальный элемент A[3,4]=11

Задачи
«B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:
вычислить среднюю яркость пикселей по всему рисунку
все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные – белыми (код 255)
Пример:
Матрица А:
12 14 67 45
32 87 45 63
69 45 14 11
40 12 35 15
Средняя яркость 37.88
Результат:
0 0 255 255
0 255 255 255
255 255 0 0
255 0 0 0

Перебор элементов матрицы
Главная диагональ:
for i in range(N):
# работаем с A[i][i]
Побочная диагональ:
for i in range(N):
# работаем с A[i][N-1-i]
Главная диагональ и под ней:
for i in range(N):
for j in range( i+1 ):
# работаем с A[i][j]

Перестановка строк и столбцов
2-я и 4-я строки:
A[2], A[4] = A[4], A[2]
2-й и 4-й столбцы:
for i in range(N):
A[i][2], A[i][4] = A[i][4], A[i][2]

Выделение строк и столбцов
1-я строка:
R = A[1][:]
2-й столбец:
C = []
for row in A:
C.append(row[2])
R = A[1]
или так:
C = [ row[2] for row in A ]
главная диагональ:
D = [ A[i][i] for i in range(N) ]

Задачи
«A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает нули во все элементы выше главной диагонали. Алгоритм не должен изменяться при изменении размеров матрицы.
Пример:
Матрица А:
12 14 67 45
32 87 45 63
69 45 14 30
40 12 35 65
Результат:
12 0 0 0
32 87 0 0
69 45 14 0
40 12 35 65

Задачи
«B»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните отражение рисунка сверху вниз:
«С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

Программирование на языке Python
§ 68. Работа с файлами

Как работать с файлами?
файлы
текстовые
двоичные
«plain text»:
текст, разбитый на строки;
из специальных символов только символы перехода на новую строку
любые символы
рисунки, звуки, видео, …

Принцип сэндвича
хлеб
хлеб
начинка
Fin = open ( "input.txt" )
Fout = open ( "output.txt", "w" )
# здесь работаем с файлами
Fin.close()
Fout.close()
файловые переменные-указатели
"r" - чтение
"w" – запись
"a" – добавление
по умолчанию – на чтение (режим "r")

Ввод данных
Fin = open( "input.txt" )
s = Fin.readline() # "1 2"
Чтение строки:
Чтение строки и разбивка по пробелам:
s = Fin.readline().split() # ["1","2"]
Чтение целых чисел:
s = Fin.readline().split() # ["1","2"]
a, b = int(s[0]), int(s[1])
или так:
a, b = [int(x) for x in s]
или так:
a, b = map( int, s )

Вывод данных в файл
a = 1
b = 2
Fout = open( "output.txt", "w" )
Fout.write ( "{:d} + {:d} = {:d}\n".format(
a, b, a+b) )
Fout.close()

Чтение неизвестного количества данных
пока не конец файла
прочитать число из файла
добавить его к сумме
Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
Fin = open ( "input.txt" )
sum = 0
while True:
s = Fin.readline()
if not s: break
sum += int(s)
Fin.close()
если конец файла, вернёт пустую строку

Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
sum = 0
Fin = open ( "input.txt" )
lst = Fin.readlines()
for s in lst:
sum += int(s)
Fin.close()
прочитать все строки в список строк

Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
sum = 0
with open ( "input.txt" ) as Fin:
for s in Fin:
sum += int(s)
или так:
sum = 0
for s in open ( "input.txt" ):
sum += int(s)

Задачи
«A»: Напишите программу, которая находит среднее арифметическое всех чисел, записанных в файле в столбик, и выводит результат в другой файл.
«B»: Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть.
«C»: В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.

Обработка массивов
Задача. В файле записаны в столбик целые числа. Вывести в другой текстовый файл те же числа, отсортированные в порядке возрастания.

Обработка массивов
Ввод массива:
A = []
while True:
s = Fin.readline()
if not s: break
A.append ( int(s) )
Ввод в стиле Python:
s = Fin.read().split()
A = list ( map(int, s) )
Сортировка:
A.sort()

Обработка массивов
Вывод результата:
Fout = open ( "output.txt", "w" )
Fout.write ( str(A) )
Fout.close()
или так:
for x in A:
Fout.write ( str(x)+"\n" )
[1, 2, 3]
1
2
3
или так:
for x in A:
Fout.write ( "{:4d}".format(x) )
1 2 3

Задачи
«A»: В файле в столбик записаны числа. Отсортировать их по возрастанию последней цифры и записать в другой файл.
«B»: В файле в столбик записаны числа. Отсортировать их по возрастанию суммы цифр и записать в другой файл. Используйте функцию, которая вычисляет сумму цифр числа.
«C»: В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.

Обработка строк
Задача. В файле записано данные о собаках: в каждой строчке кличка собаки, ее возраст и порода:
Мухтар 4 немецкая овчарка
Вывести в другой файл сведения о собаках, которым меньше 5 лет.
пока не конец файла Fin
прочитать строку из файла Fin
разобрать строку – выделить возраст
если возраст < 5 то
записать строку в файл Fout

Чтение данных из файла
Чтение одной строки:
s = Fin.readline()
Разбивка по пробелам:
data = s.split()
Выделение возраста:
sAge = data[1]
age = int ( sAge )
Кратко всё вместе:
s = Fin.readline()
age = int ( s.split()[1] )

Обработка строк
Fin = open ( "input.txt" )
Fout = open ( "output.txt", "w" )
while True:
s = Fin.readline()
if not s: break
age = int ( s.split()[1] )
if age < 5:
Fout.write ( s )
Fin.close()
Fout.close()
Полная программа:

Обработка строк
lst = Fin.readlines()
for s in lst:
age = int ( s.split()[1] )
if age < 5:
Fout.write ( s )
или так:
for s in open ( "input.txt" ):
age = int ( s.split()[1] )
if age < 5:
Fout.write ( s )
или так: