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

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` принимает следующие аргументы:

– `length`: длина пароля;

– `uppercase`, `lowercase`, `digits`, `special_chars`: булевы значения, указывающие, нужно ли включать в пароль буквы верхнего и нижнего регистра, цифры и специальные символы соответственно.

Внутри функции используется модуль `random` для выбора случайных символов из символьных наборов, сформированных на основе требований к паролю. Функция `string.ascii_uppercase` возвращает все буквы верхнего регистра, `string.ascii_lowercase` – все буквы нижнего регистра, `string.digits` – все цифры, а `string.punctuation` – все специальные символы.

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

16. Задача с шахматной доской: Определить, можно ли покрыть шахматную доску доминошками размером 2x1.

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

Шахматная доска имеет размер 8x8 и состоит из 64 клеток. Каждая клетка имеет размер 1x1.

Доминошки имеют размер 2x1. Это означает, что каждая доминошка занимает две смежные клетки доски вдоль одной из сторон.

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

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

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

```python

def can_cover_chessboard():

rows = 8

cols = 8

total_cells = rows * cols

return total_cells % 2 == 0

# Проверяем возможность покрытия шахматной доски доминошками

if can_cover_chessboard():

print("Шахматную доску можно покрыть доминошками.")

else:

print("Шахматную доску нельзя покрыть доминошками.")

```

Этот код определит, можно ли покрыть шахматную доску доминошками размером 2x1 или нет, и выведет соответствующее сообщение.

17. Задача о работе с текстом: подсчет количества слов в тексте и вывод наиболее часто встречающихся слов.

Идея решения будет следующей:

1. Разделить текст на отдельные слова (токенизация).

2. Привести слова к нижнему регистру для учета слов с разным регистром как одинаковых.

3. Удалить стоп-слова (если требуется).

4. Подсчитать количество упоминаний каждого слова.

5. Вывести наиболее часто встречающиеся слова.

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

```python

from collections import Counter

import re

import string

def count_words(text):

# Привести текст к нижнему регистру

text = text.lower()

# Удалить знаки пунктуации

text = text.translate(str.maketrans('', '', string.punctuation))

# Разделить текст на слова

words = re.findall(r'\b\w+\b', text)

return Counter(words)

def most_common_words(counter, n=10):

return counter.most_common(n)

# Пример текста