Функции. Коллекции. Алгоритмы поиска и сортировки

Что такое функция?

Функция — это блок кода, который выполняет определённую задачу. Основное назначение функций — уменьшить повторение кода и повысить читаемость.

Типы функций:

1. Встроенные функции (например, print(), len(), max()).

2. Пользовательские функции, которые вы пишете сами.

Синтаксис функций:

• Объявление функции начинается с ключевого слова def.

• У функции могут быть параметры (аргументы), которые принимают входные данные.

• Результат работы функции можно вернуть с помощью ключевого слова return.

Пример:

# Определяем функцию
def greet(name):
    return f"Привет, {name}!"

# Вызываем функцию
print(greet("Анна"))

Аргументы функций:

1. Обязательные — должны быть переданы при вызове.

2. Необязательные — задаются с помощью значений по умолчанию.

3. Произвольное количество аргументов:

   • *args — передача кортежа аргументов.

   • **kwargs — передача словаря аргументов.

Пример с необязательными и произвольными аргументами:

def describe_city(city, country="Россия", *places):
    print(f"Город: {city}, Страна: {country}")
    for place in places:
        print(f"- {place}")
        

Задание: Напишите цикл, который переберёт числа от 0 до 20 включительно и на каждом шаге будет вызывать функцию print_friends_count(), передавая в неё аргументом очередное число: print_friends_count(0), print_friends_count(1), print_friends_count(2) …и так до print_friends_count(20).Код самой функции не изменяйте. Цикл пишите после функции: перед объявлением цикла не должно быть отступов.

# Объявите функцию здесь
...
# Код, написанный ниже, переместите внутрь объявленной вами функции
if friends_count == 0:
    print('У тебя нет друзей')
elif friends_count == 1:
    print('У тебя', friends_count, 'друг')
elif friends_count >= 2 and friends_count <= 4:
    print('У тебя', friends_count, 'друга')
elif friends_count >= 5 and friends_count < 20:
    print('У тебя', friends_count, 'друзей')
else:
    print('Ого, сколько у тебя друзей! Целых', friends_count)


# Ниже напишите цикл, в котором будет вызываться функция print_friends_count
# с аргументом от 0 до 20 включительно
...

Коллекции

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

1. Список (List)

Основные характеристики:

• Изменяемый: элементы можно добавлять, удалять и изменять.

• Упорядоченный: элементы сохраняют порядок, в котором были добавлены.

• Поддерживает дублирование: элементы могут повторяться.

Пример создания:

fruits = ["яблоко", "банан", "вишня"]

Основные операции:

• Добавление элементов: append(), insert().

• Удаление элементов: remove(), pop().

• Сортировка: sort() для изменения списка, sorted() для нового.

• Объединение: extend().

Пример:

fruits = ["яблоко", "банан", "вишня"]
fruits.append("апельсин")  # Добавление
fruits.sort()              # Сортировка # Добавить элемент
print(fruits[0])  # Доступ по индексу
fruits.remove("банан")  # Удалить элемент

Задание:

friends = ['Сергей', 'Соня', 'Дима', 'Алина', 'Егор']

# присвойте переменной index целочисленное значение,
# чтобы из списка friends была выбрана Алина
index = ...

print('Привет, ' + friends[index])

Задание 2:

1. Объявите переменную count и сохраните в ней количество друзей. Посчитайте их вызовом функции len().

2. Выведите на экран строку У тебя {количество} друзей, где {количество} — значение переменной count

print("Привет, я Анфиса!")
friends = ['Сергей', 'Соня', 'Дима', 'Алина', 'Егор']
count = …  # допишите свой код сюда
print(…)

Кортежи (Tuples)

• Упорядоченные неизменяемые коллекции.

• Обозначаются круглыми скобками.

Основные характеристики:

• Неизменяемый: после создания его содержимое нельзя изменить.

• Упорядоченный: элементы сохраняют порядок.

• Поддерживает дублирование.

Пример:

days = ("понедельник", "вторник", "среда")
print(days[1])  # Вывод второго дня недели

Задание: Создайте кортеж из названий месяцев года. Напишите программу, которая принимает от пользователя номер месяца и выводит его название.

# Здесь ваш код
months = ("Январь", "Февраль", "Март", "Апрель", "Май", "Июнь",
          "Июль", "Август", "Сентябрь", "Октябрь", "Ноябрь", "Декабрь")
# Запросите у пользователя номер месяца
# Выведите соответствующий месяц

Задание: Напишите программу, которая проверяет, содержится ли указанное пользователем значение в кортеже из популярных цветов. Если цвет найден, выведите сообщение об этом.

# Здесь ваш код
colors = ("красный", "синий", "зелёный", "жёлтый", "чёрный", "белый")
# Запросите у пользователя цвет
# Проверьте, есть ли он в кортеже

В кортеже могут храниться значения разных типов. Это одна из ключевых особенностей кортежей в Python: они позволяют хранить элементы любых типов данных, включая числа, строки, списки, словари, и даже другие кортежи.

Пример:

# Кортеж с элементами разных типов
mixed_tuple = (42, "Привет", [1, 2, 3], {"ключ": "значение"}, (True, False))

# Доступ к элементам
print(mixed_tuple[0])  # Число: 42
print(mixed_tuple[1])  # Строка: "Привет"
print(mixed_tuple[2])  # Список: [1, 2, 3]
print(mixed_tuple[3])  # Словарь: {"ключ": "значение"}
print(mixed_tuple[4])  # Вложенный кортеж: (True, False)

Примечания:

1. Неизменяемость: Хотя кортеж неизменяемый (то есть его структуру изменить нельзя), если он содержит изменяемые элементы, например, список, то эти элементы могут быть изменены:

   mixed_tuple[2].append(4)
   print(mixed_tuple)  # Изменение отразится внутри списка: (42, "Привет", [1, 2, 3, 4], {...}, ...)

2. Использование: Благодаря поддержке различных типов данных, кортежи часто применяются для упаковки разнородной информации, например, записи данных о человеке:

   person = ("Анна", 25, "Москва", ["чтение", "путешествия"])
   print(f"Имя: {person[0]}, Возраст: {person[1]}, Город: {person[2]}")
   print(f"Хобби: {', '.join(person[3])}")

Таким образом, кортежи — это мощный и универсальный инструмент для работы с неизменяемыми наборами данных.

Словари (Dictionaries)

• Неупорядоченные изменяемые коллекции пар ключ-значение.

• Обозначаются фигурными скобками.

Основные характеристики:

• Изменяемый: можно добавлять, изменять и удалять пары ключ-значение.

• Неупорядоченный (в версиях Python до 3.7), с версии 3.7 порядок добавления сохраняется.

• Ключи уникальны, значения могут повторяться.

Основные операции:

• Добавление/изменение: person["страна"] = "Россия".

• Удаление: del person["возраст"].

• Доступ: person.get("город").

Пример:

person = {"имя": "Анна", "возраст": 25}
print(person["имя"])  # Получить значение по ключу
person["город"] = "Москва"  # Добавить пару

Задание: Допишите программу так, чтобы она напечатала название города, в котором живёт Серёга.

friends =  {
    'Серёга': 'Омск',
    'Соня': 'Москва',
    'Дима': 'Челябинск'
}
# Ваш код здесь

Задание 2: Замените значение элемента с ключом 'Серёга' на 'Оренбург'

friends =  {
    'Серёга': 'Омск',
    'Соня': 'Москва',
    'Дима': 'Челябинск'
}

# Ваш код здесь

print('Серёга теперь живёт в славном городе ' + friends['Серёга'])

Задание 3:

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

Орёл
Калуга
Калининград
Дудинка 

friends =  {
    'Серёга': 'Оренбург',
    'Соня': 'Москва',
    'Миша': 'Москва',
    'Дима': 'Челябинск',
    'Алина': 'Красноярск',
    'Егор': 'Пермь',
    'Коля': 'Красноярск'
}

# Здесь ваш код

Задание 4: Добавьте в словарь friends новый элемент посредством доступа по ключу. Пусть друга зовут Даниил, а его городом будет Санкт-Петербург.Напечатайте на экране словарь friends.

friends = {
    'Серёга': 'Омск',
    'Соня': 'Москва',
    'Дима': 'Челябинск',
    'Айгуль': 'Казань',	
    'Алёна': 'Белгород'
}

# Через доступ по ключу добавьте новый элемент словаря 
# с ключом 'Даниил' и значением 'Санкт-Петербург'

# Напечатайте словарь friends 

Множества (Sets)

• Неупорядоченные изменяемые коллекции уникальных элементов.

• Обозначаются фигурными скобками без пар.

Основные характеристики:

• Изменяемое, но сами элементы должны быть неизменяемыми.

• Неупорядоченное: порядок элементов не сохраняется.

• Элементы уникальны.

Основные операции:

• Добавление: add().

• Удаление: remove(), discard().

• Операции над множествами: объединение (union()), пересечение (intersection()), разность (difference()).

Пример:

colors = {"красный", "синий", "зелёный"}
colors.add("жёлтый")  # Добавить элемент
print(colors)

Операции с коллекциями:

1. Списки: сортировка, объединение.

2. Кортежи: срезы, конкатенация.

3. Словари: извлечение ключей и значений.

4. Множества: объединение, пересечение, разность.

Пример работы с множествами:

set1 = {1, 2, 3}
set2 = {2, 3, 4}
print(set1.union(set2))  # Объединение
print(set1.intersection(set2))  # Пересечение

Задания на функции:

1. Написать функцию, которая принимает список чисел и возвращает их сумму.

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

3. Реализовать функцию, которая принимает два списка и возвращает их пересечение.

Задания на коллекции:

1. Создайте список городов, удалите один из них и добавьте два новых.

2. Напишите программу, которая находит уникальные элементы двух множеств.

3. Создайте словарь студентов с баллами, найдите студента с максимальным баллом.

АЛГОРИТМЫ

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

---

Алгоритмы поиска

1. Линейный поиск (Linear Search)

Наивный способ, где мы перебираем элементы по одному, пока не найдём нужное значение.

Характеристики:

• Сложность: O(n)O(n).

• Подходит для неотсортированных массивов.

Реализация:

def linear_search(array, target):
    for index, value in enumerate(array):
        if value == target:
            return index
    return -1

# Пример
numbers = [5, 3, 8, 6]
print(linear_search(numbers, 8))  # Вернёт 2

---

2. Бинарный поиск (Binary Search)

Работает только на отсортированных массивах. Делит массив на две части и сравнивает искомый элемент со средним.

Характеристики:

• Сложность: O(log⁡n)O(\log n).

• Быстрее линейного поиска на больших массивах.

Реализация:

def binary_search(array, target):
    left, right = 0, len(array) - 1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Пример
sorted_numbers = [1, 3, 5, 7, 9]
print(binary_search(sorted_numbers, 7))  # Вернёт 3



def binary_search(a_list, n):
     first = 0
     last = len(a_list) - 1
     while last >= first:
          mid = (first + last) // 2
          if a_list[mid] == n:
               return True
          else:
               if n < a_list[mid]:
                     last = mid - 1
               else:
                     first = mid + 1
     return False

---

Алгоритмы сортировки

1. Сортировка пузырьком (Bubble Sort)

Простой, но неэффективный метод. Повторно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они в неправильном порядке.

Характеристики:

• Сложность: O(n2)O(n^2) в худшем случае.

• Подходит для небольших массивов.

Реализация:

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

# Пример
numbers = [5, 2, 9, 1, 5, 6]
bubble_sort(numbers)
print(numbers)  # [1, 2, 5, 5, 6, 9]

---

3. Сортировка вставками (Insertion Sort)

Разбивает массив на отсортированную и неотсортированную части. Постепенно вставляет элементы из неотсортированной части в правильную позицию.

Характеристики:

• Сложность: O(n2)O(n^2).

• Подходит для почти отсортированных массивов.

Реализация:

def insertion_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key

# Пример
numbers = [12, 11, 13, 5, 6]
insertion_sort(numbers)
print(numbers)  # [5, 6, 11, 12, 13]

---

5. Сортировка слиянием (Merge Sort)

Рекурсивно делит массив на две половины, сортирует их и сливает.

Характеристики:

• Сложность: O(nlog⁡n)O(n \log n).

• Эффективен для больших массивов.

Реализация:

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Пример
numbers = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(numbers))  # [3, 9, 10, 27, 38, 43, 82]

---

Сравнение алгоритмов сортировки:

Алгоритм	Сложность (лучший случай)	Сложность (средний случай)	Сложность (худший случай)	Устойчивость
Пузырьком	O(n)O(n)	O(n2)O(n^2)	O(n2)O(n^2)	Да
Выбором	O(n2)O(n^2)	O(n2)O(n^2)	O(n2)O(n^2)	Нет
Вставками	O(n)O(n)	O(n2)O(n^2)	O(n2)O(n^2)	Да
Быстрая сортировка	O(nlog⁡n)O(n \log n)	O(nlog⁡n)O(n \log n)	O(n2)O(n^2)	Нет
Сортировка слиянием	O(nlog⁡n)O(n \log n)	O(nlog⁡n)O(n \log n)	O(nlog⁡n)O(n \log n)	Да