Dưới đây là 10 bài tập Python liên quan đến thuật toán phổ biến như tìm kiếm, sắp xếp, đồ thị, và lập trình động.
Bài 71: Tìm kiếm nhị phân
Đề bài: Nhập vào một danh sách số nguyên đã được sắp xếp, sau đó nhập vào một số x, kiểm tra xem x có tồn tại trong danh sách không bằng thuật toán tìm kiếm nhị phân.
Giải:
def binary_search(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
lst = sorted(map(int, input("Nhập danh sách số nguyên: ").split()))
x = int(input("Nhập số cần tìm: "))
index = binary_search(lst, x)
print(f"{x} có trong danh sách tại vị trí {index}" if index != -1 else f"{x} không có trong danh sách")
Bài 72: Thuật toán sắp xếp nhanh (QuickSort)
Đề bài: Nhập vào một danh sách số nguyên và sắp xếp nó theo thuật toán QuickSort.
Giải:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
lst = list(map(int, input("Nhập danh sách số nguyên: ").split()))
print("Danh sách sau khi sắp xếp:", quicksort(lst))
Bài 73: Tìm đường đi ngắn nhất bằng thuật toán Dijkstra
Đề bài: Cho một đồ thị dưới dạng danh sách kề có trọng số, tìm đường đi ngắn nhất từ một đỉnh s đến các đỉnh còn lại bằng thuật toán Dijkstra.
Giải:
import heapq
def dijkstra(graph, start):
pq = [(0, start)]
distances = {node: float('inf') for node in graph}
distances[start] = 0
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (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_node = 'A'
print("Khoảng cách ngắn nhất:", dijkstra(graph, start_node))
Bài 74: Kiểm tra chu trình trong đồ thị (DFS)
Đề bài: Kiểm tra xem đồ thị có chứa chu trình hay không bằng thuật toán DFS.
Giải:
def has_cycle(graph, node, visited, parent):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if has_cycle(graph, neighbor, visited, node):
return True
elif neighbor != parent:
return True
return False
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}
visited = {node: False for node in graph}
print("Đồ thị có chu trình" if has_cycle(graph, 0, visited, -1) else "Đồ thị không có chu trình")
Bài 75: Tính số cách đi trên lưới (Lập trình động)
Đề bài: Tìm số cách đi từ góc trên trái đến góc dưới phải của lưới m x n chỉ đi xuống hoặc sang phải.
Giải:
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
m, n = map(int, input("Nhập kích thước lưới m x n: ").split())
print(f"Số cách đi từ (0,0) đến ({m-1},{n-1}):", unique_paths(m, n))
Bài 76: Dãy con chung dài nhất (LCS)
Đề bài: Nhập vào hai chuỗi, tìm độ dài dãy con chung dài nhất.
Giải:
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
s1 = input("Nhập chuỗi thứ nhất: ")
s2 = input("Nhập chuỗi thứ hai: ")
print("Độ dài dãy con chung dài nhất:", lcs(s1, s2))
Bài 77: Phân hoạch tập hợp (Subset Sum)
Đề bài: Kiểm tra xem có thể chia danh sách số nguyên thành hai tập con có tổng bằng nhau hay không.
Giải:
def can_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = {0}
for num in nums:
dp |= {num + x for x in dp}
if target in dp:
return True
return False
lst = list(map(int, input("Nhập danh sách số nguyên: ").split()))
print("Có thể phân hoạch" if can_partition(lst) else "Không thể phân hoạch")
