Алгоритмы и программы (функция, рекурсия, работа со строками, работа с файлами, сортировка, граф)

Информатика · Компьютерное мышление

Функция — именованный фрагмент программы: def f(x): return x * x + 1. Команда return возвращает результат в место вызова: f(2) = 5, а f(f(2)) = f(5) = 26. У параметра может быть значение по умолчанию: def p(a, b=2). Рекурсия — функция вызывает сама себя; обязательно нужен базовый случай, останавливающий вызовы. Факториал: f(n) = n · f(n − 1), а f(1) = 1; поэтому f(5) = 5 · 4 · 3 · 2 · 1 = 120.

Строки. Символы нумеруются с нуля, срезы работают как у списков: для s = "Astana" s[0] = "A", s[1:4] = "sta", s[::-1] = "anatsA". Методы: len(s) — длина; s.upper() и s.lower() — регистр; s.count("a") — сколько раз встречается подстрока; s.find("t") — индекс первого вхождения; s.replace("a", "o") — замена; s.split("-") — разбить на список. Строку изменить нельзя: методы возвращают новую строку. Регистр важен: "A" и "a" — разные символы.

Файлы. f = open("data.txt", "r") открывает файл для чтения; режим "w" — запись (старое содержимое стирается), "a" — дозапись в конец. Методы: f.read() — весь текст, f.readline() — одна строка, f.readlines() — список строк, f.write(текст) — запись; в конце f.close(). Символ \n означает переход на новую строку.

Сортировка и графы. Пузырьковая сортировка сравнивает соседние элементы и меняет их местами, если они стоят неверно; за один проход наибольший элемент «всплывает» в конец. Один проход для [5, 2, 8, 1] даёт [2, 5, 1, 8]. В худшем случае нужно n(n − 1)/2 обменов (для 4 элементов — 6). Встроенные средства: a.sort() сортирует сам список, sorted(a) возвращает новый. Граф — вершины, соединённые рёбрами; его задают матрицей смежности (1 — ребро есть) или весовой матрицей (длины дорог). В дереве с n вершинами n − 1 ребро. Кратчайший путь находят, сравнивая суммы длин разных маршрутов.

Главное

Ловушка на тесте

В рекурсии важно, где стоит print. Если печать идёт ПОСЛЕ рекурсивного вызова, числа выводятся в обратном порядке вызовов: r(3) напечатает 1 2 3, а не 3 2 1. И ещё: sorted(a) не меняет список a, а вот a.sort() — меняет.

Проверь себя

1. один верный ответ

Что будет выведено на экран в результате выполнения программы?

for i in range(2, 10, 3):
    print(i, end=' ')
  1. A. 2 5 8
  2. B. 2 5 8 11
  3. C. 3 6 9
  4. D. 2 3 4 5 6 7 8 9
Показать ответ и разбор

Верный ответ: A

Разбор: range(2, 10, 3): начинаем с 2, шаг 3, останавливаемся до 10: 2, 5, 8. Следующее число 11 уже не меньше 10.

2. один верный ответ

Что будет выведено на экран в результате выполнения программы?

n = 100
k = 0
while n > 1:
    n = n // 2
    k += 1
print(k)
  1. A. 6
  2. B. 7
  3. C. 50
  4. D. 5
Показать ответ и разбор

Верный ответ: A

Разбор: n меняется так: 100 → 50 → 25 → 12 → 6 → 3 → 1. Сделано 6 делений, после чего условие n > 1 ложно. Программа считает, сколько раз число можно разделить нацело на 2.

3. один верный ответ

Что будет выведено на экран в результате выполнения программы?

x = 15
if x % 3 == 0 and x % 5 == 0:
    print("A")
elif x % 3 == 0:
    print("B")
elif x % 5 == 0:
    print("C")
else:
    print("D")
  1. A. A
  2. B. B
  3. C. A B C
  4. D. D
Показать ответ и разбор

Верный ответ: A

Разбор: 15 делится и на 3, и на 5 — первое условие истинно, печатается A. Ветки elif проверяются, только если предыдущие условия ложны, поэтому B и C не печатаются.

Открыть конспект в тренажёре →Бесплатно, без регистрации