Bài giảng Phương pháp lập trình

MÔN HỌC PHƯƠNG PHÁP LẬP TRÌNHGiới thiệuMục tiêu môn họcCung 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 dungMộ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ìnhNgôn ngữ minh họa Pseudo code và C/C++Các giải thuật cơ bảnKỹ năng tư duy và thực hành trên ngôn ngữ cụ thể. Phương thứcPhương thức họcGiờ lý thuyết: giảng và báo cáoGiờ thực hành tại phòng máyKiểm tra và thiKiểm tra thực hành: kỹ năng lập trìnhThi lý thuyết : trắc nghiệm khách quanTài liệu tham khảoSlide bài giảng Lập Trình Căn BảnGiáo trình Phương Pháp Lập trình – Khoa CNTTTài liệu khácCDROM bài tập và thực hànhChương 1	Khái niệm cơ bảnMột số khái niệm cơ bản vềMáy tính & chương trình máy tínhNgôn ngữ lập trình ,translator,..Giải thuật và flow chartGiải thuật & biểu diễn giải thuậtFlowchartCông cụ phát triểnCông cụ IDE, CompilerError & debugMáy tính - ComputerMáy tính AnalogMáy tính sốHệ nhị phânMáy tính lập trình đượcMô hình máy Turing và Von NewmanCác thế hệ máy tínhĐặc tính chungKhả năng tính toánKhả năng thực hiện các phép toán logicTốc độ tính toán caoLàm theo chỉ thịKiến trúc máy tínhMáy tính (Computer system) Bao gồm nhiều thiết bị phần cứng (hardware devices)KeyboardScreen (monitor)DisksMemoryProcessing UnitsHệ đ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ệuMôi trường hoạt động: OS, Network, WEB, Server,..Chương trình máy tínhChương trìnhDanh mục các trang thiết bị, tài nguyên sử dụngTiế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ướcKết quả thực hiệnChương trình máy tínhTập hợp các lệnh được liệt kê theo một trình tự nhất địnhCác dữ liệu sẽ được nhậnCác tài nguyên cần sử dụngCác kết quả sẽ có đượcMục tiêu: xử lý dữ liệu theo yêu cầu định trướcLập trình: viết chương trình cho máy tínhNgôn ngữ lập trìnhNgôn ngữ lập trìnhPhương tiện để viết chương trình cho máy tínhHàng trăm ngôn ngữ lập trình khác nhauNhững quy định về cú pháp (syntax) & ngữ nghĩa (semantic)Máy tính có thể hiểu đượcPhân chia làm 3 nhóm chínhNgôn ngữ máy - Machine languagesNgôn ngữ duy nhất của máy tính - CPUHợp ngữ - Assembly languagesNgôn ngữ cấp cao - High-level languagesNgôn ngữ máy - Machine languagesNgô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 CPUPhụ thuộc vào máy tính cụ thểDạng nhị phân {0,1}*Rất khó đọc hiểuKhó có khả năng viết chương trình trực tiếpKhó nhớ hàng chục ngàn lệnh dạng {0,1}*Rất khó xác định & sửa lỗiKhông được sử dụng trong thực tế để viết chương trìnhNền tảng xây dựng hợp ngữHợp ngữ - Assembly LanguagesSử 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ệnChuyển đỗi nhanh chóngDễ đọc và dễ hiểu hơnVẫn tương đối khó sử dụng doCá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ệnKhả 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 caoNgôn ngữ cấp caoMột câu lệnh diễn tả nhiều động tháiCó 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ớpLập trình gotoLập trình cấu trúc – StructuredLập trình hướng đối tượng – Object OrientedCác dạng khácHọc ngôn ngữ lập trìnhHọc ngữ phápQuy tắc ngữ phápTừ vựngCấu trúc câuNgữ nghĩa của các lệnhCác “thành ngữ” Học ngôn ngữ lập trình VS. Học ngôn ngữ tự nhiênQuy tắc ngữ pháp đơn giảnTừ vựng ít, tự quy địnhCấu trúc câu đơn giảnHạn chế và khó khăn của sử dụng ngôn ngữ lập trình.Chương trình dịchDùng để dịch từ một ngôn ngữ lập trình này sang ngôn ngữ lập trình khácMục tiêu cuối cùng là dịch sang mã máy để có được executed code –> chương trình thực thiPhân loại:Intepreter – thông dịchCompiler – biên dịchIntepreter vs. CompilerCông cụ phát triển – Integrated Development Environment (IDE)Soạn thảoDịch và sửa lỗi chương trìnhChạy thử và sửa lỗiMột số khái niệm khácLỗi và sửa lỗiSyntax error – lỗi ngữ phápSemantic error- lỗi ngữ nghĩaRuntime error - Lỗi thực thiDebug – Tìm và sửa lỗiDữ liệu, kiểu dữ liệuCác kiểu dữ liệu cơ bảnSố 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ễnFlow chart – lưu đồFlow chartStart 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ệnYesNo Phát biểu rẽ nhánh khácGiá trị xét phân nhánhTrường hợp 1Trường hợp i KhácStop 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ểmTrì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ìnhBảo đảm khả năng lập trìnhCho phép dễ dàng kiểm tra giải thuậtNguyê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 STOPKhông có sự quay vòng vĩnh viễnKhông có sự kết thúc lưng chừngFlow chartStartNhập a, ba=0 ?YesNob=0 ?YesNoX=-b/aKhông có nghiệmVô số nghiệmStopAlgorithmsGiải phương trình ax + b = 0 Cấu trúc lệnh cơ bảnif (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ềmThu thập yêu cầuPhân tích thiết kếPhát triển chương trình - codeing Xác định giải thuậtViết code và dịch thử , hiệu chỉnh các lỗi syntaxThử nghiệm - TestingChạy thử với các dữ liệu mẫu để kiểm tra lỗi semantic và runtimeVận hành và bảo trìPhát triển theo yêu cầuMột số ngôn ngữ lập trìnhLập trình gotoAssemblyBasicLập trình cấu trúcPascal, CFoxproLập trình hướng đối tượngJava, C++, Object Pascal,KhácProlog, 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ìnhCác khái niệm cơ bản về dữ liệu và biểu diễn dữ liệu trong máy tínhKhai báo dữ liệu trong chương trìnhMột số phép toán cơ bảnCấu trúc cơ bản một chương trình C/C++Danh hiệuKhá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ườngMột số ngôn ngữ có phân biệt như Java,Ví dụ: 	X , BienDem, Bien_dem, X1 , X2 , X3 , x1,x2,x3Ví dụ sai: 	101X3, (X1), Bien DemDanh 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_thuaTừ 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, whileKý 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ệuQui tắc đặt tên danh hiệuTuân thủ quy tắc ngữ pháp của danh hiệuKhô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 0Cá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ánBiể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ứcPhát biểu gán và thủ tục xuất nhậpPhá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 15Chương 3Các phát biểu điều khiểnCác phát biểu điều khiểnPhát biểu điều khiển và flowchartSo sánh và đánh giáTổng quanPhá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ảnPhá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 ifPhát biểu điều kiện if..elsePhát biểu điều kiện switch ..casePhát biểu lặp while Phát biểu lặp forPhát biểu lặp do..whilePhát biểu goto, break, continuePhát biểu gọi hàm (function call): gọi các hàmPhá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); }ConditionStatementsYesChỉ có 1 phát biểu trong thân của ifNoPhát biểu if .. elseDù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ápif (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 => nhanhCầ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ảngKhi 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 searchBuble sort, quick sortLinear searchXem 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àyLặ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à QuickSortBubble Sort – giải thuậtGiả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 arrayArray nhiều chiều