🐍🧩 5 классических задач по Python для начинающих с решениями

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 задач для начинающих с решениями