Phân tích thiết kế thuật toán

Thuật toán tìm kiếm nhị phân có thể phân loại phương pháp nào bên dưới

• Quy hoạch động

• Vét cạn

• Tham lam

• Chia để trị

có 4 thuật toán A1, A2, A3, A4 có độ phức tạp lần lượt log(n), nlog(n), log(log(n)), n/log(n) thuật toán nào là tốt nhất

• A1

• A2

• A3

• A4

Phương pháp quay lui không thể giải quyết bài toán nào

• Bài toán mạch Hamiliton

• Bài toán người bán hàng

• Bài toán n quân hậu

• Bài toán tổng tập con

Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân

• 0(Nlog(N))

• Log(N)

• 1

• N

Khi chuyển biểu thức (12 - a) * (b + 9) / (d * 4) sang biểu diễn dạng hậu tố ta được biểu thức nào

• /12a - b9 + d4*

• 12a - b9 + *d4*/

• 4b d9 + a12 - */

• 12 - a * b + 9 / d * d

Trong quy hoạch động, kỹ thuật lưu trữ các giá trị tính toán trước đó gọi là

• Mapping

• Saving value property

• Storing value property

• Memorization

kết quả chương trình sau:

Thuật toán knapsack:

• 100

• Lỗi thực thi

• 180

• 220

Chiến lược giải quyết 1 bài toán bầng cách kết hợp các lời giải tối ưu của các bài toán khác nhau được gọi là

• Quy hoạch động

• Tham lam

• Chia để trị

• Đệ quy

Thuật toán qui lui nhanh hơn thuật toán vét cạn

• Đúng

• Sai

Bạn được cấp không giới hạn 3 tờ tiền có mệnh giá 5, 7, 9 số tiền nào dưới đây bạn không thể ghép được bằng các mệnh giá bên trên

• 50

• 21

• 13

• 23