Упражнения

A: Максимум

Найдите индексы первого вхождения максимального элемента. Выведите два числа: номер строки и номер столбца, в которых стоит наибольший элемент в двумерном массиве. Если таких элементов несколько, то выводится тот, у которого меньше номер строки, а если номера строк равны то тот, у которого меньше номер столбца.

Программа получает на вход размеры массива n и m, затем n строк по m чисел в каждой.

3 4
0 3 2 4
2 3 5 5
5 1 2 3

1 2

B: Снежинка

Дано нечетное число n. Создайте двумерный массив из n×n элементов, заполнив его символами "." (каждый элемент массива является строкой из одного символа). Затем заполните символами "*" среднюю строку массива, средний столбец массива, главную диагональ и побочную диагональ. В результате единицы в массиве должны образовывать изображение звездочки. Выведите полученный массив на экран, разделяя элементы массива пробелами.

5

* . * . *
. * * * .
* * * * *
. * * * .
* . * . *

C: Шахматная доска

Даны два числа n и m. Создайте двумерный массив размером n×m и заполните его символами "." и "*" в шахматном порядке. В левом верхнем углу должна стоять точка.

3 4

. * . *
* . * .
. * . *

D: Диагонали параллельные главной

Дано число n. Создайте массив размером n×n и заполните его по следующему правилу. На главной диагонали должны быть записаны числа 0. На двух диагоналях, прилегающих к главной, числа 1. На следующих двух диагоналях числа 2, и т.д.

5

0 1 2 3 4
1 0 1 2 3
2 1 0 1 2
3 2 1 0 1
4 3 2 1 0

E: Побочная диагональ

Дано число n. Создайте массив размером n×n и заполните его по следующему правилу:

Числа на диагонали, идущей из правого верхнего в левый нижний угол равны 1.

Числа, стоящие выше этой диагонали, равны 0.

Числа, стоящие ниже этой диагонали, равны 2.

Полученный массив выведите на экран. Числа в строке разделяйте одним пробелом.

4

0 0 0 1
0 0 1 2
0 1 2 2 
1 2 2 2

F: Поменять столбцы

Дан двумерный массив и два числа: i и j. Поменяйте в массиве столбцы с номерами i и j.

Решение оформите в виде функции swap_columns(a: list, i: int, j:int), модифицирующей переданный список, но не возвращающей значение.

На проверку сдайте только тело функции.

a = [[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34]]
swap_columns(a, 0, 1)

[[12, 11, 13, 14], [22, 21, 23, 24], [32, 31, 33, 34]]

G: Симметричен ли массив?

Дан массив размером \(n\times n\). Проверьте, является ли этот массив симметричным относительно главной диагонали.

Решение оформите в виде функции is_symmetric(a: list) -> bool, возвращающей True или False.

is_symmetric([[0, 1, 2], [1, 2, 3], [2, 3, 4]])

True

H: k-я диагональ

Дан квадратный двумерный массив размером n×n и число k. Создайте список из элементов k-й по счету диагонали ниже главной диагонали (т.е. если k == 1, то нужно вернуть список элементов первой диагонали, лежащей ниже главной, если k == 2, то второй диагонали и т.д.).

Значение k может быть отрицательным, например, если k == -1, то нужно вернуть список элементов первой диагонали лежащей выше главной. Если k == 0, то нужно вернуть список элементов главной диагонали.

Решение оформите в виде функции kth_diagonal(a: list, k: int) -> list

Сложность алгоритма должна быть \(O(n)\), то есть нельзя осуществлять проход по всему двумерному массиву.

kth_diagonal([[1, 2, 3, 4], [5, 6, 7, 8], [0, 1, 2, 3], [4, 5, 6, 7]], 1)

[5, 1, 6]

kth_diagonal([[1, 2, 3, 4], [5, 6, 7, 8], [0, 1, 2, 3], [4, 5, 6, 7]], -2)

[3, 8]

I: Транспонировать прямоугольную матрицу

Дан двумерный массив размером n×m. Симметричный ему относительно главной диагонали массив называется транспонированным к данному. Он имеет размеры m×n: строки исходного массива становятся столбцами транспонированного, столбцы исходного массива становятся строками транспонированного.

Для данного массива постройте транспонированный массив. Решение оформите в виде функции transpose(a: list) -> list, получающей на вход список списков (и не модифицирующей его) и возвращающей новый список.

transpose([[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34]])

[[11, 21, 31], [12, 22, 32], [13, 23, 33], [14, 24, 34]]

J: Транспонировать квадратную матрицу

Дан двумерный массив размером n×n. Транспонируйте его, записав результат в тот же массив. Вспомогательный список использовать нельзя.

Решение оформите в виде функции transpose(a: list), получающей на вход данный массив. Функция переставляет элементы внутри массива a, и не возвращает никакого значения.

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose(a)

[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

K: Поменять две диагонали

Дан квадратный массив. Поменяйте местами элементы, стоящие на главной и побочной диагонали, при этом каждый элемент должен остаться в том же столбце (то есть в каждом столбце нужно поменять местами элемент на главной диагонали и на побочной диагонали).

Решение оформите в виде функции swap_diagonals(a). Функция переставляет элементы внутри массива a, и не возвращает никакого значения.

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
swap_diagonals(a)

[[7, 2, 9], [4, 5, 6], [1, 8, 3]]

L: Таблица умножения

По данным числам n и m создайте массив из n строк и m столбцов и заполните его таблицей умножения чисел от 1 до n на числа от 1 до m (должен получиться массив, заполненный значениями типа int).

Выведите полученную таблицу, отводя на вывод каждого числа ровно 4 символа, то есть таблица при выводе должна состоять из столбцов шириной в 4 символа, числа должны быть выровнены по правому краю столбца (в каждой строке должно быть выведено 4*m символов).

4 5

   1   2   3   4   5
   2   4   6   8  10
   3   6   9  12  15
   4   8  12  16  20

M: Число маршрутов короля

В левом верхнем углу доски размером n×m стоит шахматный король. За один ход он может сделать ход вправо, вниз или на одну клетку по диагонали вправо-вниз. Посчитайте количество маршрутов, ведущий из левого верхнего угла доски в правый нижний.

Программа получает на вход размеры доски (числа n и m) и должна вывести число искомых маршрутов.

3 4

25

N: Одномерный список в двумерный

Дан одномерный список элементов. Сделайте из него двумерный список, содержащий по \(n\) элементов в каждой строке (быть может, кроме последней). В последней строке может быть меньше \(n\) элементов (но должен быть хотя бы один элемент).

Решение оформите в виде функции to_2d(a: list, n: int) -> list, принимающей в качестве параметра список чисел и значение \(n\) и возвращающей новый список чисел.

to_2d([1, 2, 3, 4, 5, 6, 7, 8, 9], 5)

[[1, 2, 3, 4, 5], [6, 7, 8, 9]]

O: Заполнение змейкой

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m “змейкой”, как показано в примере (должен получиться массив, заполненный значениями типа int).

Выведите полученный массив, отводя на вывод каждого элемента ровно 4 символа.

3 5

   1   2   3   4   5
  10   9   8   7   6
  11  12  13  14  15

P: Заполнение диагоналями

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m “диагоналями”, как показано в примере. (должен получиться массив, заполненный значениями типа int).

Выведите полученный массив, отводя на вывод каждого элемента ровно 4 символа.

3 5

   1   2   4   7  10
   3   5   8  11  13
   6   9  12  14  15

Q: Поворот прямоугольного массива

Дан прямоугольный массив размером \(n\times m\). Поверните его на 90 градусов по часовой стрелке, записав результат в новый массив размером \(m\times n\).

Решение оформите в виде функции rotate(a: list) -> list, получающей на вход данный массив и возвращающей новый массив, не модифицируя исходный массив.

rotate([[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34]])

[[31, 21, 11], [32, 22, 12], [33, 23, 13], [34, 24, 14]]

R: Поворот квадратного массива

Дан квадратный массив. Поверните его на 90 градусов по часовой стрелке. Результат запишите в этот же массив, вспомогательный массив использовать нельзя.

Решение оформите в виде функции rotate(a: list), получающей на вход данный массив. Функция переставляет элементы внутри массива a, и не возвращает никакого значения.

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(a)

[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

S: Заполнение в шахматном порядке

Даны числа n и m. Заполните массив размером \(n\times m\) в шахматном порядке: клетки одного цвета заполнены нулями, а другого цвета — заполнены числами натурального ряда сверху вниз, слева направо (должен получиться массив, заполненный значениями типа int). В левом верхнем углу записано число 1.

Выведите полученный массив на экран, отводя на вывод каждого элемента ровно 4 символа.

3 5

   1   0   2   0   3
   0   4   0   5   0
   6   0   7   0   8

T: Сапер

На поле для игры в сапер клеточки с минами обозначаются символом “*”, а в каждой пустой клеточке записано число от 0 до 8, равное количеству мин в 8 клетках, соседних с данной.

Дан список мин на поле. Постройте по данному списку изображение поля.

Программа получает на вход числа N и M - количество строк и столбцов на поле, а также количество мин на поле K. Далее идет K пар чисел - координат мин. Первое число - номер строки, второе число - номер столбца.

Выведите изображение поля на экран, клетки при выводе разделяйте одним пробелом.

3 2 2
1 1
2 2

* 2
2 *
1 1

2 2 0

0 0
0 0

U: Ходы коня

Дана шахматная доска из \(N\) строк и \(M\) столбцов. На ней стоит \(K\) шахматных коней. Постройте изображение доски, отметив на ней коней и клетки, которые бьют кони.

Клетку, где стоит конь, отметьте буквой “K”, клетки, которые бьет конь (но в ней нет коня), отметьте символами “*”, остальные клетки заполните точками.

Первая строка входных данных содержит три числа \(N\), \(M\), \(K\): количество строк доски, количество столбцов в доске и количество коней на доске (\(1\le N\le 300\), \(1\le M\le 300\), \(0\le K \le 10000\)).

В следующих \(K\) строках содержатся координаты коней  по два числа \(x_i\), \(y_i\) (\(0\le x_i\lt N\), \(0\le y_i\lt M\)), номер строки и номер столбца очередного коня соответственно (нумерация с нуля сверху вниз, слева направо).

Выведите на экран изображение доски, разделяя символы в строке пробелами.

Решение должно иметь сложность \(O(NM + K)\), решение сложности \(O(NMK)\), то есть перебирающее все клетки доски, и для каждой клетки перебирающее всех коней, не пройдет по времени.

Решение, в котором все возможные ходы коня перебираются “ручным” разбором случаев, приниматься не будут. Как красиво перебирать ходы коня:

MOVES = [[2, 1], [2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2], [-2, 1], [-2, -1]]
...
for dx, dy in MOVES:
    nx, ny = x + dx, y + dy

4 7 2
1 1
3 6

. . . * . . .
. K . . . * .
. . . * * . .
* . * . . . K

3 3 2
1 0
2 2

. * *
K . .
. . K

V: Ходы ферзя

Решите предыдущую задачу для ферзя. Ферзь обозначается буквой “Q”. Ограничение на количество ферзей: \(0\le K\le 300\). Требуемая сложность алгоритма: \(O(NM + K(N + M))\).

4 7 1
1 1

* * * . . . .
* Q * * * * *
* * * . . . .
. * . * . . .

3 3 2
0 0
2 0

Q * *
* * .
Q * *

W: Заполнение спиралью

По данным числам n и m заполните двумерный массив размером n×m числами от 1 до n×m по спирали, выходящей из левого верхнего угла и закрученной по часовой стрелке, как показано в примере (должен получиться массив, заполненный значениями типа int).

Выведите полученный массив, отводя на вывод каждого элемента ровно 4 символа.

Тесты к этой задаче закрытые.

4 5

   1   2   3   4   5
  14  15  16  17   6
  13  20  19  18   7
  12  11  10   9   8

X: K-мерный массив

Дано натуральное число \(k\). Сделайте \(k\)-мерный массив (систему списков уровня вложенности \(k\)) размера 2 по каждому измерению, то есть общее число элементов в списке должно быть \(2^k\). Заполните его нулями.

Решение оформите в виде функции gen_x(k: int) -> list.

На проверку сдайте только тело функции.

Обязательное требование - каждый элемент массива должен содержать различные вложенные массивы, а не ссылки на один и тот же массив. Как проверить своё решение?

Проверка 1. Пусть функция вернула список: a = gen_x(k). Проверьте, что условие a[0] is a[1]  — ложно.

Проверка 2. Измените элемент массива, у которого все индексы равны 0, присвоив ему значение 1. Это можно сделать при помощи следующего кода (A — исходный массив):

b = a
for i in range(k - 1):
    b = b[0]
b[0] = 1

Выведите массив после изменения. В массиве должна быть только одна единица.

1

[0, 0]

2

[[0, 0], [0, 0]]

3

[[[0, 0], [0, 0]], [[0, 0], [0, 0]]]

Y: K-мерный массив - 2

Дано натуральное число \(k\). Сделайте \(k\)-мерный массив размера 2 по каждому измерению.

Массив заполните строковыми значениями по формуле: \[ a[i_1][i_2]...[i_k] = \mbox{str}(i_1)+\mbox{str}(i_2)+...+\mbox{str}(i_k) \]

Например, если k == 4, то a[0][0][1][0] == '0010'.

Решение оформите в виде функции gen_y(k: int) -> list.

На проверку сдайте только тело функции.

gen_y(1)

['0', '1']

gen_y(2)

[['00', '01'], ['10', '11']]

gen_y(3)

[[['000', '001'], ['010', '011']], [['100', '101'], ['110', '111']]]

Z: K-мерный массив - 3

Дан набор из \(k\) натуральных чисел \(n_1\), \(n_2\), ..., \(n_k\).

Создайте \(k\)-мерный массив размера \(n_1\times n_2\times ... \times n_k\). Заполните его целыми числами по формуле: \[ a[i_1][i_2]...[i_k] = i_1 + 2i_2 + ... + ki_k. \]

Решение оформите в виде функции gen_z(dimensions: list) -> list. Передаваемый параметр: список размеров массива по каждому измерению.

На проверку сдайте только тело функции.

gen_z([2, 3])

[[0, 2, 4], [1, 3, 5]]

gen_z([3, 2])

[[0, 2], [1, 3], [2, 4]]

gen_z([2, 2, 2])

[[[0, 3], [2, 5]], [[1, 4], [3, 6]]]