Viblo Algorithm

Trong chuyên đề này, chúng ta sẽ cùng nghiên cứu về hai kĩ thuật khá quen thuộc và có tính ứng dụng cao trong các bài toán số học, đó là Phép nhân Ấn Độ và Thuật toán bình phương và nhân - những kĩ thuật sẽ giúp các bạn tính toán và trong thời gian . Mặc dù nghe có vẻ khá vô dụng (bởi vì thực ra phép nhân chỉ cần thực hiện trực tiếp), ...

I. Phép đồng dư thức cơ bản

Đồng dư thức là phép toán lấy số dư của số này khi chia cho số khác, kí hiệu là . Ví dụ: $5 \% 2=15 \equiv 1(mod2)$.

Phép đồng dư thức có tính chất phân phối đối với phép cộng, phép nhân và phép trừ, cụ thể như sau:

•      .
  

•      .
  

•      .
  

Riêng đối với phép chia, chúng ta không có tính chất phân phối, mà phải sử dụng một lí thuyết là Nghịch đảo mo...

I. Tìm các ước của một số nguyên dương

1. Giải thuật ngây thơ

Để tìm tất cả các ước nguyên dương của một số nguyên dương phương pháp dễ nhất là sử dụng một vòng lặp, duyệt qua toàn bộ các giá trị từ $1N,NN$.

Cài đặt

Dưới đây là cài đặt đếm số lượng ước nguyên dương của một số nguyên dương :

Dễ dàng nhận thấy giải thuật có độ phức tạp nếu như có giá trị khoảng $10^81$s. Ta cần một giải t...

I. Thuật toán và những tính chất của thuật toán

1. Khái niệm

Thuật toán - hay còn gọi là giải thuật - là khái niệm quan trọng nhất trong Tin học. Nó là nền tảng cho mọi khía cạnh của Tin học. Khái niệm về thuật toán đã tồn tại từ thời cổ đại, sớm nhất ở đế chế Babylonia với thuật toán chia vào năm 2500 TCN. Khái niệm về thuật toán có thể phát biểu như sau:

Thuật toán là một dãy hữu hạn các b...

I. Giới thiệu về STL STL (Standard Template Library) là một thư viện template (lập trình theo mẫu) cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của ngôn ngữ lập trình C. Với khái niệm template, những người lập trình đã đề ra khái niệm lập trình khái lược (generic programming), C++ được cung cấp kèm với bộ thư viện chuẩn ...

I. Ý tưởng thuật toán Chúng ta hãy cùng xem xét tình huống sau: Trong giờ Toán tại lớp $1A$, thầy giáo viết lên bảng một dãy số như sau:

$4, 2, 2, 8, 3, 3, 1, 2$

Thầy giáo yêu cầu cả lớp hãy sắp xếp dãy số trên theo thứ tự không giảm từ trái qua phải. Cả lớp đều đang loay hoay vì trong bài toán lần này mỗi số không phải chỉ xuất hiện $1$ lần duy nhất như bình thường mà có thể lặp lại. An là m...

I. Làm quen với thuật toán So với thuật toán sắp xếp nổi bọt (bubble sort) thì thuật toán sắp xếp nhanh có tốc độ nhanh hơn. Thay vì đi theo sắp xếp từng cặp như bubble sort, chúng ta có thể chia dữ liệu ra thành $2$ danh sách, rồi so sánh từng phần tử của danh sách với một phần tử được chọn (gọi là phần tử chốt) và mục đích của chúng ta là đưa phần tử chốt về đúng vị trí của nó.

II. Miêu tả t...

I. Bài toán sắp xếp

Sắp xếp là một khái niệm mà chúng ta dễ dàng gặp trong cuộc sống cũng như trong công việc. Cùng lấy một vài ví dụ:

• Sắp xếp lại đồ đạc trong phòng, trong nhà.
• Sắp xếp các tài liệu trong tủ sách theo thứ tự.
• Sắp xếp công việc cho anh em trong công ty.

Trong Tin học, việc sắp xếp luôn luôn diễn ra không ngừng mà đôi khi chúng ta không nhận ra. Chẳng hạn, trong mỗi fold...

[IMG]

I. Làm quen với thuật toán

Nghe đến tên gọi thú vị của thuật toán sắp xếp này có khi các bạn cũng hình dung sơ sơ về phương thức làm việc của thuật toán rồi chứ. Sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp cơ bản, chúng ta sẽ thao tác dữ liệu cần sắp xếp "nổi bọt" lần lượt theo thứ tự chúng ta mong muốn (từ trái sang phải, từ dưới lên trên, từ trên xuống dưới, ...).

II. Miêu tả...