Решаем задачи Python

8. Задача о сортировке: Реализовать свой алгоритм сортировки и сравнить его производительность с встроенной функцией сортировки Python.

Идея решения:

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

Идея быстрой сортировки заключается в следующем:

1. Выбирается опорный элемент из массива.

2. Массив разделяется на две подгруппы: одна содержит элементы, меньшие опорного, а другая – большие.

3. Рекурсивно применяется алгоритм к каждой подгруппе.

Для сравнения производительности нашего алгоритма сортировки с встроенной функцией сортировки Python (например, `sorted()`), мы можем измерить время выполнения каждого метода на одних и тех же данных.

Код:

```python

import time

import random

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[len(arr) // 2]

left = [x for x in arr if x < pivot]

middle = [x for x in arr if x == pivot]

right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

# Функция для замера времени выполнения

def measure_time(sort_function, arr):

start_time = time.time()

sorted_arr = sort_function(arr)

end_time = time.time()

return sorted_arr, end_time – start_time

# Генерация случайного списка для сортировки

arr = [random.randint(0, 1000) for _ in range(1000)]

# Сравнение производительности с собственной и встроенной сортировкой

sorted_arr_custom, time_custom = measure_time(quick_sort, arr)

sorted_arr_builtin, time_builtin = measure_time(sorted, arr)

print("Время выполнения собственной сортировки:", time_custom)

print("Время выполнения встроенной сортировки:", time_builtin)

```

Объяснения к коду:

– `quick_sort`: Это наша реализация алгоритма быстрой сортировки. Он разбивает массив на подмассивы вокруг опорного элемента, рекурсивно сортируя каждую подгруппу, а затем объединяет их в один отсортированный массив.

– `measure_time`: Это функция, которая принимает на вход функцию сортировки и список для сортировки, замеряет время выполнения этой функции над списком и возвращает отсортированный список и время выполнения.

– Мы генерируем случайный список `arr` для сортировки.

– Затем мы вызываем `measure_time` для нашей собственной реализации быстрой сортировки и для встроенной функции сортировки Python (`sorted()`).

– Наконец, мы выводим время выполнения каждой из функций сортировки для сравнения.

9. Задача о рекурсии: Реализовать алгоритм бинарного поиска с использованием рекурсии.

Идея решения:

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

Код:

```python

def binary_search_recursive(arr, target, left, right):

if left > right:

return -1

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

return binary_search_recursive(arr, target, mid + 1, right)

else:

return binary_search_recursive(arr, target, left, mid – 1)

# Пример использования:

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]

target = 11

index = binary_search_recursive(arr, target, 0, len(arr) – 1)

if index != -1:

print(f"Элемент {target} найден в позиции {index}.")

else:

print(f"Элемент {target} не найден.")

```

Объяснения к коду:

– Функция `binary_search_recursive` принимает отсортированный массив `arr`, искомый элемент `target`, левую границу `left` и правую границу `right`.

– Если `left` больше `right`, значит, искомый элемент не найден, поэтому функция возвращает `-1`.

– Иначе, находим индекс `mid` элемента в середине отрезка между `left` и `right`.

– Если значение в `arr[mid]` равно `target`, возвращаем `mid`.

– Если `arr[mid]` меньше `target`, рекурсивно вызываем функцию для правой половины массива, начиная с `mid + 1`.

– Если `arr[mid]` больше `target`, рекурсивно вызываем функцию для левой половины массива, заканчивая `mid – 1`.

– Пример использования демонстрирует поиск элемента `11` в массиве `arr`, результатом будет сообщение о том,что элемент найден в позиции `5`.

10. Задача о проверке на анаграмму: Написать программу, которая определяет, являются ли две строки анаграммами (состоят ли они из одних и тех же символов, но в другом порядке).

Для решения этой задачи мы можем воспользоваться следующим подходом:

1. Убедимся, что длины обеих строк равны. Если нет, то они не могут быть анаграммами.

2. Преобразуем обе строки в нижний регистр (для упрощения сравнения).

3. Отсортируем символы в обеих строках.

4. Сравним отсортированные строки. Если они равны, то строки являются анаграммами, иначе нет.

Пример кода на Python, реализующий этот подход:

```python

def are_anagrams(str1, str2):

# Проверяем, равны ли длины строк

if len(str1) != len(str2):

return False

# Преобразуем строки в нижний регистр

str1 = str1.lower()

str2 = str2.lower()

# Сортируем символы в обеих строках

sorted_str1 = ''.join(sorted(str1))

sorted_str2 = ''.join(sorted(str2))

# Сравниваем отсортированные строки

if sorted_str1 == sorted_str2:

return True

else:

return False

# Пример использования

string1 = "listen"

string2 = "silent"

if are_anagrams(string1, string2):

print(f"{string1} и {string2} – анаграммы.")

else:

print(f"{string1} и {string2} – не анаграммы.")

```

Этот код сначала проверяет, равны ли длины строк. Если да, он преобразует обе строки в нижний регистр и сортирует их символы. Затем он сравнивает отсортированные строки. Если они равны, функция возвращает `True`, что указывает на то, что строки являются анаграммами. В противном случае возвращается `False`.

Пояснения к коду:

Определение функции `are_anagrams`:

– Эта функция принимает две строки в качестве аргументов и возвращает булево значение, указывающее, являются ли они анаграммами.

Проверка длин строк:

– Сначала функция проверяет длины обеих строк. Если они не равны, то они не могут быть анаграммами, и функция возвращает `False`.

Преобразование строк в нижний регистр:

– Затем обе строки преобразуются в нижний регистр при помощи метода `lower()`. Это делается для упрощения сравнения, так как мы не хотим учитывать регистр при проверке на анаграмму.

Сортировка символов в строках:

– После этого символы в каждой строке сортируются в алфавитном порядке при помощи функции `sorted()`.

– Мы объединяем отсортированные символы обратно в строки при помощи метода `join()`. Это дает нам отсортированные версии строк.

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

– Отсортированные строки сравниваются. Если они равны, то строки являются анаграммами, и функция возвращает `True`. Если они не равны, функция возвращает `False`.

Пример использования:

– В конце кода показан пример использования функции, где две строки `"listen"` и `"silent"` проверяются на анаграмму.

– Выводится соответствующее сообщение в зависимости от результата проверки.

Таким образом, этот код эффективно проверяет строки на анаграммы, используя описанный выше алгоритм.

11. Задача о поиске наибольшего общего делителя (НОД): Написать программу, которая находит наибольший общий делитель двух целых чисел.

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

Пример кода на Python:

```python

def gcd(a, b):

while b:

a, b = b, a % b

return a

# Пример использования

num1 = 48

num2 = 18

result = gcd(num1, num2)

print(f"Наибольший общий делитель чисел {num1} и {num2}:", result)

```

В этом коде:

– Функция `gcd` принимает два целых числа `a` и `b`.

– В цикле `while` мы выполняем операцию над числами до тех пор, пока `b` не станет равным нулю.

– Внутри цикла `while` происходит обмен значениями `a` и `b`, где `a` принимает значение `b`, а `b` принимает значение остатка от деления `a` на `b`.

– Когда `b` становится равным нулю, цикл завершается, и `a` содержит наибольший общий делитель исходных чисел.

– Этот НОД возвращается функцией и выводится на экран.

Таким образом, данный код эффективно находит наибольший общий делитель двух целых чисел.

12. Задача о пространственном вращении: Реализовать программу для вращения точек в трехмерном пространстве относительно заданной оси и угла.

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

1. Представление точек: Каждая точка в трехмерном пространстве может быть представлена как тройка координат (x, y, z). Мы можем использовать этот формат для хранения и работы с точками.

2. Выбор оси вращения: Пользователь может задать ось вращения. Обычно используются оси X, Y и Z. Для простоты давайте начнем с оси Z.

3. Угол вращения: Пользователь также задает угол вращения в градусах или радианах, в зависимости от предпочтений.

4. Матрица поворота: Для выполнения вращения мы используем матрицу поворота, которая зависит от выбранной оси и угла вращения.

5. Применение вращения к точкам: Для каждой точки применяется матрица поворота, чтобы получить новые координаты точек после вращения.

6. Вывод результатов: Полученные новые координаты точек могут быть выведены на экран или использованы для дальнейших вычислений или отрисовки.

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

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

Пример кода на Python для вращения точек вокруг оси z на заданный угол:

```python

import numpy as np

def rotate_point(point, angle):

# Преобразуем угол в радианы

angle_rad = np.radians(angle)

# Матрица поворота для оси z

rotation_matrix = np.array([[np.cos(angle_rad), -np.sin(angle_rad), 0],

[np.sin(angle_rad), np.cos(angle_rad), 0],

[0, 0, 1]])

# Преобразуем точку в вектор-столбец

point_vector = np.array([[point[0]],

[point[1]],

[point[2]]])

# Выполняем умножение матрицы поворота на вектор точки

rotated_point = np.dot(rotation_matrix, point_vector)

# Возвращаем координаты вращенной точки

return rotated_point[0][0], rotated_point[1][0], rotated_point[2][0]

# Пример использования

point = (1, 0, 0) # Координаты точки (x, y, z)

angle = 90 # Угол в градусах

rotated_point = rotate_point(point, angle)

print("Координаты вращенной точки:", rotated_point)

```

Этот код вращает точку `point` вокруг оси Z на заданный угол `angle`.

– Мы используем функцию `rotate_point`, которая принимает координаты точки и угол вращения.

– Угол преобразуется в радианы.

– Затем создается матрица поворота для оси Z.

– Координаты точки преобразуются в вектор-столбец.

– Мы выполняем умножение матрицы поворота на вектор точки.

– Результатом являются координаты вращенной точки, которые выводятся на экран.

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

13. Задача о максимальной подпоследовательности: Найти наибольшую невозрастающую подпоследовательность в списке чисел.

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

Вот примерный алгоритм решения:

1. Создаем список длиной равной исходному списку чисел, заполненный единицами. Этот список будет содержать длины наибольших невозрастающих подпоследовательностей, заканчивающихся в каждом элементе исходного списка.

2. Проходим по каждому элементу исходного списка и сравниваем его со всеми предыдущими элементами.

3. Если текущий элемент больше или равен предыдущему, длина наибольшей невозрастающей подпоследовательности, заканчивающейся в текущем элементе, будет равна максимальной длине подпоследовательности, заканчивающейся в предыдущем элементе, плюс 1.

4. В конце алгоритма находим максимальное значение в списке длин и восстанавливаем саму подпоследовательность.

Пример кода на Python:

```python

def find_max_non_increasing_subsequence(nums):

n = len(nums)

# Создаем список для хранения длин наибольших невозрастающих подпоследовательностей

lengths = [1] * n

# Заполняем список длин

for i in range(1, n):

for j in range(i):

if nums[i] <= nums[j]:

lengths[i] = max(lengths[i], lengths[j] + 1)

# Находим максимальную длину подпоследовательности

max_length = max(lengths)

# Восстанавливаем саму подпоследовательность

subsequence = []

last_index = lengths.index(max_length)

subsequence.append(nums[last_index])

for i in range(last_index – 1, -1, -1):

if nums[i] >= nums[last_index] and lengths[i] == max_length – 1:

subsequence.append(nums[i])

max_length -= 1

last_index = i

return subsequence[::-1] # Возвращаем подпоследовательность в обратном порядке

# Пример использования

nums = [5, 3, 8, 2, 9, 1, 6]

result = find_max_non_increasing_subsequence(nums)

print("Наибольшая невозрастающая подпоследовательность:", result)

```

Этот код найдет и выведет наибольшую невозрастающую подпоследовательность в списке чисел `[5, 3, 8, 2, 9, 1, 6]`.

Пояснения к коду:

1. Определение функции `find_max_non_increasing_subsequence`:

– Эта функция принимает список чисел `nums` и возвращает наибольшую невозрастающую подпоследовательность этого списка.

2. Создание списка длин подпоследовательностей:

– В начале функции создается список `lengths` длиной, равной длине исходного списка `nums`, заполненный единицами. Этот список будет содержать длины наибольших невозрастающих подпоследовательностей, заканчивающихся в каждом элементе исходного списка.

3. Заполнение списка длин:

– Далее происходит двойной цикл, где для каждого элемента `nums[i]` проверяется, какой максимальной длины может быть наибольшая невозрастающая подпоследовательность, заканчивающаяся в этом элементе. Это делается путем сравнения элемента `nums[i]` с каждым предыдущим элементом `nums[j]` (где `j < i`). Если `nums[i]` больше или равен `nums[j]`, то длина подпоследовательности, заканчивающейся в `nums[i]`, увеличивается на 1.

4. Нахождение максимальной длины:

– После заполнения списка `lengths` находим максимальное значение в этом списке, которое будет длиной наибольшей невозрастающей подпоследовательности.

5. Восстановление подпоследовательности:

– Для восстановления самой подпоследовательности начиная с элемента с максимальной длиной, мы просматриваем элементы списка в обратном порядке, начиная с конечного элемента с максимальной длиной. Мы добавляем элемент в подпоследовательность, если он больше или равен предыдущему элементу и длина подпоследовательности, заканчивающейся в этом элементе, на 1 меньше текущей максимальной длины. Это позволяет нам найти и восстановить исходную подпоследовательность.

6. Возвращение результатов:

– Возвращаем найденную подпоследовательность, которая является наибольшей невозрастающей подпоследовательностью исходного списка `nums`.

14. Задача поиска наибольшей невозрастающей подпоследовательности в массиве чисел, но с ограничением на разницу между элементами этой подпоследовательности.

Например, нам нужно найти наибольшую невозрастающую подпоследовательность, где разница между соседними элементами не превышает заданное число `k`.

Мы можем использовать модифицированный подход динамического программирования для решения этой задачи. Примерный алгоритм:

1. Создаем список длиной равной длине исходного массива чисел, заполненный единицами. Этот список будет содержать длины наибольших невозрастающих подпоследовательностей, заканчивающихся в каждом элементе исходного массива.

2. Проходим по каждому элементу исходного массива и сравниваем его со всеми предыдущими элементами.

3. Если разница между текущим элементом и предыдущим не превышает `k`, то длина наибольшей невозрастающей подпоследовательности, заканчивающейся в текущем элементе, будет равна максимальной длине подпоследовательности, заканчивающейся в предыдущем элементе, плюс 1.

4. В конце алгоритма находим максимальное значение в списке длин и восстанавливаем саму подпоследовательность.

Давайте реализуем этот алгоритм на Python:

```python

def find_max_non_increasing_subsequence_with_limit(nums, k):

n = len(nums)

# Создаем список для хранения длин наибольших невозрастающих подпоследовательностей

lengths = [1] * n

# Заполняем список длин

for i in range(1, n):

for j in range(i):

if nums[i] <= nums[j] and nums[j] – nums[i] <= k:

lengths[i] = max(lengths[i], lengths[j] + 1)

# Находим максимальную длину подпоследовательности

max_length = max(lengths)

# Восстанавливаем саму подпоследовательность

subsequence = []

last_index = lengths.index(max_length)

subsequence.append(nums[last_index])

for i in range(last_index – 1, -1, -1):

if nums[last_index] – nums[i] <= k and lengths[i] == max_length – 1:

subsequence.append(nums[i])

max_length -= 1

last_index = i

return subsequence[::-1] # Возвращаем подпоследовательность в обратном порядке

# Пример использования

nums = [5, 3, 8, 2, 9, 1, 6]

k = 3

result = find_max_non_increasing_subsequence_with_limit(nums, k)

print("Наибольшая невозрастающая подпоследовательность с разницей не более", k, ":", result)

```

Этот код найдет и выведет наибольшую невозрастающую подпоследовательность в списке чисел `[5, 3, 8, 2, 9, 1, 6]`, где разница между соседними элементами не превышает 3.

Работа с текстом и данными

Пояснения к коду:

1. Определение функции `find_max_non_increasing_subsequence_with_limit`:

– Эта функция принимает список чисел `nums` и число `k`, которое ограничивает разницу между соседними элементами подпоследовательности. Она возвращает наибольшую невозрастающую подпоследовательность с разницей между соседними элементами не более `k`.

2. Создание списка длин подпоследовательностей:

– В начале функции создается список `lengths` длиной, равной длине исходного списка `nums`, заполненный единицами. Этот список будет содержать длины наибольших невозрастающих подпоследовательностей, заканчивающихся в каждом элементе исходного списка.

3. Заполнение списка длин:

– Далее происходит двойной цикл, где для каждого элемента `nums[i]` проверяется, какой максимальной длины может быть наибольшая невозрастающая подпоследовательность, заканчивающаяся в этом элементе и удовлетворяющая ограничению на разницу между соседними элементами. Это делается путем сравнения элемента `nums[i]` с каждым предыдущим элементом `nums[j]` (где `j < i`). Если разница между `nums[i]` и `nums[j]` не превышает `k`, и `nums[i]` меньше или равен `nums[j]`, то длина подпоследовательности, заканчивающейся в `nums[i]`, увеличивается на 1.

4. Нахождение максимальной длины:

– После заполнения списка `lengths` находим максимальное значение в этом списке, которое будет длиной наибольшей невозрастающей подпоследовательности с ограничением на разницу между соседними элементами.

5. Восстановление подпоследовательности:

– Для восстановления самой подпоследовательности начиная с элемента с максимальной длиной, мы просматриваем элементы списка в обратном порядке, начиная с конечного элемента с максимальной длиной. Мы добавляем элемент в подпоследовательность, если разница между текущим элементом и последним добавленным не превышает `k`, и длина подпоследовательности, заканчивающейся в этом элементе, на 1 меньше текущей максимальной длины. Это позволяет нам найти и восстановить исходную подпоследовательность.

6. Возвращение результатов:

– Возвращаем найденную подпоследовательность, которая является наибольшей невозрастающей подпоследовательностью с ограничением на разницу между соседними элементами.

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

Для генерации случайных паролей с заданными требованиями к сложности, такими как длина пароля, использование различных типов символов (буквы верхнего и нижнего регистра, цифры, специальные символы), мы можем создать программу на Python, используя модуль `random` для генерации случайных символов.

Пример реализации программы для генерации паролей:

```python

import random

import string

def generate_password(length, uppercase=True, lowercase=True, digits=True, special_chars=True):

# Определяем символьные наборы для пароля

chars = ''

if uppercase:

chars += string.ascii_uppercase

if lowercase:

chars += string.ascii_lowercase

if digits:

chars += string.digits

if special_chars:

chars += string.punctuation

# Генерируем пароль из символов заданной длины

password = ''.join(random.choice(chars) for _ in range(length))

return password

# Пример использования

length = 12

password = generate_password(length)

print("Сгенерированный пароль:", password)

```

Этот код генерирует случайный пароль с заданной длиной `length` и заданными требованиями к сложности. Функция `generate_password` принимает следующие аргументы: