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)
***
Материалы по теме
🐍🧩 Задача об определении латинского квадрата
🐍🧩 Задача о поврежденной XML-строке
🐍🧩 Словари в Python: 12 задач для начинающих с решениями