• Tài liệu học thuật toán

    admin - 19/05/2015

    Tài liệu dành cho các bạn muốn trở thành thánh thuật toán , hơi tiếc là không có C++, chỉ có Pascal:  

    1) Giải thuật và Lập trình.

    2) Tài liệu giáo khoa chuyên tin: Quyển 1, Quyển 2, Quyển 3-1, Quyển 3-2

    3) 150 ... (xem thêm)

    (13 phản hồi)

  • KỸ THUẬT ĐẢO NHÃN TRONG QUY HOẠCH ĐỘNG

    nxphuc - 02/04/2015

    Tác giả: Trương Thành Đạt

    Xét bài toán sau đây: Cho hai xâu A và B (|A| ≤ 106, |B| ≤ 5000), tìm xâu con chung dải nhất (Longest Common Subquence) của hai xâu trên.

    Ta có một cách giải mà chắc thẳng ai cũng đã biết, dùng phương pháp quy hoạch động để giải bài toán trên một cách dễ dàng với độ phức tạp tính toán là O(|A|.|B|). Trong bài toán này phương pháp này là không khả thi bởi vì |A|.|B| ≤ 5*109.

    Có thể nhận thấy rằng, độ dài xâu con chung dài nhất của hai xâu A và B ≤ min(|A|, |B|). Ta có một cách giải thông thường là gọi F[i][j] = k, với ý nghĩa F[... (xem thêm)

    (3 phản hồi)

  • Lời giải một số bài tập về toán học

    nxphuc - 28/02/2015

    Học theo admin, xả hàng đầu năm :) Bài viết này sẽ đưa ra lời giải 3 bài tập thuộc chủ đề toán học mức độ khó là Lũy thừa 2Trò chơi với dãy số và Giai thừa

    Lũy thừa 2:

    Việc cần xử lý trong bài này là làm sao để tính (A-1 mod K) trong trường hợp số mũ là âm. Đây là lý thuyết nghịch đảo Modulo. Lúc này ta có thể đưa ra các trường hợp để giải bài toán như sau:

     -... (xem thêm)

    (7 phản hồi)

  • Binary Indexed Tree (BIT)

    admin - 26/02/2015

    Đầu năm xả hàng, ad hướng dẫn cách giải một số bài tập về Binary Indexed Tree – BIT (bài Dãy nghịch thế và bài Dĩa nhạc 3). BIT là cây được biểu diễn bằng mảng có dạng như sau:

    Tổng quát, đặt m = 2k.p (với p là số lẻ). Hay nói cách khác, k là vị trí của bít 1 bên phải nhất của m. Trong cây BIT, nút có số hiệu m sẽ là nút gốc của một cây con gồm 2k nút có số hiệu từ m- 2k+1 đến m.

    Ví dụ:

        - 8 = 23.1, vậy 8 là n&... (xem thêm)

    (6 phản hồi)

  • sort(a + 1, a + 1 + n)

    admin - 11/10/2014

          Sắp xếp mảng là một thao tác thường được dùng rất nhiều trong các thuật toán như tìm kiếm nhị phân, tìm cặp gần nhất, tìm các giá trị lớn nhất, nhỏ nhất (ví dụ như các bài NHGA, CASO, LUTA, ...). Thuật toán đơn giản nhất để sắp xếp một mảng n phần tử là:

    for(i=1; i<n; i++)
       for(j=i+1; j<=n; j++)
          if(a[i]> a[j]) swap(a[i], a[j]);

         Thuật toán sắp xếp trên, cũng như một số thuật toán sắp xếp khác như SelectionSort, Insert... (xem thêm)

    (10 phản hồi)

  • Chuyển hướng standard input và standard output ra file

    admin - 10/10/2014

         Trong C++, để nhập xuất dữ liệu ta sử dụng các hàm cin, cout, scanf, printf... nhập liệu từ bàn phím (standard input) và xuất dữ liệu ra màn hình (standard output). Tuy nhiên nếu dữ liệu nhập vào khá lớn, chẳng hạn như bài BASU, và ta cần chạy chương trình nhiều lần để sửa lỗi, thì việc nhập dữ liệu từ bàn phím như vậy mất rất nhiều thời gian.

          Một cách khắc phục tình trạng này là chuyển hướng standard input, thay vì nhập từ bàn phím thì chuyển thành nhập từ file. Chỉ cần nhập liệu vào file input một lần và sau đó có thể chạy chương trình nhiều lần mà không mất công nhập liệu lại. Sử dụng... (xem thêm)

    (3 phản hồi)

Back to Top