Thư viện tài liệu, ebook tham khảo dành cho học sinh, sinh viên

1. Lược đồ chung 2. Bài toán tính số Fibonaci 3. Bài toán cái túi 4. Bài toán dãy con có tổng lớn nhất 5. Bài toán tìm xâu con chung dài nhất 6. Đường đi ngắn nhất - TT Floyd 7. Cây nhị phân tìm kiếm tối ưu

18 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 1368 | Lượt tải: 0

Để tính MaxE[i], i = 1, 2, , n, ta cũng có thể sử dụng công thức đệ quy như sau: – Với i=1 thì MaxE[i] = a[1]; – Với i >1, Gọi C là dãy con kế tiếp lớn nhất của dãy a[1].a[i] có chứa a[i]. Có hai khả năng: • Nếu C chứa a[i-1] thì tổng lớn nhất là MaxE[i-1]+a[i]; • Nếu C không chứa a[i-1] thì C chỉ gồm a[i] và tổng lớn nhất là a[i]

20 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 1046 | Lượt tải: 0

1. Lược đồ chung 2. Bài toán cái túi 3. Bài toán người du lịch 4. Đường đi ngắn nhất 5. Cây bao trùm nhỏ nhất 6. Bài toán tô màu 7. Bài toán các khoảng không giao nhau

23 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 1422 | Lượt tải: 0

Khởi tạo: S = {s0}, L(s0) =0, L(v)= vV\S Với vV\S: Với sS: Trong đó m(s,v) là độ dài đường đi từ s với v • Vì chỉ có L(s*) với s* là đỉnh vừa duyệt xong ở bước trước là có thay đổi về giá trị nên việc tính lại L(v) chỉ có ý nghĩa với các đỉnh kề với s* Với vV\S kề với s*: 2/2/2017 37 L(v) = min(L(v),L(s)+m(s,v)) L(v) = min(L(v),L...

21 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 1035 | Lượt tải: 0

IV. Bài tập 2. Cài đặt thuật toán nhân 2 số nguyên có n (chẵn) chữ số. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết. 3. Cài đặt thuật toán nhân ma trận theo chiến lược chia để trị của Strassen. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết 4. Cài đặt thuật toán tìm dãy con lớn nhất. Đánh giá độ phức tạp bằng ...

12 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 1138 | Lượt tải: 0

Thuật toán QuickSort • Thuật toán: partition • Input: A[l.r], l,r: đoạn cần phân chia • Ouput: A[l.r], i chỉ số phân chia 1. X=a[l] 2. i=l+1; 3. j=r; 4. While (i=i && a[j]>=x) j - - c. If(i

23 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 977 | Lượt tải: 0

III. TKTT Phương pháp trực tiếp 2. Bài toán áp dụng  Ví dụ 1 - Cho số nguyên a có không quá 100 chữ số và số nguyên b, 1  b  9. Tính c = ab. Thuật toán: input: a = (a[n], ., a[1])  N, n ≤ 100; b {0, 1, ., 9} output: c = a  b 1) nhớ = 0; 2) Nhân tuần tự từ a[1] đến a[n], mỗi lần cộng với nhớ cho kết quả tg. Mỗi lần nhân, phần dư (tg ...

18 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 1398 | Lượt tải: 0

Đoạn chương trình có gọi chương trình con • Độ phức tạp chương trình con dạng đệ quy • Ví dụ: xét hàm tính giai thừa Function gt(n) begin if n=0 then gt=1 else gt=n*gt(n-1) end Gọi T(n) là thời gian tính n!, thì T(n-1) là thời gian tính (n-1)! Khi n=0, ta có C(0)=1 (phép gán)

17 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 987 | Lượt tải: 0

Được Stephen Cook đưa ra năm 1971 trong bài báo nổi tiếng "The complexity of theorem proving procedures” • Là một trong số bảy bài toán của giải thiên niên kỷ được chọn bởi Viện Toán học Clay. • Mỗi bài trong số bảy bài này có giải thưởng US$1,000,000 cho lời giải đúng

20 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 1207 | Lượt tải: 0

(Bản scan) Phân tích thiết kế hệ thống thông tin - Chương 1: Tổng quan về hệ thống thông tin Sử dụng Thích hợp khi cần nhập liệu các phiếu ghi nhận thông tin về hoạt động các đối tượng trong thế giới thực (hóa đơn, phiếu nhập hàng,...)

261 trang | Chia sẻ: huyhoang44 | Ngày: 17/03/2020 | Lượt xem: 958 | Lượt tải: 0