Mở đầu Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra (output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý nghĩa rất quan trọng trong toàn bộ hệ thống chương trình. Việc xây dựng cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng như công sức của người lập trình trong việc thiết kế, cài đặt chương trình.
Thiết kế giải thuật Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code). Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng mã giả tựa trên một hay một số ngôn ngữ lập trình nào đó (thường là ngôn ngữ mà người lập trình chọn để cài đặt thuật toán), chẳng hạn như C, Pascal, ? Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu tiến hành xây dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở của cấu trúc dữ liệu đã được chọn. Để giải quyết một vấn đề có thể có nhiều phương pháp, do vậy sự lựa chọn phương pháp phù hợp là một việc mà người lập trình phải cân nhắc và tính toán.
Sự lựa chọn này cũng có thể góp phần đáng kể trong việc giảm bớt công việc của người lập trình trong phần cài đặt thuật toán trên một ngôn ngữ cụ thể. Phân tích giải thuật Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng thức: 7 Cấu trúc dữ liệu + Giải thuật = Chương trình Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian. Khi có cấu trúc dữ liệu mà chưa tìm ra thuật giải thì không thể có chương trình và ngược lại không thể có Thuật giải khi chưa có cấu trúc dữ liệu. Một chương trình máy tính chỉ có thể được hoàn thiện khi có đầy đủ cả Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật xử lý dữ liệu theo yêu cầu của bài toán đặt ra.
Phân tích tính đúng đắn Thiết kế xong một thuật toán câu hỏi luôn luôn phải có đó là thuật toán được thiết kế đã đúng chưa? Cách đơn giản nhất mà được sử dụng thông dụng đó là viết chương trình cho thuật toán đã thiết kế và chạy thử chương trình với nhiều bộ dữ liệu vào cụ thể (tests) để kiểm tra dữ liệu ra có chuẩn xác hay chưa. Tuy nhiên, cách này cũng chỉ khẳng định được thuật toán đúng với các trường hợp cụ thể mà thôi. Có một cách khác chứng minh được thuật toán đúng đó là chứng minh bằng toán học. Nhưng với cách chứng minh thuật toán đúng bằng toán học thì phức tạp hơn nhiều và đòi hỏi nhiều kiến thức tổng hợp cả về toán học và tin học cộng với khả năng của người thực hiện việc chứng minh thuật toán 3.
Phân tích tính đơn giản Đối với các chương trình chỉ dùng 1 vài lần thì yêu cầu giải thuật đơn giản sẽ được ưu tiên vì chúng ta cần 1 giải thuật dễ hiểu, dễ cài đặt, ở đây không đề cao vấn đề thời gian chạy vì chúng ta chỉ chạy 1 vài lần. Tuy nhiên, khi 1 chương trình sử dụng nhiều lần, yêu cầu tiết kiệm thời gian sẽ được đặc biệt ưu tiên. Tuy nhiên, thời gian thực hiện chương trình lại phụ thuộc vào rất nhiều yếu tố như: cấu hình máy tính, ngôn ngữ sử dụng, trình biên dịch, dữ liệu đầu vào, … Do đó ta khi so sánh 2 giải thuật đã được implement, chưa chắc chương trình chạy nhanh hơn đã có giải thuật tốt hơn. “Độ phức tạp của thuật toán” sinh ra để giải quyết vấn đề này.
Một số giải thuật cơ bản 4. Hoán vị hai phần tử 1.Bài toán INPUT: Nhập giá trị cho hai biến A và B. OUTPUT: Xuất biến A và B với hai giá trị được hoán đổi. Ví dụ: Nhập A= 12, B = 50 thì in ra A = 50, B = 12.
Trao đổi giá trị của 2 biến A và B thông qua biến trung gian tam : B0 Bắt đầu B1 Nhập giá trị cho A và B B2 Biến tam lấy giá trị của A ( Gọi là gán giá trị A cho tam , viết tam := A ) B3 A lấy giá trị của B ( Gọi là gán giá trị B cho A , viết A := B ) B4 B lấy giá trị của tam ( Gọi là gán giá trị tam cho B , viết B := tam ) 8 B5 Thông báo kết quả B6 Kết thúc 4. Tìm số lớn nhất, nhỏ nhất Tìm phần tử có giá trị LỚN nhất của Tìm phần tử có giá trị NHỎ nhất của dãy dãy số. * Ý tưởng: * Ý tưởng: + Khởi tạo giá trị MAX = a1. + Khởi tạo giá trị MIN = a1.
+ Lần lượt với i = 2 đến N, so sánh số + Lần lượt với i = 2 đến N, so sánh số ai với ai với MAX, nếu ai > MAX thì MAX = ai MIN, nếu ai > MIN thì MIN = ai Xác định bài toán: Xác định bài toán: Input: N, a1, a2, ., aN Output: Phần tử có giá trị lớn nhất. Output: Phần tử có giá trị nhỏ nhất. Xây dựng thuật toán: Xây dựng thuật toán: Bước 1: Nhập N và dãy a1, a2,. Bước 1: Nhập N và dãy a1, a2,.
Bước 2: Max a1, i 2; Bước 2: Min a1 , i 2; Bước 3: Nếu i > N thì đưa ra giá trị Max Bước 3: Nếu i > N thì đưa ra giá trị Min rồi rồi kết thúc; kết thúc; Bước 4: Nếu ai > Max thì Max ai; Bước 4: Nếu ai <• Min thì Min ai; Bước 5: i i + 1 rồi quay lại Bước 3; Bước 5: i i + 1 rồi quay lại Bước 3; 4. Đệ quy Thiết kế giải thuật đệ quy Thực hiện 3 bước sau: _ Tham số hóa bài toán _ Phân tích trường hợp chung: Đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tiến tới trường hợp suy biến _ Tìm trường hợp suy biến 4. Chia để trị Giải thuật chia để trị (Divide and Conquer)là gì ? Phương pháp chia để trị (Divide and Conquer) là một phương pháp quan trọng trong việc thiết kế các giải thuật. Ý tưởng của phương pháp này khá đơn giản và rất dễ hiểu: Khi cần giải quyết một bài toán, ta sẽ tiến hành chia bài toán đó thành các bài toán con nhỏ hơn.
Tiếp tục chia cho đến khi các bài toán nhỏ này không thể chia thêm nữa, khi đó ta sẽ giải quyết các bài toán nhỏ nhất này và cuối cùng kết hợp giải pháp của tất cả các bài toán nhỏ để tìm ra giải pháp của bài toán ban đầu. 9 Nói chung, bạn có thể hiểu giải thuật chia để trị (Divide and Conquer) qua 3 tiến trình sau: Tiến trình 1: Chia nhỏ (Divide/Break) Trong bước này, chúng ta chia bài toán ban đầu thành các bài toán con. Mỗi bài toán con nên là một phần của bài toán ban đầu. Nói chung, bước này sử dụng phương pháp đệ qui để chia nhỏ các bài toán cho đến khi không thể chia thêm nữa.
Khi đó, các bài toán con được gọi là "atomic – nguyên tử", nhưng chúng vẫn biểu diễn một phần nào đó của bài toán ban đầu. Tiến trình 2: Giải bài toán con (Conquer/Solve) Trong bước này, các bài toán con được giải. Tiến trình 3: Kết hợp lời giải (Merge/Combine) Sau khi các bài toán con đã được giải, trong bước này chúng ta sẽ kết hợp chúng một cách đệ qui để tìm ra giải pháp cho bài toán ban đầu. Hạn chế của giải thuật chia để trị (Devide and Conquer) Giải thuật chia để trị tồn tại hai hạn chế, đó là: Làm thế nào để chia tách bài toán một cách hợp lý thành các bài toán con, bởi vì nếu các bài toán con được giải quyết bằng các thuật toán khác nhau thì sẽ rất phức tạp.
Việc kết hợp lời giải các bài toán con được thực hiện như thế nào. 10 BÀI 2: CÁC KIỂU DỮ LIỆU CƠ SỞ Mã bài: MH11 - 02 Giới thiệu: Dữ liệu cơ sở là thành phần quan trọng trong việc tạo ra các chương trình, cũng như tạo ra các kiểu dữ liệu mới. Mục tiêu: _ Hiểu được khái niệm, phạm vi lưu trữ dữ liệu, các phép xử lý của các kiểu dữ liệu cơ sở như: kiểu số, chuỗi, logic, tập hợp,.; _ Sử dụng được các kiểu dữ liệu cơ sở trong việc mô tả các đối tượng trong các ngôn ngữ lập trình bậc cao như C, Pascal; _ Nghiêm túc, tỉ mỉ, sáng tạo trong việc học và vận dụng vào làm bài tập. Nội dung chính: 1.
Các kiểu dữ liệu cơ bản Kiểu số nguyên là kiểu dữ liệu dùng để lưu các giá trị nguyên hay còn gọi là kiểu đếm được. Kiểu số nguyên trong C được chia thành các kiểu dữ liệu con, mỗi kiểu có một miền giá trị khác nhau 1. Kiểu số nguyên 1 byte (8 bits) Kiểu số nguyên một byte gồm có 2 kiểu sau: 1. unsigned char Từ 0 đến 255 (tương đương 256 ký tự trong bảng mã ASCII) 2.
char Từ -128 đến 127 Kiểu unsigned char: lưu các số nguyên dương từ 0 đến 255. => Để khai báo một biến là kiểu ký tự thì ta khai báo biến kiểu unsigned char. Mỗi số trong miền giá trị của kiểu unsigned char tương ứng với một ký tự trong bảng mã ASCII. Kiểu char: lưu các số nguyên từ -128 đến 127.
Kiểu char sử dụng bit trái nhất để làm bit dấu. => Nếu gán giá trị > 127 cho biến kiểu char thì giá trị của biến này có thể là số âm (?). Kiểu số nguyên 2 bytes (16 bits) Kiểu số nguyên 2 bytes gồm có 4 kiểu sau: 1. enum Từ -32,768 đến 32,767 2.
unsigned int Từ 0 đến 65,535 3. short int Từ -32,768 đến 32,767 4. int Từ -32,768 đến 32,767 Kiểu enum, short int, int : Lưu các số nguyên từ -32768 đến 32767. Sử dụng bit bên trái nhất để làm bit dấu.
11 => Nếu gán giá trị >32767 cho biến có 1 trong 3 kiểu trên thì giá trị của biến này có thể là số âm. Kiểu unsigned int: Kiểu unsigned int lưu các số nguyên dương từ 0 đến 65535.