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

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

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

Код:

```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. Задача о поиске наибольшего общего делителя (НОД): Написать программу, которая находит наибольший общий делитель двух целых чисел.