LẬP TRÌNH CĂN BẢN - GIỚI THIỆU VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

88
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các bước giải bài toán bằng máy tính - Mô tả các bước giải bài toán - Vẽ sơ đồ xử lý - Viết chương trình xử lý bằng ngôn ngữ giả - Chọn ngôn ngữ lập trình và chuyển chương trình từ ngôn ngữ giả sang ngôn ngữ lập trình - Thực hiện chương trình: nhập vào các tham số, nhận kết quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LẬP TRÌNH CĂN BẢN - GIỚI THIỆU VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ

1.Từ Bài Toán Đến Chương Trình Các bước giải bài toán bằng máy tính l LẬP TRÌNH CĂN BẢN Mô tả các bước giải bài toán l l Vẽ sơ đồ xử lý l Viết chương trình xử lý bằng ngôn ngữ giả GIỚI THIỆU VỀ CẤU TRÚC DỮ l Chọn ngôn ngữ lập trình và chuyển chương LIỆU VÀ GIẢI THUẬT trình từ ngôn ngữ giả sang ngôn ngữ lập trình l Thực hiện chương trình: nhập vào các tham số, nhận kết quả 3 1 Nội dung 2. Giải Thuật Khái niệm giải thuật Từ bài toán đến chương trình l 1. l Các đặc trưng của giải thuật Giải thuật 2. l Ngôn ngữ biểu diễn giải thuật Kiểu dữ liệu l l Một số giải thuật cơ bản Khái niệm về ngôn ngữ lập trình l l Các cấu trúc suy luận cơ bản của giải thuật Chương trình dịch l l Từ giải thuật đến chương trình 2 4
Khái Niệm Giải Thuật Ngôn Ngữ Biểu Diễn Giải Thuật Ví dụ: Hoán đổi chất lỏng trong 2 bình A (nước Ngôn ngữ tự nhiên l l mắm) và B (rượu): l Ngôn ngữ sơ đồ Yêu cầu phải có thêm một bình thứ ba gọi là bình C. l Bước 1: Đổ rượu từ bình B sang bình C. l Ngôn ngữ giả l Bước 2: Đổ nước mắm từ bình A sang bình B. l Bước 3: Đổ rượu từ bình C sang bình A. l “Giải thuật là một dãy các thao tác trên những dữ l liệu vào sao cho sau một hữu hạn bước ta thu được kết quả của bài toán ”. 5 7 Các Đặc Trưng Của Giải Thuật Ngôn Ngữ Tự Nhiên Tính kết thúc l Là ngôn ngữ của chúng ta l Số bước là hữu hạn l Ví dụ: Giải thuật giải phương trình bậc nhất l Tính xác định l ax+b=0. Máy phải thực hiện được Bước 1: Nhận giá trị của các tham số a, b. l l Cho cùng kết quả trên các máy khác nhau Bước 2: Xét giá trị của a xem có bằng 0 hay không? Nếu a=0 thì làm bước 3, nếu a khác không thì Tính phổ dụng l làm bước 4. l Tính hiệu quả Bước 3: (a bằng 0) Nếu b bằng 0 => pt vô s ố nghiệm. Nếu b khác 0 => pt vô nghiệm. Thời gian l Bước 4: ( a khác 0) Ta kết luận phương trình có l Tài nguyên máy nghiệm x=-b/a. 6 8
Ngôn Ngữ Sơ Đồ (1) Ngôn Ngữ Giả Là một sự kết hợp giữa ngôn ngữ tự nhiên với Mô tả giải thuật bằng các sơ đồ hình khối đã l l các cấu trúc câu lệnh của một ngôn ngữ lập được quy ước trước trình. Ví dụ: Giải thuật giải phương trình bậc nhất l ax+b=0. Nhập vào a, b l l If a==0 then If b==0 then Kết luận phương trình vô số nghiệm else Kết luận phương trình vô nghiệm else Kết luận phương trình có nghiệm x=-b/a 9 11 Ngôn Ngữ Sơ Đồ (2) Một Số Giải Thuật Cơ Bản (1) Ví dụ: Dùng lưu đồ để biểu diễn giải thuật tìm Ví dụ 1: Yêu cầu: l l USCLN như sau: Nhập vào 1 dãy n l số hạng a1, a2, .., an Tính tổng S: l S= a1 + a2 + a3 + ... + an In S ra màn hình l 10 12
Các Cấu Trúc Suy Luận Cơ Bản Một Số Giải Thuật Cơ Bản (2) Của Giải Thuật (2) Cấu trúc lặp (Repeating) Ví dụ 2: Yêu l l cầu: Lặp lại thực hiện một công việc không hoặc l Nhập vào 2 nhiều lần căn cứ vào một điều kiện nào đó. l số a và b là l Có 2 dạng như sau: 2 hệ số của Lặp với số lần xác định l pt: ax+b=0 l Lặp với số lần không xác định Cho biết l nghiệm của phương trình. 13 15 Các Cấu Trúc Suy Luận Cơ Bản Từ Giải Thuật Đến Chương Trình Của Giải Thuật (1) Cả 2 đều là tập các chỉ thị (instruction) – làm Giải thuật được thiết kế theo 3 cấu trúc suy lu ận l l thế nào để giải quyết 1 công việc (task). cơ bản: Giải thuật l Tuần tự (Sequential): l Các công vi ệc được thực hiện tuần tự, công việc này nối tiếp Nói chuyện với con người, dễ hiểu. l l công việc kia. Dùng ngôn ngữ đơn giản (English) – không viết l Cấu trúc lựa chọn (Selection) l bằng mã. Lựa chọn một công việc để thực hiện căn cứ vào một điều kiện l Chương trình l nào đó Cấu trúc 1: Nếu < điều kiện> (đúng) thì thực hiện Nói chuyện với máy tính. l l Cấu trúc 2: Nếu < điều kiện> (đúng) thì thực hiện , ngược lại (điều kiện sai) thì thực hiện expression) của 1 giải thuật. Cấu trúc 3: Trường hợp < i> thực hiện l 14 16
3. Kiểu Dữ Liệu Kiểu Dữ Liệu Có Cấu Trúc “Kiểu dữ liệu có cấu trúc là kiểu dữ liệu Ví dụ: l l mà các giá trị của nó là sự kết hợp của int x,y; float r=3.25; các giá trị khác”. “Kiểu dữ liệu là một tập hợp các giá trị có cùng l một tính chất và tập hợp các phép toán thao Ví dụ : Kiểu chuỗi ký tự trong C. l tác trên các giá trị đó”. là kiểu có cấu trúc. Có 2 loại l l l Ví dụ: char *chuoi = “Chao cac ban!”; Kiểu dữ liệu sơ cấp l Kiểu dữ liệu có cấu trúc l 17 19 Kiểu Dữ Liệu Sơ Cấp 4. Ngôn Ngữ Lập Trình “Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà Khái niệm về ngôn ngữ lập trình l l giá trị của nó là đơn nhất”. l Chương trình dịch Ví dụ: Kiểu int trong C l là kiểu sơ cấp l l gồm các số nguyên từ -32768..32767 l và các phép toán: +, -, *, /, %… 18 20
Hợp Ngữ Khái Niệm Về Ngôn Ngữ Lập Trình (Assembly language) Bao gồm tên và quy tắc viết Ngôn ngữ lập trình là một ngôn ngữ l l các câu lệnh. dùng để viết chương trình cho máy tính Tên các câu lệnh bao gồm l hai phần: AssemblyLanguage l Ta có thể chia ngôn ngữ lập trình thành l Mã lệnh (English) chỉ INPUT a ; Nh ập giá trị cho a các loại sau: phép toán cần thực hiện LOAD a ; Đọc giá trị a vào thanh ghi A l Địa chỉ chứa toán hạng PRINT a; Hiể n thị giá trị củ a a ra màn Ngôn ngữ máy của phép toán đó. l hình. INPUT b l Hợp ngữ Để máy thực hiện được một l ADD b ; Cộng giá trị của thanh ghi tổng chương trình viết bằng hợp A l Ngôn ngữ cấp cao ;v ới giá tr ị b ngữ thì chương trình đó phải được dịch sang ngôn ngữ máy (Assembler). 21 23 Ngôn Cấp Cao Ngôn Ngữ Máy (machine language) (High level language ) Là các chỉ thị dưới dạng Rất gần với ngôn ngữ con l l nhị phân, can thiệp trực người. Machine Language tiếp vào trong các mạch l Một chương trình viết bằng đi ện t ử . ngôn ngữ cấp cao được gọi Có thể được thực hiện là chương trình nguồn l 10100110 01110110 ngay không cần qua (source programs). 00100110 00000000 bước trung gian nào. 11111010 11111010 l Để máy tính "hiểu" và thự c 01001110 10100110 Tuy nhiên chươ ng trình l 11100110 10010110 hiện được các lệnh trong 11001110 00101110 viết bằng ngôn ngữ máy chương trình nguồn thì phải 10100110 01001110 dễ sai sót, cồng kềnh và 11111010 01100110 có một chương trình dịch để 01001110 10000110 khó đọc, khó hiểu vì dịch chương trình ngu ồn etc... toàn những con số 0 và thành dạng chương trình có 3 1. khả năng thự c thi. 22 24
5. Chương Trình Dịch Được dùng để chuyển một chương l trình nguồn sang chương trình đích. l Có 2 dạng: Thông dịch (interpreter): l Dịch từng lệnh một, dịch tới đâu th ực hiện tới đó. l Ví dụ: ngôn ngữ LISP. l Biên dịch (compiler): l Dịch toàn bộ chương trình nguồn thành chương l trình đích rồi sau đó mới thực hiện. Ví dụ: Pascal, C... l 25