Giải đề thi phân tích và thiết kế thuật toán năm 2024
Was this document helpful? Was this document helpful? 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).
nguyenict đã viết:Đề 2009, chia để trị x^n chưa chính xác lắm thì phải. Giả sử x^5 thì bài này sai!, đề kế thì phần câu II, chia để trị để tìm Min thì không hợp lý lắm, nó không liên quan gì đến meresort, chỉ là giải thuật theo hướng đó thôi! Admin fix nhé
Was this document helpful? Was this document helpful? Bài Tập Tổng Kết Môn Phân Tích Thiết Kế Thuật Toán
MSSV Họ và tên Lớp 1703206038 Phan Hoàng Qúi B17TT1 1602206005 Nguyễn Bá Tuấn Đạt B16TT1 1703206113 Trần Bình An B17TT2 TMDT Bài Làm
Giả sử ta có danh sách 5 đồ vật có trọng lượng, giá trị khác nhau và có thể gọi M là trọng lượng của Balo, yêu cầu đặt ra lấy các đồ vật bỏ vào balo sau cho có giá trị cao nhất. Giải Giả sử ta có danh sách 5 đồ vật được thống kê theo bảng sau và M của balo cụ thể là 15 Đồ vật A B C D E Giá trị 50 10 48 80 200 Trọng lượng 5 2 8 1 10 Áp dụng giải thuật Tham Lam để chọn đồ vật cho balo Vì mỗi đồ vật đều có giá trị và trọng lượng, ta có thể gọi Z là đơn giá của đồ vật Z của mỗi đồ vật sẽ được tính theo công thức Z= thuật toán sắp xếp lại các đồ vật có đơn giá không giảm và tìm các đồ vật có đơn giá cao để bỏ vào balo. Cụ thể cho danh sách 5 đồ vật ở trên ta có thể thống kê theo bảng sau: Đồ vật A B C D E Giá trị 50 10 48 80 200 Trọng lượng 5 2 8 1 10 Đơn giá 10 5 6 80 20 Sau khi áp dụng giải thuật Tham Lam đồ vật được sắp xếp lại theo bảng sau: Đồ vật D E A C B
|
