Учусь - Делюсь - Python

Рекурсия в Python на практике. Ханойская башня. Ханойская башня — это математическая головоломка, в которой используются три стержня и n дисков. Цель головоломки — переместить всю стопку дисков на другой стержень, следуя простым правилам: Можно перемещать только один диск одновременно. Перемещение состоит в том, чтобы взять верхний диск из одной стопки и положить его поверх другой стопки. То есть диск можно перемещать только если он находится на вершине стопки. Диск нельзя положить поверх диска меньшего размера. Важно учесть, что перенос n-1 верхних дисков с исходного стержня на вспомогательный стержень также рассматривается как новая проблема, которую можно решить тем же способом. # Рекурсивная функция Python для решения задачи о ханойской башне def    Hanoi(n, begincol, endcol, helpcol):       if   n>0:           Hanoi(n-1, begincol, helpcol, endcol)           ...

Полный перебор (перестановка) m чисел в n системе. Пример: n=5 m=3. 000 001 002 003 010 011 012 013 020 021 ... 331 332 333 ... 440 441 442 443 444 Решаем алгоритм рекурсивно. На каждом шаге рекурсии в цикле перебираем одну позицию и формируем начало списка. Уходим на новую рекурсию. # Функция перебора def peres(n:int,m:int,prefix=[]): """ Функция делает полный перебор чисел у которых m разрядов (позиций) и оно в n-ой системе (от 0 до n-1). prefix уже сформированная часть списка (начало)"""      # Выход из рекурсии      if  m==0:           print(prefix,end=" ")           return None      # перебор вариантов      # добавляем в список элемент      # уходим на новую рекурсию      # убираем его чтобы добавить другой      # на новой ит...

Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании. Бинарный поиск — это эффективный алгоритм поиска значения в отсортированном массиве. Он работает следующим образом: Отсортируйте массив. Выберите опорную точку (середину) массива. Сравните значение искомого элемента с опорной точкой. Если они равны, то поиск завершён, иначе перейдите к следующему шагу. Если искомый элемент меньше опорной точки, исключите правую часть массива и повторите шаг 3 для левой части массива. Если искомый элемент больше опорной точки, исключите левую часть массива и повторите шаг 3 для правой части массива. Этот алгоритм имеет среднюю временную сложность O(logn), где n — количество элементов в массиве Дополнительный материал: Сортировка массива методом пуз...

Что такое двоичная система? Двоичная система счисления — это позиционная система счисления с основанием 2. Она используется в цифровых электронных устройствах, таких как компьютеры и смартфоны, благодаря своей простоте и возможности непосредственной реализации в логических операциях. Алгоритм перевода числа из десятичной системы в двоичную: Последовательно делить число на 2, записывая результат деления и остаток в виде целого числа. Продолжать деление до тех пор, пока в остатке не останется 1. Итоговое двоичное число формируется путём последовательной записи результата последнего деления и остатков всех делений в обратном порядке. Программа: # Перевод любого целого положительного числа # из десятичной системы в двоичную def bin_number(x:int):     if x<2:        tmp=[x]        return str(tmp[0])      # для случаев 0 и 1     # ищем в цикле остальные бинарные цифры     Listnumber="" ...

Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел. Одно из наиболее частых применений HOK — приведение дробей к общему знаменателю. Программа # Функция поиска наименьшего общего кратного НОК def find_nok(x, y:int):        # НОКом может быть максимальное из двух чисел       if   x > y:           tmp_nok = x       else:           tmp_nok = y        # Ищем НОК обычным перебором от максимального и далее...       while (True):             if ((tmp_nok % x == 0) and(tmp_nok % y == 0)):                  ...

Проверка на простое число в Python. Проверка на простое число часто используется в математических задачах и программировании. Простое число — это число, которое делится только на 1 и на самого себя. Программа  # Функция принимает на вход число и проверяет, простое оно или нет. def prostoeN(N:int):     # Выкидываем четные     if (N % 2 == 0):          return False;     # если найден хотя бы один делитель возвращаем False (Ложь)     for i in range(3, (N//2)+1,2):         # проверяем, делится ли наше число без остатка на         # числа из выбранного диапазона цикла (только не четные)         if (N % i == 0):             return False;     return True # Тестируем программу def    test():      # если функция prostoeN вернет     # Истину напишем "Да", а Ложь напи...

НОД — это наибольший общий делитель. Наибольший общий делитель чисел a и b — это наибольшее число, на которое делятся числа a и b без остатка. Найти наибольший общий делитель двух чисел можно разными способами. Сегодня один из них! Простой! Программа # Нахождение НОД (наибольший общий делитель) для  А и Б больше нуля. # При нуле одного второй автоматически становится НОДом. def nod(a,b:int):     # Оба параметра нули.     if ((a==0) and (b==0)):         print('Oшибка параметров! Числа равны нулю!')         return None     # Параметры функции должны быть положительными     if ((a<0) or (b<0)):         print('Oшибка параметров! Один или оба отрицательны!')         return None     # Один из параметров равен нулю, тогда второй и есть НОД.     if a==0:         return b     if b==0:       ...

В данной статье мы рассмотрим сортировку методом вставки, реализованную на языке Python. Еще статья: Сортировка массива методом пузырька на Python Еще статья: Сортировка массива методом выбора на Python Описание алгоритма: Сортировка вставками — это алгоритм сортировки, при котором массив обрабатывается пошагово, начиная с первого элемента. На каждом шаге выбирается текущий элемент и перемещается в нужную позицию в уже отсортированной части массива. Суть сортировки: 1. Перебираются элементы в неотсортированной части массива. 2. Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться.  # Функция сортировки массива методом вставки def sort_insertion(massiv):          for i in range(1, len(massiv)):                  tmp = massiv[i]         j = i         while j > 0 and massiv[j - 1]  < tmp:   ...

В данной статье мы рассмотрим сортировку методом выбора, реализованную на языке Python. Еще статья: Сортировка массива методом пузырька на Python Еще статья: Сортировка массива методом вставки на Python Описание алгоритма: Один из самых простых методов сортировки — сортировка выбором. Этот метод предполагает выбор максимального или минимального элемента массива, в зависимости от требуемой сортировки (по возрастанию или по убыванию).Если требуется отсортировать массив по возрастанию, то из исходного массива выбираются минимальные элементы. Если же сортировка должна быть выполнена по убыванию, то выбираются максимальные элементы.Например, если нужно отсортировать массив по возрастанию, то в исходном массиве находим минимальный элемент и меняем его с первым элементом массива. Затем рассматриваем неотсортированную часть массива, выбираем минимальный элемент и меняем его со вторым элементом и так далее. # Функция сортировки массива методом выбора def sort_choise(massiv): ...

В данной статье мы рассмотрим сортировку методом пузырька, реализованную на языке Python. Еще статья: Сортировка массива методом выбора на Python Еще статья: Сортировка массива методом вставки на Python Описание алгоритма: Суть этой сортировки заключается в парном сравнении соседних элементов, начиная с нулевого элемента в массиве. В конце первой итерации наибольший элемент оказывается в конце массива, и в последующих итерациях мы его больше не сравниваем с другими элементами (то есть будет проведено n - 1 сравнений). Затем аналогичным образом мы находим второй по величине элемент и помещаем его на предпоследнее место, и так далее. В итоге после всех итераций наименьший элемент окажется на нулевом месте, а наибольший — на последнем. Таким образом, элементы как бы «всплывают» от большего к меньшему.Обратите внимание, что можно также реализовать сортировку от меньшего к большему. В коде это достигается заменой знака «>» на «<» в коде (более подробно см. в примечании ниже). ...