Алгоритми в Python

Алгоритми в Python – це структуровані набори інструкцій, які виконують певні завдання або розв’язують конкретні проблеми. Вони є основою для розв’язання різноманітних задач у програмуванні. В Python ви можете реалізувати широкий спектр алгоритмів для сортування, пошуку, обробки даних та інших задач. Давайте розглянемо кілька базових алгоритмів і їх реалізацію в Python.

1. Сортування списку: Алгоритм сортування бульбашкою

Сортування бульбашкою є простим алгоритмом сортування, який порівнює сусідні елементи і переставляє їх, якщо вони не відсортовані.

def bubble_sort(arr):
n = len(arr)
for i in range(n – 1):
for j in range(0, n – i – 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Приклад використання:
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(“Відсортований масив:”, arr)

2. Пошук елемента в списку: Алгоритм лінійного пошуку

Лінійний пошук перевіряє кожен елемент списку послідовно до тих пір, поки не знайде шуканий елемент.

def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Повертаємо індекс знайденого елемента
return -1 # Якщо елемент не знайдено

# Приклад використання:
arr = [64, 34, 25, 12, 22, 11, 90]
target = 25
result = linear_search(arr, target)
if result != -1:
print(f”Елемент {target} знайдено на позиції {result}.”)
else:
print(f”Елемент {target} не знайдено в списку.”)

3. Обхід графа: Пошук в ширину (Breadth-First Search, BFS)

Пошук в ширину використовується для обходу або пошуку у графі або дереві, рухаючись спочатку до всіх сусідніх вершин поточної вершини, а потім до наступного рівня.

from collections import deque

def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node, end=’ ‘)
queue.extend(graph[node] – visited)

# Приклад використання:
graph = {
‘A’: {‘B’, ‘C’},
‘B’: {‘A’, ‘D’, ‘E’},
‘C’: {‘A’, ‘F’},
‘D’: {‘B’},
‘E’: {‘B’, ‘F’},
‘F’: {‘C’, ‘E’}
}
print(“Результат обходу в ширину (BFS) з вершини A:”)
bfs(graph, ‘A’)

4. Пошук найменшого шляху: Алгоритм Дейкстри

Алгоритм Дейкстри знаходить найкоротший шлях від однієї вершини графа до всіх інших, коли всі ребра мають додатні ваги.

import heapq

def dijkstra(graph, start):
distances = {vertex: float(‘infinity’) for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)

if current_distance > distances[current_vertex]:
continue

for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight

if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return distances

# Приклад використання:
graph = {
‘A’: {‘B’: 1, ‘C’: 4},
‘B’: {‘A’: 1, ‘C’: 2, ‘D’: 5},
‘C’: {‘A’: 4, ‘B’: 2, ‘D’: 1},
‘D’: {‘B’: 5, ‘C’: 1}
}
start_vertex = ‘A’
distances = dijkstra(graph, start_vertex)
print(f”Найкоротші відстані від вершини {start_vertex}:”)
for vertex, distance in distances.items():
print(f”Від {start_vertex} до {vertex}: {distance}”)

Знання алгоритмів дозволить вам ефективно розв’язувати різноманітні завдання і задачі програмування, включаючи розробку програмного забезпечення і роботу з великими обсягами даних.