Archive | Thuật toán

[Cây] Một số phép toán trên cây nhị phân tìm kiếm

[qads] Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Dưới đây là một ví dụ về cây nhị phân tìm kiếm: Nội dung Cấu trúc cây Thêm phần tử vào cây Nhập cây Duyệt cây Tìm một node […]

Các thuật toán kiểm tra số nguyên tố – Algorithm check prime number

Bài viết nêu các thuật toán kiểm tra số nguyên tố từ đơn giản đến nâng cao, viết theo tư duy của bạn đọc từ đơn giản đến các bước tối ưu thuật toán. Code demo viết trên ngôn ngữ C

[Thuật toán – C/C++] Quick Sort – Các vấn đề liên quan

Trước tiên chúng ta tìm hiểu ý tưởng thuật toán Ý tưởng: QuickSort chia mảng thành hai danh sách bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn được gọi là phần tử chốt. Những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau […]

Đáp án OLP Tin học Sinh viên ICTU 2017

GỢI Ý LỜI GIẢI BÀI THI OLP TIN HỌC SINH VIÊN ICTU 2017 Dưới đây là đề bài, hướng dẫn giải, lời giải của đề thi. Code được viết bằng ngôn ngữ C, các ngôn ngữ khác làm tương tự. Tất cả các bài đều dùng nhập xuất chuẩn (nhập từ bàn phím, xuất ra màn hình). Download PDF File Bài 1: Doanh thu (50 điểm) Đề bài: DOANHTHU Thời gian chạy: 1 gây Điểm: […]

[Thuật toán – Java] Chuyển biểu thức trung tố sang hậu tố – Java – converts infix to postfix

Các biểu thức đại số được sử dụng hằng ngày đều được biểu diễn dưới dạng trung tố (infix). Cách biểu diễn này rất dễ hiểu với con người vì hầu hết các toán tử (+, -, *, /) đều là toán tử hai ngôi và chúng phân cách giữa hai toán hạng với nhau. Tuy nhiên đối với máy tính, để tính được giá trị của một biểu thức đại số theo dạng này […]

[C/C++] Tính toán với số lớn

Để xử lý số lớn chúng ta sẽ chuyển sang xử lý chuỗi ký tự. Trong code dưới đây các bạn chú ý phuơng thức str.insert(int pos, int n, int ch); chèn n lần ký tự ch vào vị trí pos của chuỗi str; Ngoài ra còn có 2 phương thức khác là : str.insert(int pos, char* s); chèn s (mảng ký tự kết thúc ‘’) vào vị trí pos của str; str.insert(int pos, string […]

Lát gạch 2*n

Đề bài: http://vn.spoj.com/problems/LATGACH/ Đầu tiên ta xét hình chữ nhật 2×1 thì có 1 cách xếp đó là xếp 1 viên gạch 2×1. Xét hình chữ nhật 2×2 thì có 2 cách xếp đó là xếp 2 viên 1×2 hoặc 2 viên 2×1. Xét hình chữ nhật 2xi có các trường hợp sau với f(i) là số cách xếp cho hình chữ nhật 2xi. => f(i) = f(i-1) + f(i-2) với f(1) = 1 và […]

[Java – Thuật toán] Mô phỏng thuật toán Dijkstra tìm đường đi ngắn nhất

Về thuật toán, bạn có thể xem lại tại bài viết Tìm đường đi ngắn nhất Dijkstra, Floyd. Bài này mình sẽ giới thiệu tới các bạn chương trình mô phỏng thuật toán Dijkstra có đồ họa trên Java, đây cũng là đề tài thực tập cơ sở của mình. Update ngày 23/05/2015: Sửa lỗi không load được icon trên windows. Chương trình cho phép người dùng vẽ đồ thị một cách nhanh chóng và […]

Thư viện tính biểu thức theo thuật toán Balan

Thư viện này mình xây dựng trên nền tảng java để phục vụ việc tính toán giá trị các biểu thức phức tạp. Một số hàm chính trong thư viện gồm có: Update 09/10/2014: phiên bản 1.1: Fix & bắt một số lỗi, thông báo khi phép toán không chuẩn. isNumber(String s) : trả về true nếu s là số, ngược lại trả về false isNumber(char c): trả về true nếu s là số, ngược […]

[Cây nhị phân] Chuyển cây nhị phân sang cây nhị phân tìm kiếm

Cách làm của mình rất đơn giản. Chúng ta chỉ việc duyệt vào lưu lại các phần tử của cây nhị phân ban đầu vào mảng và cuối cùng là chèn các giá trị của mảng vào cây theo cách chèn 1 Node vào cây nhị phâ. Vậy là đã được 1 cây nhị phân tìm kiếm. Code: