Tài liệu, ebook Kỹ Thuật Lập Trình

Bài giảng: Kiểm tra đánh giá trên máy Tiết thứ: 57-60 Tuần thứ: 15 Mục đích, yêu cầu: Mục đích: - Kiểm tra đánh giá phân loại sinh viên bằng hình thức lập trình giải bài toán trên máy Yêu cầu: - Sinh viên bốc thăm đề, lập trình giả bài toán trên máy tính. - Hình thức tổ chức dạy học: Thực hành trên máy tính - Thời gian: 4 tiết - Địa điểm:...

82 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1979 | Lượt tải: 0

Giải thuật tìm kiếm trên B-tree Algorithm search_B_tree Input: subroot là gốc của cây và target là khóa cần tìm Output: dữ liệu tìm thấy 1. if (cây rỗng) 1.1. return not_present 2. else 2.1. Tìm target trên dữ liệu của subroot 2.2. if (tìm thấy) 2.2.1. return dữ liệu tìm thấy 2.3. else //Tìm không thấy sẽ ngừng tại vị trí có khóa vừa lớn...

26 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 3038 | Lượt tải: 2

Cây cân bằng chiều cao - AVL Cây cân bằng hoàn toàn: Số node của nhánh trái và nhánh phải chênh nhau không quá 1. ĐN cây AVL: BST Tại node bất kỳ, chiều cao nhánh trái và nhánh phải chênh nhau không quá 1. Ký hiệu cho mỗi node của cây AVL: Node cân bằng: ‘-’ Nhánh trái cao hơn: ‘/’ Nhánh phải cao hơn: ‘\’

52 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1967 | Lượt tải: 1

Đánh giá phương pháp dùng bảng Hash load factor λ = số mẫu tin/kích thước bảng hash Tìm kiếm với bảng hash nối kết: 1+(1/2)λ phép thử khi tìm thấy λ phép thử khi không tìm thấy. Tìm với bảng hash địa chỉ mở (thử ngẫu nhiên): (1/λ)ln (1/(1-λ)) phép thử khi tìm thấy 1/(1-λ) phép thử khi không tìm thấy Tìm với bảng hash địa chỉ mở (thử tuyến t...

25 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1823 | Lượt tải: 1

Đánh giá Heap sort Trường hợp xấu nhất: C = 2n lg n + O(n) M = n lg n + O(n) So với Quick sort Trung bình: chậm hơn quick sort Xấu nhất: O(n lg n) < n(n-1)/2

65 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1854 | Lượt tải: 1

Đánh giá độ phức tạp của giải thuật So sánh với các hàm cơ bản: g(n) = 1 Constant function g(n) = log n Logarithmic function g(n) = n Linear function g(n) = n2 Quadratic function g(n) = n3 Cubic function g(n) = 2n Exponential function

30 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1774 | Lượt tải: 0

Thêm vào trong DSLK kép Algorithm Insert Input: x là giá trị cần thêm vào tại position (0<=position<=count) Output: danh sách đã thêm giá trị x vào vị trí position 1. if position là 0 1.1. if số phần tử là 0 1.1.1. Trỏ following đến NULL 1.2. Trỏ preceding đến NULL 2. else 2.1. Trỏ preceding đến vị trí position -1, following đến vị trí pos...

39 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1879 | Lượt tải: 1

Bài toán 8 con Hậu – Giải thuật Algorithm Solve Input trạng thái bàn cờ Output 1. if trạng thái bàn cờ chứa đủ 8 con hậu 1.1. In trạng thái này ra màn hình 2. else 2.1. for mỗi ô trên bàn cờ mà còn an toàn 2.1.1. thêm một con hậu vào ô này 2.1.2. dùng lại giải thuật Solve với trạng thái mới 2.1.3. bỏ con hậu ra khỏi ô này End Solve

28 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1845 | Lượt tải: 2

Giải thuật cộng hai đa thức 1 Algorithm Equals_sum1 Input: p,q là hai đa thức Output: đa thức tổng 1. Trong khi p và q chưa rỗng 1.1. Lấy phần tử front của p và q thành p_term, q_term 1.2. Nếu bậc của p_term lớn (hoặc nhỏ) hơn bậc của q_term 1.2.1. Đẩy p_term (hoặc q_term) vào kết quả 1.2.2. Bỏ phần tử đầu trong p (hoăc trong q) 1.3. Ngược...

33 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1921 | Lượt tải: 1

Giải thuật cộng hai đa thức 1 Algorithm Equals_sum1 Input: p,q là hai đa thức Output: đa thức tổng 1. Trong khi p và q chưa rỗng 1.1. Lấy phần tử front của p và q thành p_term, q_term 1.2. Nếu bậc của p_term lớn (hoặc nhỏ) hơn bậc của q_term 1.2.1. Đẩy p_term (hoặc q_term) vào kết quả 1.2.2. Bỏ phần tử đầu trong p (hoăc trong q) 1.3. Ngược...

56 trang | Chia sẻ: truongthinh92 | Ngày: 27/07/2016 | Lượt xem: 1854 | Lượt tải: 2