1. Заполнение матрицы по спирали
Эта классическая задача часто встречается на собеседованиях и олимпиадах. Рассмотрим несколько способов решения на Python.
На вход программе подаются два натуральных числа n и m. Напишите программу, которая создает матрицу размером n х m, заполнив ее по спирали числами от 1 до n x m. Спираль начинается в левом верхнем углу и закручивается по часовой стрелке.
Пример ввода:
7 6
Пример вывода:
1 2 3 4 5 6
22 23 24 25 26 7
21 36 37 38 27 8
20 35 42 39 28 9
19 34 41 40 29 10
18 33 32 31 30 11
17 16 15 14 13 12
Решение
Способ 1:
n, m = map(int, input().split())
matrix = [[0] * m for _ in range(n)]
dx, dy, x, y = 0, 1, 0, 0
for i in range(1, n * m + 1):
matrix[x][y] = i
if matrix[(x + dx) % n][(y + dy) % m]:
dx, dy = dy, -dx
x += dx
y += dy
for line in matrix:
print(*(f'{i:<3}' for i in line), sep='')
Способ 2:
n, m = (int(i) for i in input().split())
spiral = []
x, y, dx, dy, k = 0, 0, 1, 0, 1
spiral = [[0]* n for _ in range(m)]
for i in range(1, n * m + 1):
spiral[x][y] = i
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and spiral[nx][ny] == 0:
x, y = nx, ny
else:
dx, dy = -dy, dx
x, y = x + dx, y + dy
for i in range(n):
for j in range(m):
print(str(spiral[j][i]).ljust(3), end=' ')
print()
Способ 3:
n, m = [int(i) for i in input().split()]
spiral = [[0] * m for _ in range(n)]
c = 1
for k in range(min(n // 2 + 1, m //2 + 1)):
for j in range(k, m - k):
if spiral[k][j] == 0:
spiral[k][j] = c
c += 1
for i in range(1 + k, n - k):
if spiral[i][m - k - 1] == 0:
spiral[i][m - k - 1] = c
c += 1
for j in range(m - k - 2, k - 1, -1):
if spiral[n - k - 1][j] == 0:
spiral[n - k - 1][j] = c
c += 1
for i in range(n - k - 2, k, -1):
if spiral[i][k] == 0:
spiral[i][k] = c
c += 1
for i in range(n):
for j in range(m):
print(str(spiral[i][j]).ljust(3), end=' ')
print()
2. Единственный выживший
Это вариант классической задачи Иосифа Флавия. В кругу стоят n человек, пронумерованных числами от 1 до n. Начинается расчет, при котором каждый k-й по счету человек выбывает из круга, после чего счет продолжается со следующего за ним человека. Напишите программу, определяющую номер человека, который останется в кругу последним.
Входные данные:
Числа n и k на отдельных строках.
#Пример ввода
9 3
Выходные данные:
Номер последнего оставшегося человека.
#Пример вывода
1
Решение
Способ 1:
n, k = int(input()), int(input())
last = 0
for i in range(1, n + 1):
last = (last + k) % i
print(last + 1)
Способ 2 – рекурсия:
def lastSurvivor(n, k):
if n == 1:
return 1
elif n > 1:
return (1 + (lastSurvivor(n - 1, k) + k - 1) % n)
n, k = int(input()), int(input())
print(lastSurvivor(n, k))
3. Определение магического квадрата
Магические квадраты издавна интриговали воображение людей: дата изготовления древнейшей сохранившейся таблицы относится к 2200 г. до н.э. Магический квадрат – это квадратная таблица размера n х n, составленная из всех чисел 1, 2, 3 … n2 таким образом, что суммы по каждому столбцу, каждой строке и каждой диагонали равны между собой. Напишем программу, которая определяет, можно ли считать матрицу магическим квадратом.
Входные данные:
Число n, затем n строк с n цифр в каждой.
#Пример ввода
3
8 1 6
3 5 7
4 9 2
Выходные данные:
YES, если введенная матрица является магическим квадратом, и NO в обратном случае.
#Пример вывода
YES
Решение
Способ 1:
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
if all(i in sum(matrix,[]) for i in range(1, n**2 + 1)):
print('YES' if all(sum(i) == sum(j) == sum([matrix[i][i] for i in range(n)]) == sum([matrix[n-i-1][i] for i in range(n)]) for i in matrix for j in list(map(list, zip(*matrix)))) else 'NO')
else:
print('NO')
Способ 2 – с магической константой и множествами:
n = int(input())
square = [[*map(int, input().split())] for _ in range(n)]
m_const = n * (1 + n ** 2) // 2
print(('NO', 'YES')[all(sum(el) == m_const for x in (((square[i][i] for i in range(n)),(square[i][~i] for i in range(n))), square, zip(*square)) for el in x) and set(sum(square, [])) == set(range(1, n ** 2 + 1))])
4. Разделение списка на подсписки
На вход подается строка чисел, из которой формируется список. Напишите программу, создающую вложенный список, элементами которого являются все возможные подсписки исходного списка, включая пустой.
Пример ввода:
a f z
Пример вывода:
[[], ['a'], ['f'], ['z'], ['a', 'f'], ['f', 'z'], ['a', 'f', 'z']]
Решение
Способ 1:
lst = input().split()
def sub_lists(lst):
lists = [[]]
for i in range(len(lst) + 1):
for j in range(i):
lists.append(lst[j:i])
lists = sorted(lists, key=len)
return lists
print(sub_lists(lst))
Способ 2:
print([[]] + [lst[j:i + j + 1] for lst in [input().split()] for i in range(len(lst)) for j in range(len(lst) - i)])
Способ 3:
st, lst = input().split(), [[]]
for i in range(1, len(st) + 1):
for j in range(len(st) - i + 1):
lst += [st[j:j+i]]
print(lst)
5. Ходы шахматного ферзя
На шахматной доске 8 х 8 стоит ферзь. Отметьте положение ферзя на доске и все клетки, которые бьет ферзь. Клетку, где стоит ферзь, отметьте буквой Q, клетки, которые бьет ферзь, отметьте звездочками *, остальные клетки заполните точками. Шахматный ферзь может ходить по вертикали, горизонтали и по диагоналям.
Входные данные:
Координаты ферзя на шахматной доске в формате номер столбца (буква от a до h, слева направо) и номер строки (цифра от 1 до 8, снизу вверх).
Пример ввода:
c4
Выходные данные:
Программа выводит стилизованное изображение шахматной доски со схемой возможных передвижений ферзя.
Пример вывода:
. . * . . . * .
. . * . . * . .
* . * . * . . .
. * * * . . . .
* * Q * * * * *
. * * * . . . .
* . * . * . . .
. . * . . * . .
Решение
Способ 1:
x, y, board = *('abcdefgh87654321'.index(i) % 8 for i in input()), range(8)
[print(*['?Q**.'[len({j - x, x - j, i - y, y - i})] for j in board]) for i in board]
Способ 2:
x, y = ('abcdefgh87654321'.index(i) % 8 for i in input())
directions = lambda i, j: (j - i == x - y) + (j + i == x + y) + ((j == x) != (i == y))
[print(*['.*Q'[directions(i, j)] for j in range(8)]) for i in range(8)]
Способ 3:
coor = input()
board = [['.'] * 8 for _ in range(8)]
y, x = 8 - int(coor[1]), ord(coor[0]) - 97
for i in range(8):
for j in range(8):
if (y == i) or (x == j) or abs(y - i) == abs(x - j):
board[i][j] = '*'
board[y][x] = 'Q'
for line in board:
print(*line)
Комментарии