Сообщения

Программа на Python для Ханойской башни

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

Перебор (перестановка) чисел на Pyton

Изображение
Полный перебор (перестановка) 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 — количество элементов в массиве Дополнительный материал: Сортировка массива методом пуз...

Перевод числа из десятичной системы в двоичную (бинарную) на Python

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

Нахождение НОК (наименьшее общее кратное) в Python

Изображение
Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел. Одно из наиболее частых применений 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)):                  ...

Поиск простых чисел в диапазоне от 1 до 100

Изображение
Проверка на простое число в 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 вернет     # Истину напишем "Да", а Ложь напи...

Как найти наибольший общий делитель (НОД) в Python

Изображение
НОД — это наибольший общий делитель. Наибольший общий делитель чисел 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:       ...