các bạn tự tìm sách trên google theo gợi ý bên dưới nhé!

algorithms and complexity.pdf

bài tập thực hành phân tích thuật toán.pdf

generating functionology.pdf

pttt01_phân tích và thiết kế thuật toán.pdf

pttt02_đá á nh giá bằng công cụ toán học cơ bản.pdf

pttt03_đệ quy và đánh giá.pdf

pttt04_hàm sinh và ứng dụng.pdf

pttt05_hoán vị và ứng dụng.pdf

pttt06_đá á nh giá một số thuật toán thông dụng.pdf

pttt08_chia để trị divide and conquer.pdf

pttt09_kỹ thuật greedy (tham lam).pdf

Bài tập môn phân tích và thiết kế thuật toán:

Bài 1: giải thuật tìm n!

Ý tưởng bài toán:

Để tính giai thừa của một số nguyên dương n, ta có thể sử

dụng công thức:

n! = n x (n-1) x (n-2) x ... x 2 x 1

Ta có thể sử dụng đệ quy để tính giai thừa của n bằng cách

tính giai thừa của (n-1) và nhân với n

Code trong python:

def giai_thua(n):

if n == 1 :

return 1

else:

return n * giai_thua(n- 1 )

n = int(input("nhap vao n: "))

print(giai_thua(n))

Đánh giá độ phức tạp:

Độ phức tạp của thuật toán tính giai thừa bằng đệ quy có

thể được đánh giá qua 3 mức độ như sau:

 Tốt nhất: O(1)

 Trung bình: O(n)

 Xấu nhất: O(n)

Giải thích:

 Tốt nhất: khi giá trị đầu vào là 1, thì thuật toán sẽ thực

hiện 1 lần phép so sánh và 1 lần trả về giá trị 1, vì vậy độ

phức tạp là O(1).

 Trung bình và xấu nhất: khi giá trị đầu vào là n, thì

thuật toán sẽ thực hiện n lần phép nhân và n lần phép gọi

đệ quy, vì vậy độ phức tạp của thuật toán là O(n).

BÀI 2: giải thuật Eculid. ( tìm ước chung lớn nhất của 2 số

nguyên )

Ý tưởng bài toán:

Giả sử ta có hai số nguyên dương a và b (a > b), ta muốn tìm ước chung

lớn nhất của chúng.

 Nếu b = 0, kết quả là a.

 Nếu b khác 0, ta thực hiện đệ quy với hai số nguyên b và a % b

(phần dư của a khi chia cho b).

Hình ảnh minh h a ọ

Code trong python:

Bài 3:thuật toán tìm max

Ý tưởng bài toán:

sử dụng đệ quy để liên tục giảm độ dài của mảng và so sánh giá trị của phần tử

cuối cùng với giá trị lớn nhất hiện tại. Nếu phần tử cuối cùng lớn hơn giá trị lớn

nhất hiện tại, ta cập nhật giá trị lớn nhất hiện tại. Sau đó, ta gọi đệ quy với độ dài

của mảng giảm đi một đơn vị và giá trị lớn nhất hiện tại. Tiếp tục thực hiện đệ

quy đến khi độ dài của mảng bằng 0 và trả về giá trị lớn nhất tìm được.

Code trong python:

def findMax(arr, n, maxVal):

if n == 0 :

return maxVal

else:

if arr[n- 1 ] > maxVal:

maxVal = arr[n- 1 ]

return findMax(arr, n- 1 , maxVal)

# Ví dụ

arr = [ 3 , 5 , 2 , 9 , 7 , 1 , 8 , 4 ]

maxValue = findMax(arr, len(arr), float("-inf"))

print(maxValue) # Kết quả: 9

Đánh giá độ phức tạp:

 Tốt nhất: O(1), khi mảng chỉ có một phần tử và giá trị của phần tử

đó là giá trị lớn nhất.

 Xấu nhất: O(n), khi mảng có n phần tử và phần tử lớn nhất nằm ở

cuối mảng.

 Trung bình: O(n), khi mảng có n phần tử và phần tử lớn nhất xuất

hiện ở bất kỳ vị trí nào.

Giải thích: Đối với mỗi lần gọi đệ quy, ta sẽ giảm độ dài của mảng đi 1. Vì vậy, số

lần gọi đệ quy sẽ là n. Trong mỗi lần gọi đệ quy, ta sẽ thực hiện một số thao tác

cơ bản như so sánh giá trị của phần tử cuối cùng với giá trị lớn nhất hiện tại và

cập nhật giá trị lớn nhất hiện tại nếu cần. Vì vậy, độ phức tạp của giải thuật là

O(n).

BÀI 4: tìm số fibinacci

Ý tưởng bài toán:

 nếu n = 0, số Fibonacci thứ n là 0

 nếu n = 1, số Fibonacci thứ n là 1

 nếu n > 1, số Fibonacci thứ n là tổng của hai số Fibonacci liền trước

nó

Vì vậy, để tính số Fibonacci thứ n, chúng ta cần tính số Fibonacci thứ n-

và n-2.

Code trong python:

def fibonacci(n):

if n <= 1 :

return n

else:

return fibonacci(n- 1 ) + fibonacci(n- 2 )

n = int(input("Nhập n: "))

fib_n = fibonacci(n)

print(f"Số Fibonacci thứ {n} là {fib_n}")

Đánh giá độ phức tạp thuật toán:

Tốt nhất: O(1). Khi n = 0 hoặc 1 hoặc 2, ta trả về giá trị cố định 0 hoặc 1, do đó

thời gian thực hiện của thuật toán là rất nhanh và không phụ thuộc vào n.

Trung bình, xấu nhất; O(2^n). Khi n lớn, thuật toán sẽ gọi đệ quy nhiều lần để

tính toán số Fibonacci thứ n. Mỗi lần gọi đệ quy sẽ tạo ra hai lần gọi đệ quy khác,

do đó số lần gọi đệ quy tăng theo cấp số nhân. Thời gian thực hiện của thuật

toán tăng theo cấp số nhân 2^n, vì mỗi lần gọi đệ quy tốn O(1) và ta phải gọi đệ

quy 2 lần.

Ví d ụtnh f(5).

Chứng minh độ phức tạp thuật toán với phương pháp truy

hồi: (gõ lại bằng máy cho chuyên nghiệp nhá)

Ý tưởng giải:

1. Đưa n-1 đĩa từ cọc A đến cọc B bằng cách sử dụng cọc C làm cọc

trung gian.

2. Di chuyển đĩa còn lại từ cọc A đến cọc C.

3. Đưa n-1 đĩa từ cọc B đến cọc C bằng cách sử dụng cọc A làm cọc

trung gian.

Code trong python:

def tower_of_hanoi(n, source, target, auxiliary):

# n: số lượng đĩa cần di chuyển

# source: cọc ban đầu

# target: cọc đích

# auxiliary: cọc trung gian

# nếu chỉ có một đĩa, di chuyển nó từ cọc ban đầu đến cọc đích và kết

thúc

if n == 1 :

print("Move disk 1 from source", source, "to target", target)

return

# di chuyển n-1 đĩa từ cọc ban đầu đến cọc trung gian

tower_of_hanoi(n - 1 , source, auxiliary, target)

# di chuyển đĩa cuối cùng từ cọc ban đầu đến cọc đích

print("Move disk", n, "from source", source, "to target", target)

# di chuyển n-1 đĩa từ cọc trung gian đến cọc đích

tower_of_hanoi(n - 1 , auxiliary, target, source)

# ví dụ sử dụng hàm trên cho 3 đĩa, bắt đầu từ cọc A, di chuyển đến cọc C,

sử dụng cọc B làm cọc trung gian

n = 3

tower_of_hanoi(n, &

039;A&

039;, &

039;C&

039;, &

039;B&

039;)

Kết quả:

Đánh giá độ phức tạp thuật toán:

 Tốt nhất: O(1) - khi n = 1 , ta chỉ cần di chuyển đĩa từ cọc ban đầu

đến cọc đích và kết thúc hàm.

 Trung bình: O(2^n) - khi n > 1 , ta cần di chuyển n-1 đĩa từ cọc ban

đầu đến cọc trung gian, sau đó di chuyển đĩa cuối cùng từ cọc ban đầu

đến cọc đích và cuối cùng di chuyển n-1 đĩa từ cọc trung gian đến cọc

đích. Vì mỗi lần di chuyển đĩa đều có hai lựa chọn (từ cọc ban đầu đến cọc

đích hoặc từ cọc đích đến cọc ban đầu), nên số lần di chuyển là 2^n - 1.

 Xấu nhất: O(2^n) - khi n > 1 , ta vẫn phải di chuyển n-1 đĩa từ cọc

ban đầu đến cọc trung gian, sau đó di chuyển đĩa cuối cùng từ cọc ban

đầu đến cọc đích và cuối cùng di chuyển n-1 đĩa từ cọc trung gian đến cọc

đích. Vì số lần di chuyển là 2^n - 1, nên độ phức tạp là O(2^n).

Bài 6: Tìm hiểu thêm về đệ quy_Duyệt đồ thị theo chiều

sâu bằng đệ quy

Ý tưởng bài toán:

Ý tưởng chính của thuật toán là thực hiện duyệt DFS trên đồ thị, bắt đầu từ một

đỉnh bất kỳ, sau đó tiếp tục duyệt trên các đỉnh kề với đỉnh hiện tại chưa được

duyệt. Trong quá trình duyệt, lưu lại danh sách các đỉnh đã được duyệt và in ra

kết quả cuối cùng

Code trong python:

def DFS_traversal(graph):

visited_nodes = [] # khởi tạo danh sách các đỉnh đã được duyệt

num_nodes = len(graph) # số lượng đỉnh trong đồ thị

# định nghĩa hàm đệ quy DFS để duyệt đồ thị

def DFS(current_node):

visited_nodes(current_node) # thêm đỉnh hiện tại vào danh

sách đã duyệt

for neighbor in range(num_nodes): # duyệt qua tất cả các đỉnh kề

với đỉnh hiện tại

if graph[current_node][neighbor] == 1 and neighbor not in

visited_nodes:

# nếu đỉnh kề chưa được duyệt, thực hiện DFS trên đỉnh đó

DFS(neighbor)