Примеры заданий по программированию для уроков информатики

Раздел: Образование -> Информатика и программирование

В данном разделе рассматриваются типовые задачи по информатике, решаемые с помощью языка программирования Python. Каждая задача сопровождается несколькими вариантами реализации, описанием возникающих проблем и способов их устранения. Для удобства код и результаты выделены в блоки.

Практические задачи и их решения

Как проверить, является ли строка палиндромом?

Основной подход

Простейший способ - сравнить строку с её обратной копией. В Python это делается с помощью среза [::-1].

def is_palindrome(s):
    return s == s[::-1]

print(is_palindrome('radar'))  # True
print(is_palindrome('hello'))  # False

информатика python задачи (задачи по информатике на python)

Пояснение

Срез [::-1] создаёт перевёрнутую копию строки. Сравнение возвращает True, если строки идентичны. Учтите, что регистр имеет значение.

Вариант 1: игнорирование регистра и пробелов

Для более сложного палиндрома (например, 'А роза упала на лапу Азора') нужно очистить строку от лишних символов и привести к нижнему регистру.

import re
def is_palindrome_clean(s):
    cleaned = re.sub(r'[^a-zA-Zа-яА-ЯёЁ0-9]', '', s).lower()
    return cleaned == cleaned[::-1]

print(is_palindrome_clean('А роза упала на лапу Азора'))  # True

Модуль re - регулярные выражения. Функция sub заменяет все небуквенно-цифровые символы на пустую строку.

Вариант 2: рекурсивный метод

Можно проверять палиндром рекурсивно, сравнивая первый и последний символ.

def is_palindrom_rec(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrom_rec(s[1:-1])

print(is_palindrom_rec('radar'))  # True

Этот подход менее эффективен из-за создания подстрок на каждом шаге и глубины рекурсии.

Типичные ошибки

  • Забыли учесть регистр и пробелы, из-за чего строка 'Radar' с разным регистром не считается палиндромом.
  • Переполнение стека при рекурсивном решении для длинных строк (более 1000 символов).
  • Некорректная обработка символов Unicode (например, кириллицы) - срез [::-1] работает корректно, но регулярное выражение может не включать кириллицу, если не указать диапазон.

Для устранения последней ошибки используйте в регулярном выражении [^a-zA-Zа-яА-ЯёЁ0-9] или более универсальный шаблон [^\w] (но \w включает только буквы латиницы и цифры в Python). Лучше всего очищать с помощью str.isalpha() или str.isalnum().

Как отсортировать список методом выбора?

Основной подход

Сортировка выбором (selection sort) заключается в нахождении минимального элемента на каждом шаге и обмене его с первым неупорядоченным элементом.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

arr = [64, 25, 12, 22, 11]
print(selection_sort(arr))  # [11, 12, 22, 25, 64]

Алгоритм имеет сложность O(n^2), подходит для небольших массивов.

Вариант 1: использование встроенной сортировки

В Python есть встроенный метод sort() и функция sorted(), которые реализуют Timsort (гибридный алгоритм) с эффективностью O(n log n).

arr = [64, 25, 12, 22, 11]
arr.sort()
print(arr)  # [11, 12, 22, 25, 64]

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

Вариант 2: пузырьковая сортировка

Ещё один классический алгоритм - пузырьковая сортировка. Она проще в реализации, но менее эффективна.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

arr = [64, 25, 12, 22, 11]
print(bubble_sort(arr))  # [11, 12, 22, 25, 64]

Пузырьковая сортировка также O(n^2), но на практике работает медленнее из-за большего количества обменов.

Типичные ошибки

  • Ошибка индексации (выход за границы) при обмене, особенно в сортировке выбором. Важно, что внутренний цикл начинается с i+1.
  • Неправильная работа с копией списка: если нужно сохранить исходный список, следует передавать копию (arr[:]) или использовать sorted().
  • Сортировка списка с разными типами данных (например, числа и строки) вызывает TypeError. Необходимо приводить к общему типу.

Как найти наибольший общий делитель двух чисел?

Основной подход

Алгоритм Евклида - эффективный способ вычисления НОД. Он основан на том, что НОД(a, b) = НОД(b, a % b) для целых чисел.

def gcd_euclid(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd_euclid(48, 18))  # 6
print(gcd_euclid(17, 5))   # 1

Этот алгоритм работает за O(log min(a,b)).

Вариант 1: рекурсивная реализация

def gcd_rec(a, b):
    return a if b == 0 else gcd_rec(b, a % b)

print(gcd_rec(48, 18))  # 6

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

Вариант 2: использование встроенной функции math.gcd

В Python 3.5 и выше есть функция gcd в модуле math.

import math
print(math.gcd(48, 18))  # 6

Это самый надёжный и быстрый способ.

Типичные ошибки

  • Не учтён случай отрицательных чисел: алгоритм Евклида работает только с неотрицательными. Для отрицательных можно брать модуль.
  • Некорректный результат при нуле: math.gcd(0,0) возвращает 0, но обычно НОД(0,0) не определён. Необходима проверка.
  • Использование перебора делителей для больших чисел крайне неэффективно.

Как получить последовательность чисел Фибоначчи?

Основной подход

Итеративный метод с циклом - наиболее эффективный. Вычисление n первых чисел Фибоначчи.

def fibonacci(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]
    fib = [0, 1]
    for i in range(2, n):
        fib.append(fib[-1] + fib[-2])
    return fib

print(fibonacci(10))  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Сложность O(n), память O(n).

Вариант 1: рекурсивный подход (без мемоизации)

def fib_rec(n):
    if n <= 1:
        return n
    return fib_rec(n-1) + fib_rec(n-2)

# Вычисление отдельного числа
print(fib_rec(10))  # 55

Этот метод экспоненциальный O(2^n), крайне неэффективен для n больше 30.

Вариант 2: рекурсия с мемоизацией (кэширование)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

print(fib_memo(100))  # 354224848179261915075

lru_cache автоматически кэширует результаты, делая сложность O(n) при первом вызове. Однако для получения последовательности требуется вызывать функцию для каждого n.

Типичные ошибки

  • Рекурсивная реализация без мемоизации приводит к огромному времени выполнения или переполнению стека для n > 1000.
  • Неверное начальное условие: последовательность Фибоначчи может начинаться с 0,1 или с 1,1. В большинстве задач подразумевается F0=0, F1=1.
  • При больших n (например, 1000) числа Фибоначчи становятся огромными, и вычисления в Python занимают много памяти, но это решаемо.

Ниже приведены расширенные примеры с более сложными сценариями использования.

Расширенные примеры

1. Палиндром: обработка сложных строк

Пример: игнорирование не только пробелов, но и знаков препинания, работа с Unicode. Используем таблицу перевода символов для удаления диакритических знаков (для упрощения приведён базовый вариант).

Пример 
import unicodedata
import re

def normalize_text(s):
    # Удаление диакритических знаков (например, é -> e)
    nfkd = unicodedata.normalize('NFKD', s)
    ascii_str = nfkd.encode('ASCII', 'ignore').decode('ASCII')
    return re.sub(r'[^a-zA-Z0-9]', '', ascii_str).lower()

def is_palindrom_unicode(s):
    cleaned = normalize_text(s)
    return cleaned == cleaned[::-1]

test = 'Évitons les détails!'  # на самом деле не палиндром, но для демонстрации
print(is_palindrom_unicode('A man, a plan, a canal, Panama'))  # True
print(is_palindrom_unicode('Racecar'))  # True
True
True

2. Сортировка выбором с подсчётом операций

Добавим счётчик сравнений и обменов для анализа эффективности.

Пример 
def selection_sort_count(arr):
    n = len(arr)
    comparisons = 0
    swaps = 0
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            comparisons += 1
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            swaps += 1
    return arr, comparisons, swaps

arr = [29, 10, 14, 37, 13]
result, comp, sw = selection_sort_count(arr[:])
print(f'Массив: {result}, сравнений: {comp}, обменов: {sw}')
Массив: [10, 13, 14, 29, 37], сравнений: 10, обменов: 3

3. НОД для списка чисел

Расширение алгоритма Евклида на несколько чисел с использованием reduce.

Пример 
from functools import reduce
import math

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

print(gcd_list([48, 18, 30]))  # 6
print(gcd_list([17, 5, 25]))   # 1
6
1

4. Генерация чисел Фибоначчи с помощью генератора

Использование функции-генератора для экономии памяти при больших n.

Пример 
def fib_generator(limit):
    a, b = 0, 1
    for _ in range(limit):
        yield a
        a, b = b, a + b

# Получить первые 15 чисел
print(list(fib_generator(15)))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

5. Рекурсивный НОД с использованием бинарного алгоритма

Бинарный алгоритм Евклида (алгоритм Штейна) использует битовые операции для ускорения.

Пример 
def gcd_binary(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    shift = 0
    while ((a | b) & 1) == 0:
        shift += 1
        a >>= 1
        b >>= 1
    while (a & 1) == 0:
        a >>= 1
    while b != 0:
        while (b & 1) == 0:
            b >>= 1
        if a > b:
            a, b = b, a
        b -= a
    return a << shift

print(gcd_binary(48, 18))  # 6
print(gcd_binary(17, 5))   # 1
6
1

Этот алгоритм может быть быстрее для больших чисел, хотя на практике math.gcd уже оптимизирован.

Задачи по информатике на Python - comments

En
информатика python задачи (python)