ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.12.2023
Просмотров: 407
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
§ 63. Алгоритмы обработки массивов
§ 63. Алгоритмы обработки массивов
Срезы в Python – отрицательные индексы
Особенности работы со списками
Метод пузырька (сортировка обменами)
Быстрая сортировка (QuickSort)
Сортировка в Python – на месте
Преобразования «строка» – «число»
s все вхождения слова-образца wOld на слово-замену wNew.
пока слово wOld есть в строке s
удалить слово wOld из строки
вставить на это место слово wNew
Что плохо?
?
wOld: "12"
wNew: "A12B"
зацикливание
s
res
б)
wNew
s
res
в)
s
res
г)
wOld
res
s
а)
wNew
s = "12.12.12"
s = replaceAll ( s, "12", "A12B" )
print( s )
def replaceAll ( s, wOld, wNew ):
lenOld = len(wOld)
res = ""
while len(s) > 0:
p = s.find ( wOld )
if p < 0:
res = res + s
return
if p > 0: res = res + s[:p]
res = res + wNew
if p+lenOld >= len(s):
s = ""
else:
s = s[p+lenOld:]
return res
добавить слово-замену
строка кончилась
взять «хвост»
взять начало перед образцом
искать образец
если не нашли
s = "12.12.12"
s = s.replace( "12", "A12B" )
print ( s )
Встроенная функция:
«A»: Напишите функцию, которая отсекает всю часть строки после первого слова.
Пример:
Введите строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды
«B»: Напишите функцию, которая заменяет расширение файла на заданное новое расширение.
Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.exe
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.work.xml
Введите новое расширение: tmp
Результат: qq.work.tmp
«C»: Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов.
Результат:
В 2013 году в школе 123 состоялся очередной выпуск 11 классов.
Задача. В алфавите языка племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все слова, состоящие из L букв, которые можно построить из букв этого алфавита.
перебор L-1 символов
задача для слов длины К сведена к задаче для слов длины L-1!
перебор 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 букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.
«C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.
пар
парк
Пар
?
?
Сравнение по кодам символов:
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
1
а правильно так:
A = []
for i in range(N):
A.append ( [0]*M )
A
A[0][0] = 1
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 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:
«С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:
Главная диагональ:
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[i]
или так:
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 столбцов. Выполните отражение рисунка сверху вниз:
пока слово wOld есть в строке s
удалить слово wOld из строки
вставить на это место слово wNew
Что плохо?
?
wOld: "12"
wNew: "A12B"
зацикливание
s
res
б)
wNew
s
res
в)
s
res
г)
wOld
res
s
а)
wNew
| рабочая строка s | результат res |
| "12.12.12" | "" |
| ".12.12" | "A12B" |
| ".12" | "A12B.A12B" |
| "" | "A12B.A12B.A12B" |
s = "12.12.12"
s = replaceAll ( s, "12", "A12B" )
print( s )
def replaceAll ( s, wOld, wNew ):
lenOld = len(wOld)
res = ""
while len(s) > 0:
p = s.find ( wOld )
if p < 0:
res = res + s
return
if p > 0: res = res + s[:p]
res = res + wNew
if p+lenOld >= len(s):
s = ""
else:
s = s[p+lenOld:]
return res
добавить слово-замену
строка кончилась
взять «хвост»
взять начало перед образцом
искать образец
если не нашли
s = "12.12.12"
s = s.replace( "12", "A12B" )
print ( s )
Встроенная функция:
Задачи
«A»: Напишите функцию, которая отсекает всю часть строки после первого слова.
Пример:
Введите строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды
Задачи
«B»: Напишите функцию, которая заменяет расширение файла на заданное новое расширение.
Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.exe
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.work.xml
Введите новое расширение: tmp
Результат: qq.work.tmp
Задачи
«C»: Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов.
Результат:
В 2013 году в школе 123 состоялся очередной выпуск 11 классов.
Рекурсивный перебор
Задача. В алфавите языка племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все слова, состоящие из L букв, которые можно построить из букв этого алфавита.
| Ы | ? | ? | ? |
перебор L-1 символов
| Ш | ? | ? | ? |
| Ч | ? | ? | ? |
| 0 | ? | ? | ? |
задача для слов длины К сведена к задаче для слов длины L-1!
Рекурсивный перебор
перебор 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 букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.
Задачи
«C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.
Сравнение строк
пар
парк
Пар
?
?
Сравнение по кодам символов:
| A | B | ... | Y | Z | |
| CP-1251 | 65 | 66 | ... | 89 | 90 |
| UNCODE | 65 | 66 | ... | 89 | 90 |
| a | b | ... | y | z | |
| CP-1251 | 97 | 98 | ... | 121 | 122 |
| UNCODE | 97 | 98 | ... | 121 | 122 |
| 0 | 1 | ... | 8 | 9 | |
| CP-1251 | 48 | 49 | ... | 56 | 57 |
| UNCODE | 48 | 49 | ... | 56 | 57 |
Создание матриц
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
Нулевая матрица:
| 0 | |
| 1 | |
| 2 |
| 0 | 0 |
row
A
A[0][0] = 1
1
а правильно так:
A = []
for i in range(N):
A.append ( [0]*M )
| 0 | |
| 1 | |
| 2 |
| 0 | 0 |
A
A[0][0] = 1
| 0 | 0 |
| 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
Задачи
«С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:
Перебор элементов матрицы
Главная диагональ:
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]
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 |
Выделение строк и столбцов
1-я строка:
R = A[1][:]
2-й столбец:
C = []
for row in A:
C.append(row[2])
R = A[i]
или так:
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 столбцов. Выполните отражение рисунка сверху вниз:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
| 7 | 8 | 9 |
| 4 | 5 | 6 |
| 1 | 2 | 3 |