Bài giảng Môn học Phương pháp lập trình

MÔN HỌC PHƯƠNG PHÁP LẬP TRÌNH Giới thiệu Mục tiêu môn học Cung cấp cho sinh viên kiến thức căn bản về kỹ thuật lập trình và lập trình theo tiếp cận hướng đối tượng, một phương pháp lập trình rất thông dụng hiện nay. Nội dung Một số thuật ngữ liên quan đến máy tính và lập trình. Sơ lược về ngôn ngữ lập trình Ngôn ngữ minh họa Pseudo code và C/C++ Các giải thuật cơ bản Kỹ năng tư duy và thực hành trên ngôn ngữ cụ thể. Phương thức Phương thức học Giờ lý thuyết: giảng và báo cáo Giờ thực hành tại phòng máy Kiểm tra và thi Kiểm tra thực hành: kỹ năng lập trình Thi lý thuyết : trắc nghiệm khách quan Tài liệu tham khảo Slide bài giảng Lập Trình Căn Bản Giáo trình Phương Pháp Lập trình – Khoa CNTT Tài liệu khác CDROM bài tập và thực hành Chương 1 Khái niệm cơ bản Một số khái niệm cơ bản về Máy tính & chương trình máy tính Ngôn ngữ lập trình ,translator,.. Giải thuật và flow chart Giải thuật & biểu diễn giải thuật Flowchart Công cụ phát triển Công cụ IDE, Compiler Error & debug Máy tính - Computer Máy tính Analog Máy tính số Hệ nhị phân Máy tính lập trình được Mô hình máy Turing và Von Newman Các thế hệ máy tính Đặc tính chung Khả năng tính toán Khả năng thực hiện các phép toán logic Tốc độ tính toán cao Làm theo chỉ thị Kiến trúc máy tính Máy tính (Computer system) Bao gồm nhiều thiết bị phần cứng (hardware devices) Keyboard Screen (monitor) Disks Memory Processing Units Hệ điều hành (Operating System – OS) Phần mềm (software) Công dụng: êệ thống, ứng dụng, cơ sở dữ liệu Môi trường hoạt động: OS, Network, WEB, Server,.. Chương trình máy tính Chương trình Danh mục các trang thiết bị, tài nguyên sử dụng Tiến trình sử dụng các tài nguyên và thực hiện các công việc định trước Kết quả thực hiện Chương trình máy tính Tập hợp các lệnh được liệt kê theo một trình tự nhất định Các dữ liệu sẽ được nhận Các tài nguyên cần sử dụng Các kết quả sẽ có được Mục tiêu: xử lý dữ liệu theo yêu cầu định trước Lập trình: viết chương trình cho máy tính Ngôn ngữ lập trình Ngôn ngữ lập trình Phương tiện để viết chương trình cho máy tính Hàng trăm ngôn ngữ lập trình khác nhau Những quy định về cú pháp (syntax) & ngữ nghĩa (semantic) Máy tính có thể hiểu được Phân chia làm 3 nhóm chính Ngôn ngữ máy - Machine languages Ngôn ngữ duy nhất của máy tính - CPU Hợp ngữ - Assembly languages Ngôn ngữ cấp cao - High-level languages Ngôn ngữ máy - Machine languages Ngôn ngữ duy nhất được máy tính (CPU) hiểu trực tiếp. Được xác định bởi tập lệnh của CPU Phụ thuộc vào máy tính cụ thể Dạng nhị phân {0,1}* Rất khó đọc hiểu Khó có khả năng viết chương trình trực tiếp Khó nhớ hàng chục ngàn lệnh dạng {0,1}* Rất khó xác định & sửa lỗi Không được sử dụng trong thực tế để viết chương trình Nền tảng xây dựng hợp ngữ Hợp ngữ - Assembly Languages Sử dụng các từ khóa tiếng Anh cho các lệnh hay nhóm lệnh của mã máy. Được dịch sang mã máy khi thực hiện Chuyển đỗi nhanh chóng Dễ đọc và dễ hiểu hơn Vẫn tương đối khó sử dụng do Các lệnh còn đơn giản nên phải dùng nhiều lệnh. Chưa có những cấu trúc điều khiển thuận tiện Khả năng tìm và sửa lỗi cũng chưa thuận tiện. Nền tảng xây dựng các ngôn ngữ cấp cao Ngôn ngữ cấp cao Một câu lệnh diễn tả nhiều động thái Có cấu trúc ngày càng giống ngôn ngữ tự nhiên (tiếng Anh) Được dịch sang assembly hay mã máy bằng các chương trình dịch trước khi thực thi. Source code & Executed code Được phân làm nhiều lớp Lập trình goto Lập trình cấu trúc – Structured Lập trình hướng đối tượng – Object Oriented Các dạng khác Học ngôn ngữ lập trình Học ngữ pháp Quy tắc ngữ pháp Từ vựng Cấu trúc câu Ngữ nghĩa của các lệnh Các “thành ngữ” Học ngôn ngữ lập trình VS. Học ngôn ngữ tự nhiên Quy tắc ngữ pháp đơn giản Từ vựng ít, tự quy định Cấu trúc câu đơn giản Hạn chế và khó khăn của sử dụng ngôn ngữ lập trình. Chương trình dịch Dùng để dịch từ một ngôn ngữ lập trình này sang ngôn ngữ lập trình khác Mục tiêu cuối cùng là dịch sang mã máy để có được executed code –> chương trình thực thi Phân loại: Intepreter – thông dịch Compiler – biên dịch Intepreter vs. Compiler Công cụ phát triển – Integrated Development Environment (IDE) Soạn thảo Dịch và sửa lỗi chương trình Chạy thử và sửa lỗi Một số khái niệm khác Lỗi và sửa lỗi Syntax error – lỗi ngữ pháp Semantic error- lỗi ngữ nghĩa Runtime error - Lỗi thực thi Debug – Tìm và sửa lỗi Dữ liệu, kiểu dữ liệu Các kiểu dữ liệu cơ bản Số nguyên, Số thực, Kí tự Kiểu dữ liệu có cấu trúc: mảng, chuỗi, cấu trúc,.. Biến (Variable) & Hằng (Constant) Giải thuật: khái niệm, công cụ biểu diễn Flow chart – lưu đồ Flow chart Start Start /Begin bắt đầu giải thuật. Chỉ có 1 và chỉ 1 điểm START. Input / Output dữ liệu xuất/nhập Dòng xử lý Đặc tả thao tác xử lý hay tính toán dữ liệu Điều khiển rẽ nhánh Điều kiện Yes No Phát biểu rẽ nhánh khác Giá trị xét phân nhánh Trường hợp 1 Trường hợp i Khác Stop Stop/End kết thúc của giải thuật. Có thể có một hoặc nhiều điểm STOP. Flow chart Ưu điểm Trình bày trực quan giải thuật Độc lập với ngôn ngữ tự nhiên Độc lập với ngôn ngữ lập trình Bảo đảm khả năng lập trình Cho phép dễ dàng kiểm tra giải thuật Nguyên tắc kiểm tra Đi từ START theo bất cứ đường nào cũng phải đến một điểm dừng STOP Không có sự quay vòng vĩnh viễn Không có sự kết thúc lưng chừng Flow chart Start Nhập a, b a=0 ? Yes No b=0 ? Yes No X=-b/a Không có nghiệm Vô số nghiệm Stop Algorithms Giải phương trình ax + b = 0 Cấu trúc lệnh cơ bản if (condition) Statement; if (condition) Statement 1; else Statement 2; switch(BiểuThứcChọn) { case hằng 1: S1;break; case hằng 2: S2;break; ……. case hằng n: Sn;break; default: S0; } while (condition) Statement; do{ Statement }while (condition); for (BT1; ĐK ; BT2) Statement; Chu kỳ sống của phần mềm Thu thập yêu cầu Phân tích thiết kế Phát triển chương trình - codeing Xác định giải thuật Viết code và dịch thử , hiệu chỉnh các lỗi syntax Thử nghiệm - Testing Chạy thử với các dữ liệu mẫu để kiểm tra lỗi semantic và runtime Vận hành và bảo trì Phát triển theo yêu cầu Một số ngôn ngữ lập trình Lập trình goto Assembly Basic Lập trình cấu trúc Pascal, C Foxpro Lập trình hướng đối tượng Java, C++, Object Pascal,… Khác Prolog, LISP, Visual basic (VB), VC++, J++, Delphi, ASP, PHP,.. Visual studio .NET: VB.NET, ASP.NET, C++.NET, C# Chương 2Dữ liệu & cấu trúc chương trình Các khái niệm cơ bản về dữ liệu và biểu diễn dữ liệu trong máy tính Khai báo dữ liệu trong chương trình Một số phép toán cơ bản Cấu trúc cơ bản một chương trình C/C++ Danh hiệu Khái niệm “Danh hiệu” Là tên của các đối tượng khác nhau trong lập trình, dùng để phân biệt giữa đối tượng này với đối tượng khác. Các đối tượng thường được đặt tên bằng danh hiệu: biến, hằng, chương trình con, …… Qui tắc ngữ pháp của danh hiệu: Bắt đầu bằng chữ cái (A-Z, a-z) hay dấu gạch dưới ( _ ) Theo sau là chữ cái, dấu gạch dưới hay chữ số. Với Pascal không phân biệt CHỮ HOA hay chữ thường Một số ngôn ngữ có phân biệt như Java,… Ví dụ: X , BienDem, Bien_dem, X1 , X2 , X3 , x1,x2,x3 Ví dụ sai: 101X3, (X1), Bien Dem Danh hiệu (tt) Danh hiệu gồm 2 loại: Danh hiệu thuộc ngôn ngữ (Pre-defined) Do ngôn ngữ quy định trước ý nghĩa của nó. Được dùng cho các đối tượng có sẵn trong ngôn ngữ Ví dụ: int, cin, cout,… Danh hiệu do người sử dụng đặt ra (user defined) Do người sử dụng tự qui ước và qui định ý nghĩa của nó trong chương trình nguồn (source code) Ví dụ: abc, xyz1, xyz2, delta, namsinh, tinh_giai_thua Từ dành riêng: Là những từ do ngôn ngữ quy định sẵn như là một bộ phận cấu thành ngôn ngữ đó. Ví dụ: if, else, do, while Ký hiệu đặc biệt: là những ký tự có ý nghĩa được quy định trước trong ngôn ngữ. Ví dụ: + - * / > >= := ; , ( ) @ [ ] Qui ước đặt tên danh hiệu Qui tắc đặt tên danh hiệu Tuân thủ quy tắc ngữ pháp của danh hiệu Không được trùng lắp với danh hiệu thuộc ngôn ngữ hoặc đã được định nghĩa. Nên sử dụng các tên gợi nhớ Tên gợi nhớ? Tên mà khi đọc đến sẽ giúp ta biết được ý nghĩa của đối tượng mang tên đó. Lợi ích của tên gợi nhớ: giúp chương trình dễ đọc, dễ hiểu & dể kiểm tra. if (ABC , = cho kết quả bằng 0 hoặc 1 ( ‘a’ > ‘B’ ) có giá trị bằng 0 Các phép toán logic !, &&, || Các phép toán số học: +, - , * , /, % Phép gọi hàm: gọi một chương trình con loại hàm số tương đương với một phép toán Biểu thức: là một công thức tính toán tạo từ các biến, hằng, các giá trị cụ thể, các phép toán và dấu (, ) . Kiểu dữ liệu trả về cũng là kiểu dữ liệu của biểu thức. A+2*b(c-d) Biến là một biểu thức Phát biểu gán và thủ tục xuất nhập Phát biểu gán = Gán một giá trị của một biểu thức cho một biến TenBien = Bieuthuc; Các thao tác xuất nhập: cin>>B1>>B2; cout>a>>b ; 12 15 Chương 3Các phát biểu điều khiển Các phát biểu điều khiển Phát biểu điều khiển và flowchart So sánh và đánh giá Tổng quan Phát biểu điều khiển: là những dòng lệnh dùng để điều khiển hoạt động của chương trình. Các phát biểu điều khiển cơ bản Phát biểu gán (assignment statement) Các phát biểu điều khiển (control statements) Phát biểu ghép { } Phát biểu điều kiện if Phát biểu điều kiện if..else Phát biểu điều kiện switch ..case Phát biểu lặp while Phát biểu lặp for Phát biểu lặp do..while Phát biểu goto, break, continue Phát biểu gọi hàm (function call): gọi các hàm Phát biểu ghép { }; Dùng để ghép nhiều phát biểu thành một phát biểu. Cú pháp : { các phát biểu;} Ví dụ { t =x; x =y; y =t; cout 0) { X1= (-b + sqrt(Delta))/(2*a); X2= (-b - sqrt(Delta))/(2*a); } Condition Statements Yes Chỉ có 1 phát biểu trong thân của if No Phát biểu if .. else Dùng để chọn lựa phát biểu nào sẽ được thực hiện giữa 2 phát biểu. Cú pháp if (condition) statement1 else statement2 ; Ví dụ if (Delta > 0) { X1= (-b + sqrt(Delta))/(2*a); X2= (-b - sqrt(Delta))/(2*a); } else { cout lãng phí bộ nhớ. Các phần tử của dãy được xếp liên tục trong bộ nhớ do đó: Cho phép khả năng truy xuất ngẫu nhiên => nhanh Cần có vùng nhớ trống liên tục đủ lớn khi cấp phát bộ nhớ cho dãy. => khó cấp phát. Một số giải thuật trên mảng Khi tổ chức lưu trữ trên array của nhiều phần tử, thao tác thường phải thực hiện là tìm kiếm (search) và sắp xếp (sort) các phần tử trong dãy Việc tìm kiếm (search) dùng để truy vấn thống tin. Việc sắp xếp (sort) dùng để trình bày thông tin và giúp cho thao tác search hiệu quả hơn. Một số giải thuật: Linear search có và chưa sort, Binary search Buble sort, quick sort Linear search Xem xét từng phần tử xem có phải giá trị cần tìm hay không cho đến khi tìm thấy hoặc hết số phần tử của array thì kết luận có không có. Timthay := 0; for (int i= 0;i X) j=m; else i=m; } If (co) cout n-1. Nếu phần tử a[i] >a[j] thì hoán đỗi 2 phần tử này Lặp lâi bước trên với số phần tử củ dãy còn lại giảm dần từ n -> 2 . Khi hoàn tất dãy sẽ có thứ tự tăng dần. Ưu điểm của giải thuật là đơn giản. Tuy nhiên tốc độ sắp thứ tự không cao. Có một giải thuật khác khá mạnh là QuickSort Bubble Sort – giải thuật Giải thuật bubble Sort cho dãy có n phần tử và tăng dần. for (int i= 0 ;iA[j+1] ) { t= a[i]; a[j]=a[j+1]; a[j+1]=t; } So sánh và hoán đổi giá trị 2 phần tử. Biến t có dùng kiểu dữ liệu với kiểu cơ sở của array Array nhiều chiều