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

Алгоритмы и структуры данных на Python. (Бакалавриват). Учебное пособие.

Гриф: Рекомендовано Экспертным советом УМО в системе ВО и СПО в качестве учебного пособия для направлений подготовки бакалавриата укрупненных групп «Информатика и вычислительная техника» и «Компьютерные и информационные науки»

Знакомит обучающихся с базовыми алгоритмами, структурами данных и способами их реализации на языке программирования Python. Код написан с использованием аннотации типов (type hints) в соответствии с руководством по стилю написания кода на Python – PEP8 (Style Guide for Python Code), а код самих структур — с использованием обобщенного программирования (generic, дженериков). Материал подается по принципу «от простого к сложному» и сопровождается большим количеством примеров и упражнений, что позволяет сформировать практические навыки программирования и тестирования. Все исходные коды рассматриваемых примеров можно скачать с репозитория автора на GitHub.
Соответствует ФГОС ВО последнего поколения.
Для студентов высших учебных заведений, обучающихся по инженерно-техническим направлениям.

Программирование. СУБД

Основы проектирования баз данных. (СПО). Учебник.

Фасет-ориентированная модель данных. Концепция, исполнение, применение. (Бакалавриат). Монография.

Алгоритмы и структуры данных на языке GO. (Бакалавриат). Учебник.

Программирование на языке GO. (Бакалавриат). Учебник.

Алгоритмы и структуры данных на Python. (Бакалавриват). Учебное пособие.

Программирование в Интернете вещей. (Бакалавриат). Учебное пособие.

Практикум по нейропакетам. (Бакалавриат, Магистратура). Монография.

Вычислительные нанотехнологии. (Бакалавриат). Учебное пособие.

Программирование, численные методы и математическое моделирование. (Бакалавриат). Учебное пособие.

Теоретические основы разработки и реализации языков программирования. (Бакалавриат, Магистратура).

Программные решения для бизнеса. Рекомендации по выполнению демонстрационного экзамена +.

Анализ больших данных. (Бакалавриат). Учебное пособие.

Введение в язык Pascal. (Бакалавриат). Учебное пособие.

Проектирование и разработка интерфейсов пользователя. (СПО). Учебное пособие.

Вычислительные и экспериментальные методы научного эксперимента. (Бакалавриат, Специалитет).

Источник

Алгоритмы и структуры данных на Python. (Бакалавриват). Учебное пособие.

Также данная книга доступна ещё в библиотеке. Запишись сразу в несколько библиотек и получай книги намного быстрее.

Посоветуйте книгу друзьям! Друзьям – скидка 10%, вам – рубли

По вашей ссылке друзья получат скидку 10% на эту книгу, а вы будете получать 10% от стоимости их покупок на свой счет ЛитРес. Подробнее

По абонементу вы каждый месяц можете взять из каталога одну книгу до 700 ₽ и две книги из специальной подборки. Узнать больше

Знакомит обучающихся с базовыми алгоритмами, структурами данных и способами их реализации на языке программирования Python. Код написан с использованием аннотации типов (type hints) в соответствии с руководством по стилю написания кода на Python – PEP8 (Style Guide for Python Code), а код самих структур — с использованием обобщенного программирования (generic, дженериков). Материал подается по принципу «от простого к сложному» и сопровождается большим количеством примеров и упражнений, что позволяет сформировать практические навыки программирования и тестирования. Все исходные коды рассматриваемых примеров можно скачать с репозитория автора на GitHub. Соответствует ФГОС ВО последнего поколения. Для студентов высших учебных заведений, обучающихся по инженерно-техническим направлениям.

Возрастное ограничение: 0+ Дата выхода на ЛитРес: 01 апреля 2023 Дата написания: 2024 Объем: 326 стр.

ISBN: 9785406116838 Общий размер: 4 MB Общее кол-во страниц: 326 Размер страницы: Правообладатель: КноРус

«Алгоритмы и структуры данных на Python. (Бакалавриват). Учебное пособие.» — читать онлайн бесплатно фрагмент книги. Оставляйте комментарии и отзывы, голосуйте за понравившиеся.

Источник

Алгоритмы и структуры данных на 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
 
 
Возможно вам будет интересно:
 
Источник