Алгоритмы языка программирования питон

Основные алгоритмы и их реализация на Python

Аннотация: При разборе задач в этой части будем обращать внимание на постановку задачи (что именно нужно сделать) и собственно алгоритм, который будет описываться как блок-схемой, так и на «псевдоязыке» программирования (подобие «школьного алгоритмического языка»). И только после этого можно приступать к написанию программы на Python с учётом всех тех его особенностей и возможностей, которые были описаны в предыдущей части.

2.1 Линейные алгоритмы. Операции с числами и строками

Линейный алгоритм — алгоритм, в котором вычисления выполняются строго последовательно. Типичная блок-схема линейного алгоритма показана на рис. 2.1.

Далее рассмотрим типичные задачи с линейной структурой алгоритма.

Задача 1. Дано два числа a и b . Сделать так, чтобы их значения поменялись местами.

Постановка задачи: Имеются две переменные с какими-то определёнными значениями. Пусть значение a равно x , а значение b равно y . Требуется, чтобы значение a стало равно y , а значение b стало равно x .

Метод решения (общий): Использовать дополнительную переменную c , в которую временно записать начальное значение переменной a , присвоить переменной a значение переменной b , а потом переменной b присвоить значение переменной c .

Блок-схема такого алгоритма показана на рис. 2.2.

Текст программы на «псевдоязыке»:

ввод a, b c=a a=b b=c вывод a, b

Метод решения с использованием особенностей Python: использовать два кортежа. В первом будут определены переменные a и b и их значения, а второй сформируем из этих же переменных, но в обратном порядке.

Текст программы на Python:

# Перестановка местами двух чисел с использованием кортежа

(a, b)=input(‘Введите исходные значения (a, b) через запятую: ‘)

print ‘Новое значение а: ‘, a, ‘\n’, ‘Новое значение b: ‘, b

Как описано в разделе 1.4.2, комбинация ‘\n’ означает директиву на перевод строки для команды print.

Задача 2. Известны оклад (зарплата) и ставка процента подоходного налога. Определить размер подоходного налога и сумму, получаемую на руки.

Постановка задачи: Исходными данными являются величина оклада (переменная oklad , выражаемая числом) и ставка подоходного налога (переменная procent, выражаемая числом). Размер налога (переменная nalog ) определяется как oklad*procent/100 , а сумма, получаемая на руки (переменная summa) — как oklad-nalog .

Блок-схема алгоритма показана на рис. 2.3.

Текст программы на «псевдоязыке»:

ввод oklad, procent nalog=oklad * procent /100 summa=oklad-nalog вывод summa, nalog

print «Сумма на руки: «, summa

Если все числа в этом примере использовать как целые, то результат может получиться неверным. Поэтому при вычислении налога используется преобразование числителя из целого числа в вещественное (функция float() ).

Задача 3. Используя данные таблицы определить общую стоимость обеда в столовой. Определить, во сколько раз возрастёт стоимость обеда, если цена котлеты увеличится вдвое. 1 Источник: В.А.Молодцов, Н.Б.Рыжикова. Информатика: тесты, задания, лучшие методики. Ростов-на-Дону: Феникс, 2009.

Постановка задачи (формализованная): Имеется четыре числа, которые требуется просуммировать (обозначим их переменными a, b, c и d соответственно). Сумму их значений обозначим S1 . Требуется найти также величину S2=S1+b и определить отношение S2/S1 (обозначим это отношение переменной res ). В результате нужно вывести значения переменных S1 и res .

Текст программы на «псевдоязыке»:

ввод a, b, c, d S1=a, b, c, d S2=S1+b res=S2/S1 вывод S1, res

В программе на Python разумно будет использовать кортеж:

t=(a, b, c, d)=input(‘Введите значения через запятую: ‘)

print ‘Начальная_стоимость : ‘, S1, ‘ \n ‘, ‘Увеличение, _раз : ‘, res

И снова для преобразования целого числа в вещественное использована функция float() . (Полезно сравнить результат, получаемый при использвании выражения res=float(S2)/S1 и выражения res=float(S2/S1) ).

Задача 4. Преобразовать дату в «компьютерном» представлении (системную дату) в «российский» формат, т. е. день/месяц/год (например, 17/05/2009).

Постановка задачи: Системная дата имеет вид 2009-06-15. Нужно преобразовать это значение в строку, строку разделить на компоненты (символразделитель — дефис), потом из этих компонентов сконструировать нужную строку.

Сразу перейдём к программе на Python. Функциями работы с датами и временем в Python «заведует» модуль datetime , а непосредственно для работы с датами используется объект date и его методы.

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

Источник

Алгоритмы и структуры данных на Python

Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) | Алгоритмы на Python

t = "лилила" p = [0]*len(t) j = 0 i = 1 while i < len(t): if t[j] == t[i]: p[i] = j+1 i += 1 j += 1 else: if j == 0: p[i] = 0; i += 1 else: j = p[j-1] print(p) a = "лилилось лилилась" m = len(t) n = len(a) i = 0 j = 0 while i < n: if a[i] == t[j]: i += 1 j += 1 if j == m: print("образ найден") break else: if j >0: j = p[j-1] else: i += 1 if i == n and j != m: print("образ не найден")

Алгоритм Бойера-Мура-Хорспула | Алгоритмы на Python

t = "данные" # Этап 1: формирование таблицы смещений S = set() # уникальные символы в образе M = len(t) # число символов в образе d = <> # словарь смещений for i in range(M-2, -1, -1): # итерации с предпоследнего символа if t[i] not in S: # если символ еще не добавлен в таблицу d[t[i]] = M-i-1 S.add(t[i]) if t[M-1] not in S: # отдельно формируем последний символ d[t[M-1]] = M d['*'] = M # смещения для прочих символов print(d) # Этап 2: поиск образа в строке a = "метеоданные" N = len(a) if N >= M: i = M-1 # счетчик проверяемого символа в строке while(i < N): k = 0 j = 0 flBreak = False for j in range(M-1, -1, -1): if a[i-k] != t[j]: if j == M-1: off = d[a[i]] if d.get(a[i], False) else d['*'] # смещение, если не равен последний символ образа else: off = d[t[j]] # смещение, если не равен не последний символ образа i += off # смещение счетчика строки flBreak = True # если несовпадение символа, то flBreak = True break k += 1 # смещение для сравниваемого символа в строке if not flBreak: # если дошли до начала образа, значит, все его символы совпали print(f"образ найден по индексу ") break else: print("образ не найден") else: print("образ не найден")

Алгоритм Дейкстры (Dijkstra’s algorithm) | Алгоритмы на Python

import math def arg_min(T, S): amin = -1 m = math.inf # максимальное значение for i, t in enumerate(T): if t < m and i not in S: m = t amin = i return amin D = ((0, 3, 1, 3, math.inf, math.inf), (3, 0, 4, math.inf, math.inf, math.inf), (1, 4, 0, math.inf, 7, 5), (3, math.inf, math.inf, 0, math.inf, 2), (math.inf, math.inf, 7, math.inf, 0, 4), (math.inf, math.inf, 5, 2, 4, 0)) N = len(D) # число вершин в графе T = [math.inf]*N # последняя строка таблицы v = 0 # стартовая вершина (нумерация с нуля) S = # просмотренные вершины T[v] = 0 # нулевой вес для стартовой вершины M = [0]*N # оптимальные связи между вершинами while v != -1: # цикл, пока не просмотрим все вершины for j, dw in enumerate(D[v]): # перебираем все связанные вершины с вершиной v if j not in S: # если вершина еще не просмотрена w = T[v] + dw if w < T[j]: T[j] = w M[j] = v # связываем вершину j с вершиной v v = arg_min(T, S) # выбираем следующий узел с наименьшим весом if v >= 0: # выбрана очередная вершина S.add(v) # добавляем новую вершину в рассмотрение #print(T, M, sep="\n") # формирование оптимального маршрута: start = 0 end = 4 P = [end] while end != start: end = M[P[-1]] P.append(end) print(P)

Алгоритм Флойда (Floyd’s algorithm) | Алгоритмы на Python

import math def get_path(P, u, v): path = [u] while u != v: u = P[u][v] path.append(u) return path V = [[0, 2, math.inf, 3, 1, math.inf, math.inf, 10], [2, 0, 4, math.inf, math.inf, math.inf, math.inf, math.inf], [math.inf, 4, 0, math.inf, math.inf, math.inf, math.inf, 3], [3, math.inf, math.inf, 0, math.inf, math.inf, math.inf, 8], [1, math.inf, math.inf, math.inf, 0, 2, math.inf, math.inf], [math.inf, math.inf, math.inf, math.inf, 2, 0, 3, math.inf], [math.inf, math.inf, math.inf, math.inf, math.inf, 3, 0, 1], [10, math.inf, 3, 8, math.inf, math.inf, 1, 0], ] N = len(V) # число вершин в графе P = [[v for v in range(N)] for u in range(N)] # начальный список предыдущих вершин для поиска кратчайших маршрутов for k in range(N): for i in range(N): for j in range(N): d = V[i][k] + V[k][j] if V[i][j] > d: V[i][j] = d P[i][j] = k # номер промежуточной вершины при движении от i к j # нумерацця вершин начинается с нуля start = 1 end = 4 print(get_path(P, end, start))

Алгоритм Форда-Фалкерсона | Алгоритмы на Python

import math def get_max_vertex(k, V, S): m = 0 # наименьшее допустимое значение v = -1 for i, w in enumerate(V[k]): if i in S: continue if w[2] == 1: # движение по стрелке if m < w[0]: m = w[0] v = i else: # движение против стрелки if m < w[1]: m = w[1] v = i return v def get_max_flow(T): w = [x[0] for x in T] return min(*w) def updateV(V, T, f): for t in T: if t[1] == -1: # это исток continue sgn = V[t[2]][t[1]][2] # направление движения # меняем веса в таблице для (i,j) и (j,i) V[t[1]][t[2]][0] -= f * sgn V[t[1]][t[2]][1] += f * sgn V[t[2]][t[1]][0] -= f * sgn V[t[2]][t[1]][1] += f * sgn V = [[[0,0,1], [20,0,1], [30,0,1], [10,0,1], [0,0,1]], [[20,0,-1], [0,0,1], [40,0,1], [0,0,1], [30,0,1]], [[30,0,-1], [40,0,-1], [0,0,1], [10,0,1], [20,0,1]], [[10,0,-1], [0,0,1], [10,0,-1], [0,0,1], [20,0,1]], [[0,0,1], [30,0,-1], [20,0,-1], [20,0,-1], [0,0,1]], ] N = len(V) # число вершин в графе init = 0 # вершина истока (нумерация с нуля) end = 4 # вершина стока Tinit = (math.inf, -1, init) # первая метка маршруто (a, from, vertex) f = [] # максимальные потоки найденных маршрутов j = init while j != -1: k = init # стартовая вершина (нумерация с нуля) T = [Tinit] # метки маршрута S = # множество просмотренных вершин while k != end: # пока не дошли до стока j = get_max_vertex(k, V, S) # выбираем вершину с наибольшей пропускной способностью if j == -1: # если следующих вершин нет if k == init: # и мы на истоке, то break # завершаем поиск маршрутов else: # иначе, переходим к предыдущей вершине k = T.pop()[2] continue c = V[k][j][0] if V[k][j][2] == 1 else V[k][j][1] # определяем текущий поток T.append((c, j, k)) # добавляем метку маршрута S.add(j) # запоминаем вершину как просмотренную if j == end: # если дошди до стока f.append(get_max_flow(T)) # находим максимальную пропускную способность маршрута updateV(V, T, f[-1]) # обновляем веса дуг break k = j F = sum(f) print(f"Максимальный поток равен: ")

Алгоритм Краскала (Kruskal’s algorithm) | Алгоритмы на Python

#------------------------------------------------- # Алгоритм Краскала поиска минимального остова графа #------------------------------------------------- # список ребер графа (длина, вершина 1, вершина 2) R = [(13, 1, 2), (18, 1, 3), (17, 1, 4), (14, 1, 5), (22, 1, 6), (26, 2, 3), (22, 2, 5), (3, 3, 4), (19, 4, 6)] Rs = sorted(R, key=lambda x: x[0]) U = set() # список соединенных вершин D = <> # словарь списка изолированных групп вершин T = [] # список ребер остова for r in Rs: if r[1] not in U or r[2] not in U: # проверка для исключения циклов в остове if r[1] not in U and r[2] not in U: # если обе вершины не соединены, то D[r[1]] = [r[1], r[2]] # формируем в словаре ключ с номерами вершин D[r[2]] = D[r[1]] # и связываем их с одним и тем же списком вершин else: # иначе if not D.get(r[1]): # если в словаре нет первой вершины, то D[r[2]].append(r[1]) # добавляем в список первую вершину D[r[1]] = D[r[2]] # и добавляем ключ с номером первой вершины else: D[r[1]].append(r[2]) # иначе, все то же самое делаем со второй вершиной D[r[2]] = D[r[1]] T.append(r) # добавляем ребро в остов U.add(r[1]) # добавляем вершины в множество U U.add(r[2]) for r in Rs: # проходим по ребрам второй раз и объединяем разрозненные группы вершин if r[2] not in D[r[1]]: # если вершины принадлежат разным группам, то объединяем T.append(r) # добавляем ребро в остов gr1 = D[r[1]] D[r[1]] += D[r[2]] # объединем списки двух групп вершин D[r[2]] += gr1 print(T)

Алгоритм Прима (ближайшего соседа) | Алгоритмы на Python

#------------------------------------------------- # Алгоритм Прима поиска минимального остова графа #------------------------------------------------- import math def get_min(R, U): rm = (math.inf, -1, -1) for v in U: rr = min(R, key=lambda x: x[0] if (x[1] == v or x[2] == v) and (x[1] not in U or x[2] not in U) else math.inf) if rm[0] > rr[0]: rm = rr return rm # список ребер графа (длина, вершина 1, вершина 2) # первое значение возвращается, если нет минимальных ребер R = [(math.inf, -1, -1), (13, 1, 2), (18, 1, 3), (17, 1, 4), (14, 1, 5), (22, 1, 6), (26, 2, 3), (19, 2, 5), (30, 3, 4), (22, 4, 6)] N = 6 # число вершин в графе U = # множество соединенных вершин T = [] # список ребер остова while len(U) < N: r = get_min(R, U) # ребро с минимальным весом if r[0] == math.inf: # если ребер нет, то остов построен break T.append(r) # добавляем ребро в остов U.add(r[1]) # добавляем вершины в множество U U.add(r[2]) print(T)

Сортировка выбором | Алгоритмы на Python

#------------------------------------------------- # Алгоритм сортировки выбором #------------------------------------------------- a = [-3, 5, 0, -8, 1, 10] N = len(a) # число элементов в списке for i in range(N-1): m = a[i] # запоминаем минимальное значение p = i # запоминаем индекс минимального значения for j in range(i+1, N): # поиск миимального среди оставшихся элементов if m > a[j]: m = a[j] p = j if p != i: # обмен значениями, если был найден минимальный не в i-й позиции t = a[i] a[i] = a[p] a[p] = t print(a)

Сортировка вставками | Алгоритмы на Python

#------------------------------------------------- # Алгоритм сортировки вставками #------------------------------------------------- a = [-3, 5, 0, -8, 1, 10] N = len(a) # число элементов в списке for i in range(1, N): for j in range(i, 0, -1): if a[j] < a[j-1]: a[j], a[j-1] = a[j-1], a[j] else: break print(a)

Сортировка пузырьком (метод всплывающего пузырька) | Алгоритмы на Python

#------------------------------------------------- # Алгоритм сортировки пузырьком #------------------------------------------------- a = [7, 5, -8, 0, 10, 1] N = len(a) # число элементов в списке for i in range(0, N-1): # N-1 итераций работы алгоритма for j in range(0, N-1-i): # проход по оставшимся не отсортированным парам массива if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] print(a)

Слияние двух упорядоченных списков | Алгоритмы на Python

#------------------------------------------------- # Метод слияния двух списков #------------------------------------------------- a = [1, 4, 10, 11] b = [2, 3, 3, 4, 8] c = [] N = len(a) M = len(b) i = 0 j = 0 while i < N and j < M: if a[i] 
Быстрая сортировка слиянием (merge sort) | Алгоритмы на Python

#------------------------------------------------- # Сортировка слиянием #------------------------------------------------- # функция слияния двух отсортированных списков def merge_list(a, b): c = [] N = len(a) M = len(b) i = 0 j = 0 while i < N and j < M: if a[i] 1: # если длина 1-го списка больше 1, то делим дальше a1 = split_and_merge_list(a1) if len(a2) > 1: # если длина 2-го списка больше 1, то делим дальше a2 = split_and_merge_list(a2) return merge_list(a1, a2) # слияние двух отсортированных списков в один a = [9, 5, -3, 4, 7, 8, -8] a = split_and_merge_list(a) print(a)
 
Быстрая сортировка Хоара | Алгоритмы на Python
 
 
#------------------------------------------------- # Быстрая сортировка Хоара через рекурсию #------------------------------------------------- import random def quick_sort(a): if len(a) > 1: x = a[random.randint(0, len(a)-1)] # случайное пороговое значение (для разделения на малые и большие) low = [u for u in a if u < x] eq = [u for u in a if u == x] hi = [u for u in a if u >x] a = quick_sort(low) + eq + quick_sort(hi) return a a = [9, 5, -3, 4, 7, 8, -8] a = quick_sort(a) print(a)
 
Стек типа LIFO (Last-In-First-Out) | Алгоритмы на Python
 
 
# Пример использования стека типа LIFO a = input("Введите строку: ") stack = [] flVerify = True for lt in a: if lt in "([": if len(stack) == 0: flVerify = False break br = stack.pop() if br == '(' and lt == ')': continue if br == '[' and lt == ']': continue if br == '': continue flVerify = False break if flVerify and len(stack) == 0: # стек по итогам проверок должен быть пустым print("Yes") else: print("No")
 
Делаем очередь (queue) | Алгоритмы на Python
 
 
Возможно вам будет интересно:
 
Источник