25/05/2018, 00:00

Một số bài toán thông dụng

Trong thực tế giải quyết bài toán, nhiều khi ta cần thực hiện một công việc nào đó tương tự nhau nhiều lần, chẳng hạn như nhập danh sách sinh viên hay tính điểm trung bình môn học cho một lớp v.v... Khi đó ta thường phải sử dụng đến thuật ...

Trong thực tế giải quyết bài toán, nhiều khi ta cần thực hiện một công việc nào đó tương tự nhau nhiều lần, chẳng hạn như nhập danh sách sinh viên hay tính điểm trung bình môn học cho một lớp v.v... Khi đó ta thường phải sử dụng đến thuật toán lặp. Thuật toán lặp có thể mô tả bằng sơ đồ khối như sau

Một lưu ý quan trọng là : Khâu "Thực hiện công việc" ở trên có thể chứa một hoặc rất nhiều các thao tác khác, như : Kiểm tra, nhập xuất thậm chí lại là một thuật toán lặp.

Một số ví dụ:

Sau đây ta sẽ lấy một số ví dụ minh hoạ cụ thể của việc áp dụng thuật toán lặp được mô tả ở trên.

Ví dụ 1: Viết lưu đồ nhập vào một danh sách họ tên của một lớp có N sinh viên.

Ở đây gọi i là vị trí của SV thứ i. Khi đó ta lưu đồ thuật toán như sau:

Ở ví dụ này, khâu "Thực hiện công việc" chỉ làm một việc là nhập họ tên cho sinh viên thứ i.

Ví dụ 2: Vẽ lưu đồ thuật toán để đếm xem có bao nhiêu chữ số chia hết cho 3 trong khoảng từ 1 đến 1000.

Gọi i là số hiện tại đang xét và Tong_So là tổng các chữ số chia hết cho 3, ta có lưu đồ như sau:

Nhận xét: Trong lưu đồ này khâu "Thực hiện công việc" đã phức tạp hơn, trong nó có chứa thêm các thao tác xử lý và kiểm tra khác.

Nhiều bài toán về khoa học kỹ thuật có sử dụng rất nhiều đến kỹ thuật tìm kiếm. Ngoài ra, khái niệm tìm kiếm cũng đã quá quen thuộc trong đời sống thường ngày của chúng ta, như tìm kiếm thông tin, tìm kiếm (tra cứu) từ điển, tìm một học sinh có điểm thi cao nhất trong lớp học, tìm một số lớn nhất trong một dãy số v.v... Để tìm kiếm các thông tin như vậy, có rất nhiều phương pháp (thuật toán) tìm kiếm khác nhau, mỗi phương pháp đều có những ưu nhược điểm riêng. Dưới đây chúng ta chỉ đề cập đến một thuật toán tìm kiếm đơn giản là thuật toán tìm kiếm TUẦN TỰ.

Tình huống đặt ra là : Có n mục thông tin (n > 0), hãy tìm mục thông tin x, nếu có thì thông báo là tìm thấy và cho biết vị trí của mục x, Trái lại thông báo là không tìm thấy.

Ý tưởng giải quyết bài toán này như sau :

- Ta sẽ thử lần lượt từ mục 1 cho đến mục thứ n,

- Qua mỗi lần thử ta so sánh mục x với mục thứ i.

- Nếu mục thứ i bằng x thì thông báo là thấy và vị trí thấy là i, trái lại ta sẽ thử tiếp với mục thứ i + 1.

- Nếu đã thử hết các mục (tức khi i > n ) mà vẫn chưa thấy thì thông báo là không tìm thấy.

Có thể mô tả bằng lưu đồ như sau:

Ví dụ sử dụng thuật toán tìm kiếm.

Cho một danh sách sinh viên lớp TinK33, Tổng số có 100 SV. Hãy vẽ lưu đồ thuật toán tìm xem sinh viên Phạm Văn An có trong danh sách này không. Nếu thấy thì thông báo là "Đã tìm thấy", Trái lại thông báo là "Không thấy"

Ta ký hiệu SV[i] là sinh viên đang xét và có số thứ tự thứ i trong danh sách,

X = "Phạm Văn An". Khi đó lưu đồ thuật toán được biểu diễn như sau:

Thuật toán sắp xếp

Thuật toán sắp xếp là một thuật toán chỉ ra cách thức để sắp xếp một danh sách các thông tin theo một tiêu chí nào đó. Ví dụ ta có thuật toán sắp xếp danh sách sinh viên của lớp theo vần Alphabet của họ tên, hay sắp xếp các thí sinh thi Đại học theo số báo danh v.v...

Trong thực tế, tuỳ thuộc vào lượng thông tin cần sắp xếp mà người ta sử dụng các thuật toán có độ phức tạp và thời gian tính toán khác nhau. Ở đây ta sẽ đề cập đến một thuật toán sắp xếp thường dùng trong các bài toán đơn giản.

Xét bài toán: Một danh sách có n mục thông tin, mỗi mục chỉ chứa các chữ cái Alphabet. Hãy sắp xếp danh sách này theo trình tự chữ cái Alphabet.

Để có thể giải quyết được bài toán này bằng thuật toán nêu sau đây, trước hết chúng ta cần nắm được một thuật toán khác gọi là "thuật toán đổi chỗ".

+ Thuật toán đổi chỗ:

Một tình huống trong thực tế: Có 2 chiếc Can, một đựng Xăng và một đựng Dầu. Hãy chuyển Xăng từ can xăng sang can Dầu và ngược lại, chuyển Dầu từ can dầu sang can Xăng.

Ta có thể thực hiện theo như sơ đồ mô tả dưới đây:

Ở đây ta sử dụng một can rỗng thứ 3, gọi là Can trung gian.

- Bước 1: Đổ can xăng sang can Trung gian

- Bước 2: Đổ Dầu sang can xăng

- Bước 3: Đổ từ can trung gian sang can Dầu

Như vậy ta đã thực hiện được yêu cầu của bài toán đặt ra.

Ta cũng có thể mở rộng tình huống này trong Toán học. Hãy hoán đổi giá trị của hai số x và y cho nhau.

Sử dụng ý tưởng ở trên, ta làm như sau:

- Lưu giá trị của x vào một số trung gian, giả sử là z: z = x

- Thay x bằng giá trị y: x = y

- Thay y bằng giá trị z: y = z

Như vậy ta đã đổi chỗ được giá trị của x và y thông qua một số trung gian z.

Sau đây, Ta sẽ lấy một ví dụ về sắp xếp một danh sách theo thứ tự tăng dần.

Ví dụ, hãy sắp xếp danh sách gồm các số 57, 33, 21, 84, 49, 50, 75 theo thứ tự tăng dần.

Các bước thực hiện:

- Ta đi qua danh sách để tìm ra phần tử nhỏ nhất và thấy rằng nó ở vị trí 3:

67, 33, , 84, 49, 50, 75

- Ta hoán vị phần tử này với phần tử đầu tiên và như vậy xác định đúng vị trí của phần tử nhỏ nhất ở đầu danh sách:

- Ta lại đi qua danh sách con gồm các phần tử từ vị trí 2 để tìm phần tử nhỏ nhất :

Trong dãy con này, ta thấy 33 là nhỏ nhất do vậy ta thực hiện hoán vị với chính nó. Và được phần tử nhỏ nhất tiếp theo là 33.

Cứ tiếp tục theo cách này, định vị phần tử nhỏ nhất trong danh sách con từ vị trí 3 và thực hiện cho đến khi nào danh sách con chỉ chứa 2 phần tử cuối cùng.

Bây giờ chúng ta sẽ thảo luận chi tiết thuật toán Sắp xếp theo yêu cầu trên.

0