Giáo trình Lập trình căn bản (Ngành: Lập trình máy tính - Trình độ: Trung cấp) - Trường Trung cấp Kinh tế - Kỹ thuật Bình Thuận

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:122

Thêm vào BST

Báo xấu

4
lượt xem 0
download

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

Giáo trình "Lập trình căn bản (Ngành: Lập trình máy tính - Trình độ: Trung cấp)" được chia thành 6 chương như sau: Chương 1: Làm quen ngôn ngữ lập trình; Chương 2: Các thành phần trong ngôn ngữ lập trình; Chương 3: Các cấu trúc điều khiển; Chương 4: Hàm và thủ tục; Chương 5: Dữ liệu kiểu tập hợp, mảng và bản ghi; Chương 6: Dữ liệu kiểu chuỗi. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Lập trình căn bản (Ngành: Lập trình máy tính - Trình độ: Trung cấp) - Trường Trung cấp Kinh tế - Kỹ thuật Bình Thuận

TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM TRƯỜNG TRUNG CẤP KINH TẾ - KỸ THUẬT BÌNH THUẬN GIÁO TRÌNH MÔN HỌC: LẬP TRÌNH CĂN BẢN NGÀNH: LẬP TRÌNH MÁY TÍNH TRÌNH ĐỘ: TRUNG CẤP (Ban hành kèm theo Quyết định số:…./QĐ-TC .ngày….tháng…năm 202… của Trường Trung cấp Kinh tế - Kỹ thuật Bình Thuận) Bình Thuận, năm 2023 (Lưu hành nội bộ)
TUYÊN BỐ BẢN QUYỀN Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm.
LỜI GIỚI THIỆU Giáo trình Lập trình căn bản được biên soạn nhằm đáp ứng yêu cầu học tập của sinh viên bước đầu làm quen với công việc lập trình, đồng thời giúp cho sinh viên có một tài liệu học tập, rèn luyện tốt khả năng lập trình, tạo nền tảng vững chắc cho các môn học tiếp theo . Giáo trình không chỉ phù hợp cho người mới bắt đầu mà còn phù hợp cho những người cần tham khảo. Nội dung của giáo trình được chia thành 6 chương: Chương 1: Làm quen ngôn ngữ lập trình Chương 2: Các thành phần trong ngôn ngữ lập trình Chương 3: Các cấu trúc điều khiển Chương 4: Hàm và thủ tục Chương 5: Dữ liệu kiểu tập hợp, mảng và bản ghi Chương 6: Dữ liệu kiểu chuỗi Khi biên soạn, chúng tôi đã tham khảo các giáo trình và tài liệu giảng dạy môn học này của một số trường Trung cấp, Cao đẳng để giáo trình vừa đạt yêu cầu về nội dung vừa thích hợp với đối tượng là sinh viên của các trường Trung cấp. Bên cạnh đó, giáo trình cũng không thể tránh khỏi những sai sót nhất định. Nhóm tác giả rất mong được nhận những ý kiến đóng góp, phản hồi từ quý đồng nghiệp, các bạn, người học và bạn đọc. Trân trọng cám ơn. Bình Thuận, ngày tháng năm 202 Tham gia biên soạn 1. ………………………………………… 2. ………………………………………… 3. ………………………………………… 4. ………………………………………… 5. ………………………………………… 5
MỤC LỤC TRANG CHƯƠNG 1. THUẬT TOÁN ................................................................................................... 14 1. Ví dụ ..................................................................................................................................... 14 2. Khái niệm ............................................................................................................................. 15 3. Các đặc trưng của thuật toán: ................................................................................................ 16 4. Các phương pháp biểu diễn thuật toán ................................................................................... 16 CHƯƠNG 2: GIỚI THIỆU NGÔN NGỮ LẬP TRÌNH C++ ..................................................... 19 1. Lịch sử hình thành................................................................................................................ 20 2. Đặc điểm............................................................................................................................... 19 3. Cấu trúc một chương trình C++ ............................................................................................. 20 4. Một số ví dụ mẫu .................................................................................................................. 21 5. Cài đặt chương trình .............................................................................................................. 23 6. Khởi động chương trình ........................................................................................................ 23 7. Soạn thảo chương trình ......................................................................................................... 23 8. Thoát khỏi chương trình ........................................................................................................ 24 CHƯƠNG 3: CÁC THÀNH PHẦN VÀ CÁC KIỂU DỮ LIỆU CƠ BẢN ................................. 25 1. Các thành phần...................................................................................................................... 25 2. Các kiểu dữ liệu căn bản ....................................................................................................... 30 3. Hằng ..................................................................................................................................... 33 4. Các phép toán của C++ ......................................................................................................... 36 5. Xuất nhập dữ liệu .................................................................................................................. 43 CHƯƠNG 4: CÁC CẤU TRÚC ĐIỀU KHIỂN ........................................................................ 48 1. Lệnh đơn và lệnh phức .......................................................................................................... 48 2. Cấu trúc điều kiện if…else .................................................................................................... 48 3. Cấu trúc lựa chọn switch … case ........................................................................................... 50 4. Các cấu trúc lặp ..................................................................................................................... 52 5. Câu lệnh break, continue, goto và hàm exit ........................................................................... 63 CHƯƠNG 5: HÀM ................................................................................................................... 66 1. Khái niệm ............................................................................................................................. 66 2. Khai báo hàm ........................................................................................................................ 66 3. Kết quả trả về của hàm – lệnh return ..................................................................................... 70 4. Cách truyền tham số cho hàm ................................................................................................ 70 5. Đệ qui ................................................................................................................................... 77 CHƯƠNG 6: MẢNG (ARRAY) ............................................................................................... 81 1. Khái niệm ............................................................................................................................. 81 2. Khai báo mảng ...................................................................................................................... 82 4. Dùng mảng làm tham số ........................................................................................................ 98 6
CHƯƠNG 7: CON TRỎ (POINTER) ......................................................................................108 1. Khái niệm ............................................................................................................................108 2. Toán tử (&) ..........................................................................................................................108 3. Toán tử (*) ...........................................................................................................................109 4. Khai báo biến kiểu con trỏ....................................................................................................109 5. Các phép toán ......................................................................................................................109 6. Con trỏ hằng ........................................................................................................................110 7. Con trỏ mảng .......................................................................................................................110 8. Khởi tạo con trỏ ...................................................................................................................110 9. Con trỏ tới con trỏ ................................................................................................................111 10. Con trỏ không kiểu .............................................................................................................112 11. Con trỏ hàm .......................................................................................................................113 CHƯƠNG 8: CẤU TRÚC (STRUCTURE) .............................................................................115 1. Khái niệm cấu trúc ...............................................................................................................115 2. Khai báo cấu trúc .................................................................................................................115 3. Truy nhập đến các thành phần của cấu trúc ..........................................................................117 4. Ví dụ cấu trúc.......................................................................................................................122 7
GIÁO TRÌNH MÔN HỌC LẬP TRÌNH CĂN BẢN Tên môn học: LẬP TRÌNH CĂN BẢN Mã số môn học: MH11 Thời gian môn học: 90 giờ (Lý thuyết: 15 giờ; Thực hành: 72 giờ; Kiểm tra: 3 giờ) I. VỊ TRÍ, TÍNH CHẤT CỦA MÔN HỌC: * Vị trí: Môn học được bố trí sau khi học xong các môn cơ sở phương pháp tính toán, soạn thảo văn bản, trước các môn học/ mô đun đào tạo chuyên môn nghề. * Tính chất: Là môn học lý thuyết cơ sở bắt buộc. II. MỤC TIÊU MÔN HỌC: Kiến thức:  Trình bày được khái niệm về lập máy tính;  Mô tả được ngôn ngữ lập trình: cú pháp, công dụng của các câu lệnh;  Phân tích được chương trình: xác định nhiệm vụ chương trình; Kỹ năng:  Thực hiện được các thao tác trong môi trường phát triển phần mềm: biên tập chương trình, sử dụng các công cụ, điều khiển, thực đơn lệnh trợ giúp, gỡ rối, bẫy lỗi, v.v.; Năng lực tự chủ và trách nhiệm:  Viết chương trình và thực hiện chương trình trong máy tính.  Bố trí làm việc khoa học đảm bảo an toàn cho người và phương tiện học tập. III. NỘI DUNG MÔN HỌC: 1. Chương trình khung Thời gian đào tạo (giờ) Học kỳ Trong đó Mã Số Thực Tên môn học/ mô Thi/ MH, đun tín Tổng hành/ thực MĐ chỉ số Lý kiể 1 2 3 4 tập/ bài thuyết m tập/ tra thảo luận Các môn học I 15 316 116 183 17 151 165 0 0 chung MH01 Giáo dục Chính trị 2 30 15 13 2 30 MH02 Pháp luật 1 15 9 5 1 15 MH03 Giáo dục thể chất 1 30 4 24 2 30 MH04 Giáo dục QP - AN 2 45 21 21 3 45 8
Thời gian đào tạo (giờ) Học kỳ Trong đó Mã Số Thực Tên môn học/ mô Thi/ MH, đun tín Tổng hành/ thực MĐ chỉ số Lý kiể 1 2 3 4 tập/ bài thuyết m tập/ tra thảo luận MH05 Tin học 2 45 15 28 2 45 MH06 Tiếng Anh 4 90 30 56 4 90 GD SKSS, SK tình MH07 dục và phòng chống 1 16 7 9 16 HIV/AIDS MH08 Kỹ năng mềm 2 45 15 27 3 45 Các môn học, mô II đun đào tạo bắt 47 1.410 332 1.028 50 315 240 405 450 buộc Môn học, mô đun II.1 10 255 72 172 11 255 0 0 0 cơ sở MH09 An toàn lao động 2 30 27 1 2 30 MĐ10 Tin học văn phòng 3 75 15 57 3 75 MH11 Lập trình căn bản 3 90 15 72 3 90 MĐ12 Phần cứng máy tính 2 60 15 42 3 60 Môn học, mô đun II.2 37 1.155 260 856 39 60 240 405 450 chuyên môn Cấu trúc dữ liệu và MH13 2 60 25 32 3 60 giải thuật Lập trình hướng đối MH14 2 60 25 32 3 60 tượng MH15 Cơ sở dữ liệu 3 90 25 62 3 90 MĐ16 Đồ họa ứng dụng 3 90 15 72 3 90 MH17 Mạng căn bản 2 60 25 33 2 60 Tiếng Anh chuyên MH18 2 60 25 32 3 60 ngành MĐ19 Thiết kế Web 3 90 15 71 4 90 MĐ20 Lập trình Windows 4 105 25 76 4 105 MĐ21 Lập trình Web 3 90 25 61 4 90 MĐ22 Lập trình quản lý 3 90 25 61 4 90 MĐ23 PHP & MySQL 3 90 15 72 3 90 MĐ24 Quản trị mạng 3 90 15 72 3 90 Thực tập nghề MĐ25 4 180 180 180 nghiệp tại cơ sở Tổng cộng 62 1.726 448 1.211 67 466 405 405 450 9
2. Chương trình chi tiết môn học Thời gian Số Thực Kiểm Tên chương, mục Lý TT Tổng số hành tra* thuyết Bài tập Thuật toán Ví dụ I. Khái niệm 4 1 3 Các đặc trưng của thuật toán Phương pháp biểu diễn Giới thiệu ngôn ngữ lập trình C Lịch sử hình thành Đặc điểm Cấu trúc của một chương trình C II. Một số ví dụ mẫu 6 2 4 Cài đặt chương trình Khởi động chương trình Soạn thảo chương trình Thoát khỏi chương trình Các thành phần và các kiểu dữ liệu cơ bản CÁC THÀNH PHẦN VÀ CÁC KIỂU DỮ Các thành phần III. Các kiểu dữ liệu căn bản 8 2 6 Hằng Các phép toán của C Xuất nhập dữ liệu Các cấu trúc điều khiển Lệnh đơn và lệnh phức Cấu trúc điều kiện: if ... else IV. Cấu trúc lựa chọn: switch..case 13 3 9 1(TH) Các cấu trúc lặp Câu lệnh break, continue, goto và hàm exit Hàm Khái niệm Khai báo hàm V. Kết quả trả về của hàm 12 2 10 Lệnh return Cách truyền tham số cho hàm Đệ qui Mảng Khái niệm VI. Khai báo mảng 15 2 12 1(LT) Khởi tạo mảng Dùng mảng làm tham số Con trỏ VII. 17 1 16 Khái niệm 10
Toán tử lấy địa chỉ(&) Toán tử tham chiếu(*) Khai báo biến kiếu con trỏ Các phép toán Con trỏ hằng Con trỏ mảng Khởi tạo con trỏ Con trỏ trỏ tới con trỏ Con trỏ không kiểu Con trỏ hàm Cấu trúc Khái niệm cấu trúc Khai báo cấu trúc VIII. 15 2 12 1(TH) Truy cập đến các thành phần của cấu trúc Ví dụ cấu trúc Cộng 90 15 72 3 IV. ĐIỀU KIỆN THỰC HIỆN MÔN HỌC: - Phòng học chuyên môn hóa, nhà xưởng: + Xưởng thực hành đạt chuẩn. + CD ROM chương trình phần mềm ngôn ngữ lập trình (C). + Giấy A0, bút lông. - Trang thiết bị máy móc: + Máy tính, máy chiếu. - Học liệu, dụng cụ, nguyên vật liệu: + Bài giảng soạn trên phần mềm dạy học. + Phần mềm kiểm tra trắc nghiệm. - Các điều kiện khác: + Phòng học thực hành máy tính đạt chuẩn. V. NỘI DUNG VÀ PHUƠNG PHÁP ĐÁNH GIÁ: 1. Nội dung: - Về kiến thức: + Được đánh giá qua bài kiểm tra viết, trắc nghiệm đạt được các yêu cầu sau: a. Phân tích chương trình: Để xác định dữ liệu và nhiệm vụ chương trình (phải làm gì), bao gồm: - Xác định các công việc và kế hoạch cần thực hiện. - Mô tả chi tiết, tần suất và khối lượng kết quả đưa ra. - Xác định dữ liệu đưa vào hệ thống và (cấu trúc dữ liệu) dữ liệu lưu trữ để tạo kết quả đầu ra hệ thống. - Xác định các điều khiển cần phải thiết kế đưa vào hệ thống để đảm bảo hệ thống làm việc chính xác và tin cậy. b. Thiết kế chương trình: tìm giải pháp kỹ thuật (làm thế nào) đối với những công việc đặt ra trong giai đoạn phân tích, bao gồm: - Xác định trang, thiết bị cần thiết để hệ thống hoạt động. 11
- Biểu đồ hệ thống: diễn tả mối liên quan, tác động giữa các khối, mô đun chương trình, dữ liệu đưa vào, các tệp lưu trữ, và kết quả đưa ra. - Thiết kế mẫu thu thập dữ liệu. - Phương tiện, quy cách đưa dữ liệu vào hệ thống. - Quy cách các bản ghi dữ liệu. - Xác định các điều khiển áp dụng cho việc nhập dữ liệu đảm bảo đã được xử lý, kiểm tra chính xác. - Mô tả chức năng và viết chương trình logic (pseudo code) của từng mô đun xử lý và của hệ thống. c. Viết chương trình - Chọn ngôn ngữ lập trình thích hợp theo nhiệm vụ của hệ thống. - Vận dụng điều kiện, trợ giúp môi trường của ngôn ngữ lập trình, chẳng hạn: các thao tác biên tập chương trình, các công cụ, điều khiển, thực đơn lệnh trợ giúp, gỡ rối, bẫy lỗi,v.v. - Mô tả hằng và biến dùng trong chương trình: định nghĩa kiểu hằng, kiểu biến, tên biến và chú ý phạm vi tác dụng (cục bộ hay toàn thể) của từng biến và hằng. - Vận dụng quy tắc cú pháp của ngôn ngữ, các hoạt động vào/ra, lựa chọn biểu thức lồng nhau (đệ quy), tuần tự tuyến tính. - Vận dụng các phương pháp lặp điều kiện trước hoặc sau, đảm bảo điều kiện kết thúc của vòng lặp (không quẩn và bị lặp vô hạn). - Chương trình có chú thích cho từng đoạn xử lý, dễ theo dõi: dòng nhô ra, lùi vào theo chức năng xử lý. Đặt tên chương trình, tên biến, tên hằng diễn tả được ý nghĩa và chức năng của chúng. d. Dịch và chạy chương trình: Dịch và sửa các lỗi cú pháp. Chạy và hiệu chỉnh chương trình. e. Thử nghiệm chương trình: - Sử dụng bộ dữ liệu: thử nghiệm các giai đoạn, phân tích giá trị biến qua từng đoạn mã (mô đun chương trình). - Sử dụng công cụ: dùng Debugger của hệ thống để phân tích biến và cấu trúc dữ liệu tương ứng. - Kỹ năng: - Đánh giá kỹ năng thực hành của học sinh trong bài thực hành đạt được các yêu cầu sau: - Xác định các công việc và kế hoạch cần thực hiện. - Mô tả chi tiết, tần xuất và khối lượng kết quả đưa ra. - Xác định bao gồm: dữ liệu đưa vào hệ thống và dữ liệu lưu trữ để tạo kết quả đầu ra. - Xác định trang, thiết bị đối với hệ thống. - Biểu đồ hệ thống: diễn tả mối liên quan, tác động giữa các mô đun chương trình, dữ liệu đưa vào, các tệp lưu trữ, và kết quả đưa ra. - Thiết kế mẫu thu thập dữ liệu. - Phương tiện, quy cách đưa dữ liệu vào hệ thống. - Quy cách bản ghi dữ liệu. - Xác định các điều khiển áp dụng cho việc nhập dữ liệu đảm bảo chính xác, có chu trình xử lý dữ liệu. 12
- Mô tả chức năng và viết giả trình logic (Pseudo code) của từng mô đun chương trình và hệ thống. - Sử dụng các công cụ trong môi trường ngôn ngữ lập trình: Debugger kiểm soát phạm vi và giá trị của biến dùng trong chương trình. - Kiểm tra giá trị tính toán của biểu thức qua các mô đun chương trình. - Kiểm tra các giá trị vào/ra . - Xác định môi trường hoạt động của hệ thống (các điều khiển, công cụ, các thành phần, tập hợp dữ liệu ...). Nhập dữ liệu, in kết quả. Năng lực tự chủ và trách nhiệm: - Rèn luyện kỹ năng phân tích, tổng hợp, cẩn thận, thao tác chuẩn xác. - Rèn luyện thao tác cẩn thận, chính xác, tỉ mỉ, chu đáo. 2. Phương pháp đánh giá: - Trắc nghiệm; - Thực hành trên máy tính. VI. HƯỚNG DẪN THỰC HIỆN MÔN HỌC: 1. Phạm vi áp dụng mô đun: - Chương trình môn học được sử dụng để giảng dạy cho trình độ trung cấp. - Giáo viên trước khi giảng dạy cần phải căn cứ vào nội dung của từng bài học chuẩn bị đầy đủ các điều kiện thực hiện bài học để đảm bảo chất lượng giảng dạy. 2. Hướng dẫn về phương pháp giảng dạy, học tập môn học: - Đối với giáo viên, giảng viên: - Giáo viên trước khi giảng dạy cần phải căn cứ vào nội dung của từng bài học chuẩn bị đầy đủ các điều kiện thực hiện bài học để đảm bảo chất lượng giảng dạy. - Đối với người học: - Phân nhóm cho các sinh viên trao đổi với nhau, trình bày theo nhóm. 3. Những trọng tâm cần chú ý: - Phân tích được chương trình: xác định nhiệm vụ chương trình (phải làm gì). - Vận dụng điều kiện, trợ giúp môi trường của ngôn ngữ lập trình, chẳng hạn: các thao tác biên tập chương trình, các công cụ, điều khiển, thực đơn lệnh trợ giúp, gỡ rối, bẫy lỗi,v.v. - Viết chương trình và thực hiện chương trình trong máy tính - Giáo viên trước khi giảng dạy cần phải căn cứ vào nội dung của từng bài học - Chuẩn bị đầy đủ các điều kiện thực hiện bài học để đảm bảo chất lượng giảng dạy. 4. Tài liệu tham khảo: [1] H. M Deitel and P. J. Deitel, C How to Program, Prentice-Hall, 3rd Edition, 2001 [2] GS Phạm Văn Ất, Lập trình C, NXB Khoa học - kỹ thuật. 13
CHƯƠNG 1 THUẬT TOÁN Mã chương: MH11_CH01 Mục tiêu: - Trình bày được các khái niệm về lập trình; - Trình bày các phương pháp biểu diễn thuật toán; - Trình bày được thuật toán cho một vấn đề cụ thể - Thực hiện các thao tác an toàn với máy tính. Nội dung chính: Chương 1. THUẬT TOÁN 1. Ví dụ Có rất nhiều thuật toán trong tin học, chẳng hạn, cho một dãy các số nguyên, tìm số lớn nhất; cho một tập hợp, liệt kê các tập con của nó; cho tập hợp các số nguyên, xếp chúng theo thứ tự tăng dần; cho một mạng, tìm đường đi ngắn nhất giữa hai đỉnh của nó. Khi được giao cho một bài toán như vậy thì việc đầu tiên phải làm là xây dựng một mô hình dịch bài toán đó thành ngữ cảnh toán học. Các cấu trúc rời rạc được dùng trong các mô hình này là tập hợp, dãy, hàm, hoán vị, quan hệ, cùng với các cấu trúc khác như đồ thị, cây, mạng. Lập được một mô hình toán học thích hợp chỉ là một phần của quá trình giảA. Để hoàn tất quá trình giải, còn cần phải có một phương pháp dùng mô hình để giải bài toán tổng quát. Nói một cách lý tưởng, cái được đòi hỏi là một thủ tục, đó là dãy các bước dẫn tới đáp số mong muốn. Một dãy các bước như vậy, được gọi là một thuật toán. Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đó, ta cần phải đưa ra phương pháp giải quyết mà thực chất đó là thuật toán giải quyết vấn đề này. Rõ ràng rằng, nếu không tìm được một phương pháp giải quyết thì không thể lập trình được. Chính vì thế, thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học. 14
2. Khái niệm Thuật toán là một bảng liệt kê các chỉ dẫn (hay quy tắc) cần thực hiện theo từng bước xác định nhằm giải một bài toán đã cho. Thuật ngữ “Algorithm” (thuật toán) là xuất phát từ tên nhà toán học Ả Rập Al- KhowarizmA. Ban đầu, từ algorism được dùng để chỉ các quy tắc thực hiện các phép tính số học trên các số thập phân. Sau đó, algorism chuyển thành algorithm vào thế kỷ 19. Với sự quan tâm ngày càng tăng đối với các máy tính, khái niệm thuật toán đã được cho một ý nghĩa chung hơn, bao hàm cả các thủ tục xác định để giải các bài toán, chứ không phải chỉ là thủ tục để thực hiện các phép tính số học. Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên, ngôn ngữ lưu đồ (sơ đồ khối), ngôn ngữ lập trình. Tuy nhiên, một khi dùng ngôn ngữ lập trình thì chỉ những lệnh được phép trong ngôn ngữ đó mới có thể dùng được và điều này thường làm cho sự mô tả các thuật toán trở nên rối rắm và khó hiểu. Hơn nữa, vì nhiều ngôn ngữ lập trình đều được dùng rộng rãi, nên chọn một ngôn ngữ đặc biệt nào đó là điều người ta không muốn. Vì vậy ở đây các thuật toán ngoài việc được trình bày bằng ngôn ngữ tự nhiên cùng với những ký hiệu toán học quen thuộc còn dùng một dạng giả mã để mô tả thuật toán. Giả mã tạo ra bước trung gian giữa sự mô tả một thuật toán bằng ngôn ngữ thông thường và sự thực hiện thuật toán đó trong ngôn ngữ lập trình. Các bước của thuật toán được chỉ rõ bằng cách dùng các lệnh giống như trong các ngôn ngữ lập trình. Thí dụ 1: Mô tả thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên. a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện: 1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. (Cực đại tạm thời sẽ là số nguyên lớn nhất đã được kiểm tra ở một giai đoạn nào đó của thủ tục.) 2. So sánh số nguyên tiếp sau với giá trị cực đại tạm thời, nếu nó lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó. 3. Lặp lại bước trước nếu còn các số nguyên trong dãy. 4. Dừng khi không còn số nguyên nào nữa trong dãy. Cực đại tạm thời ở điểm này chính là số nguyên lớn nhất của dãy. b) Dùng đoạn giả mã: procedure max (a1, a2, ..., an: integers) max:= a1 for i:= 2 to n if max
Thuật toán này trước hết gán số hạng đầu tiên a 1 của dãy cho biến max. Vòng lặp “for” được dùng để kiểm tra lần lượt các số hạng của dãy. Nếu một số hạng lớn hơn giá trị hiện thời của max thì nó được gán làm giá trị mới của max. 3. Các đặc trưng của thuật toán: - Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ. - Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán. - Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. - Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn, trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau. - Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn. - Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ liệu khác nhau trong một miền xác định. 4. Các phương pháp biểu diễn thuật toán 4.1. Bằng lời Thí dụ: thuật giải nấu cơm có thể diễn đạt như sau: Bước 1: Lấy gạo theo định lượng cần thiết Bước 2: Vo gạo và đổ gạo nước vào nồi Bước 3: Đun sôi cạn nước Bước 4: Giữ lửa nhỏ Bước 5: Cách 5 phút một: nếm cơm xem chín chưa - Nếu chưa chín: quay về bước 5 - Nếu chín cơm chuyển sang bước 6 Bước 6: Tắt lửa và bắc nồi cơm ra. Kết thúc 4.2. Bằng ngôn ngữ lập trình Một thuật toán có thể được cài đặt trên rất nhiều ngôn ngữ lập trình khác nhau, ví dụ như Pascal, C, C++…Trong đó Pascal là một trong các ngôn ngữ thuật giải, nghĩa là tự nó đã điễn tả thuật giải cần tiến hành, đó cũng là ưu điểm của Pascal. Ngoài ra cài đặt thuật toán còn được diễn đạt thành mã giả hay còn gọi là tự Pascal. Như vậy, còn C và C++ có những ưu điểm gì trong quá trình cài đặt thuật giải, chúng ta sẽ được nghiên cứu trong qúa trình học. Ví dụ: Thuật toán tìm kiếm tuyến tính: Tìm kiếm tuyến tính hay tìm kiếm tuần tự là bắt đầu bằng việc so sánh x với a1; khi x=a1, nghiệm là vị trí a1, tức là 1; khi 16
xa1, so sánh x với a2. Nếu x=a2, nghiệm là vị trí của a2, tức là 2. Khi xa2, so sánh x với a3. Tiếp tục quá trình này bằng cách tuần tự so sánh x với mỗi số hạng của bảng liệt kê cho tới khi tìm được số hạng bằng x, khi đó nghiệm là vị trí của số hạng đó. Nếu toàn bảng liệt kê đã được kiểm tra mà không xác định được vị trí của x, thì nghiệm là 0. Giả mã đối với thuật toán tìm kiếm tuyến tính được cho dưới đây: procedure tìm kiếm tuyến tính (x: integer, a1,a2,...,an: integers phân biệt) i := 1 while (i  n and x  ai) i := i + 1 if i  n then location := i else location := 0 {location là chỉ số dưới của số hạng bằng x hoặc là 0 nếu không tìm được x} 4.3. Bằng lưu đồ Các hình cơ bản để xây dựng lưu đồ thuật giải là: A A A Thực hiện công việc A Gọi chương trình A Vào/ra dữ liệu BEGIN Sai B END Đúng Một phép thử B. tuỳ thuộc vào Bắt đầu hay kết thúc 1 thuật giải trạng thái của B là Đúng hay Sai mà rẽ nhánh thích hợp. BÀI TẬP CHƯƠNG I 1. Lập một thuật toán tính tổng tất cả các số nguyên trong một bảng. 2. Lập thuật toán tính xn với x là một số thực và n là một số nguyên. 17
3. Mô tả thuật toán chèn một số nguyên x vào vị trí thích hợp trong dãy các số nguyên a1, a2, ..., an xếp theo thứ tự tăng dần. 4. Tìm thuật toán xác định vị trí gặp đầu tiên của phần tử lớn nhất trong bảng liệt kê các số nguyên, trong đó các số này không nhất thiết phải khác nhau. 5. Tìm thuật toán xác định vị trí gặp cuối cùng của phần tử nhỏ nhất trong bảng liệt kê các số nguyên, trong đó các số này không nhất thiết phải khác nhau. 6. Mô tả thuật toán đếm số các số 1 trong một xâu bit bằng cách kiểm tra mỗi bit của xâu để xác định nó có là bit 1 hay không. 18
CHƯƠNG 2 GIỚI THIỆU NGÔN NGỮ LẬP TRÌNH C++ Mã chương: MH11_CH02 Mục tiêu: - Mô tả được lịch sử hình thành và phát triển của ngôn ngữ C++. - Hiểu được cấu trúc của một chương trình C++. - Cài đặt và sử dụng được chương trình C++. - Soạn thảo được một chương trình C++. - Thực hiện các thao tác an toàn với máy tính Nội dung chính: CHƯƠNG 2: GIỚI THIỆU NGÔN NGỮ LẬP TRÌNH C++ 1. Lịch sử hình thành •C – Dennis Ritchie (Bell Laboratories) – Là ngôn ngữ phát triển của hệ điều hành UNIX – Độc lập phần cứng => có thể viết các chương trình khả chuyển – Chuẩn hóa năm 1990 – ANSI C – Kernighan & Ritchie “The C Programming Language”, 2nd, 1988 • C++ – Là mở rộng của C – Đầu những năm 1980: Bjarne Stroustrup (phòng thí nghiệm Bell) – Cung cấp khả năng lập trình hướng đối tượng. – Ngôn ngữ lai • Lập trình cấu trúc kiểu C • Lập trình hướng đối tượng • Cả hai • Có cần biết C trước khi học C++? 2. Đặc điểm C++ là ngôn ngữ lập trình hướng đối tượng được mở rộng từ ngôn ngữ C. Do vậy, C++ có ưu điểm là kế thừa được các điểm mạnh truyền thống của ngôn ngữ C như uyển chuyển, tương thích với các thiết bị phần cứng. Hiện nay, C++ là một ngôn ngữ lập trình phổ biến, được giảng dạy tại các trường đại học trong nước và 19
trên thế giới và đặc biệt được sử dụng rộng rãi cho nhu cầu phát triển của công nghiệp phần mềm hiện nay. 3. Cấu trúc một chương trình C++ Một chương trình C++ có thể được đặt trong một hoặc nhiều file văn bản khác nhau. Mỗi file văn bản chứa một số phần nào đó của chương trình. Với những chương trình đơn giản và ngắn thường chỉ cần đặt chúng trên một file. Một chương trình gồm nhiều hàm, mỗi hàm phụ trách một công việc khác nhau của chương trình. Đặc biệt trong các hàm này có một hàm duy nhất có tên hàm là main(). Khi chạy chương trình, các câu lệnh trong hàm main() sẽ được thực hiện đầu tiên. Trong hàm main() có thể có các câu lệnh gọi đến các hàm khác khi cần thiết, và các hàm này khi chạy lại có thể gọi đến các hàm khác nữa đã được viết trong chương trình (trừ việc gọi quay lại hàm main()). Sau khi chạy đến lệnh cuối cùng của hàm main() chương trình sẽ kết thúc. Cụ thể, thông thường một chương trình gồm có các nội dung sau: − Phần khai báo các tệp nguyên mẫu: khai báo tên các tệp chứa những thành phần có sẵn (như các hằng chuẩn, kiểu chuẩn và các hàm chuẩn) mà NSD sẽ dùng trong chương trình. − Phần khai báo các kiểu dữ liệu, các biến, hằng ... do NSD định nghĩa và được dùng chung trong toàn bộ chương trình. − Danh sách các hàm của chương trình (do NSD viết, bao gồm cả hàm main()). Cấu trúc chi tiết của mỗi hàm sẽ được đề cập đến trong chương 4. Dưới đây là một đoạn chương trình đơn giản chỉ gồm 1 hàm chính là hàm main(). Nội dung của chương trình dùng in ra màn hình dòng chữ: Chào các bạn, bây giờ là 2 giờ. #include // khai báo tệp nguyên mẫu để int main() // được sử dụng toán tử in cout
Không riêng hàm main(), mọi hàm khác đều phải bắt đầu tập hợp các câu lệnh của mình bởi dấu { và kết thúc bởi dấu }. Tập các lệnh bất kỳ bên trong cặp dấu này được gọi là khối lệnh. Khối lệnh là một cú pháp cần thiết trong các câu lệnh có cấu trúc như ta sẽ thấy trong các chương tiếp theo. 4. Một số ví dụ mẫu Có lẽ một trong những cách tốt nhất để bắt đầu học một ngôn ngữ lập trình là bằng một chương trình. Vậy đây là chương trình đầu tiên của chúng ta : // my first program in C++ Hello World! #include int main () { cout
Dòng này tương ứng với phần bắt đầu khai báo hàm main. Hàm main là điểm mà tất cả các chương trình C++ bắt đầu thực hiện. Nó không phụ thuộc vào vị trí của hàm này (ở đầu, cuối hay ở giữa của mã nguồn) mà nội dung của nó luôn được thực hiện đầu tiên khi chương trình bắt đầu. Thêm vào đó, do nguyên nhân nói trên, mọi chương trình C++ đều phải tồn tại một hàm main. Theo sau main là một cặp ngoặc đơn bởi vì nó là một hàm. Trong C++, tất cả các hàm mà sau đó là một cặp ngoặc đơn () thì có nghĩa là nó có thể có hoặc không có tham số (không bắt buộc). Nội dung của hàm main tiếp ngay sau phần khai báo chính thức được bao trong các ngoặc nhọn ( { } ) như trong ví dụ của chúng ta cout