Bài giảng Tin học căn bản - Chương III: Giải quyết bài toán bằng máy tính

CHƯƠNG III GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNH 133CHƯƠNG III GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNH 3.1 Kỹ thuật lập trình3.2 Thuật toán và Thuật giải3.3 Biểu diễn thuật toán3.4 Các bước giải quyết bài toán trên máy1343.1 Kỹ thuật lập trình135Khái quátKỹ thuật xây dựng phần mềm chính là kỹ thuật lập trình. Lập trình vừa là một kỹ thuật vừa là một nghệ thuật.Lập trình (Programming) thực chất là điều khiển - bằng một ngôn ngữ lập trình cụ thể - cách xử lý thông tin trên máy theo yêu cầu của bài toán đặt ra.Để lập trình, phải biết cách tổ chức dữ liệu (nguyên liệu để máy xử lý) và cách thức xử lí dữ liệu (thuật giải) để cho ra kết quả mong muốn.136PROGRAMMING = ALGORITHMS + DATA STRUCTURE137PHẢI TỔ CHỨC DỮ LIỆU THEO CÁCH TỐT NHẤT :	Dữ liệu trong tin học phải được phân loại, xác định một cách rạch ròi theo những quy định chặt chẽ, chính xác để máy có thể phân biệt, nhận biết, lưu trữ và xử lýPHẢI TÌM ĐƯỢC THUẬT TOÁN TỐT NHẤT, TỐI ƯU NHẤT 	 1384 TIÊU CHUẨN ĐÁNH GIÁ MỘT CHƯƠNG TRÌNH :ü Tính tin cậy	ü Tính uyển chuyển ü Tính trong sáng	ü Tính hữu hiệu 139	LẬP TRÌNH CẤU TRÚC	ü Cấu trúc về mặt dữ liệu	ü Từ những lệnh đơn giản đã có hoặc những lệnh đã có cấu trúc, có thể xây dựng những lệnh có cấu trúc phức tạp hơn 	ü Cấu trúc về mặt chương trình :	Một chương trình lớn có thể chia thành nhiều modun chương trình con độc lập Mỗi chương trình con lại có thể phân chia thành các chương trình con khác. 	PASCAL là một trong các ngôn ngữ tiêu biểu về có cấu trúc1403.2 Thuật toán và Giải thuật141KHÁI NIÊM THUẬT TOÁN	Lµ kh¸i niƯm c¬ së cđa To¸n häc vµ Tin häc	ThuËt to¸n (Algorithm) lµ mét hƯ thèng chỈt chÏ vµ râ rµng c¸c quy t¾c nh»m x¸c ®Þnh mét d·y c¸c thao t¸c trªn những ®èi t­ỵng, sao cho sau mét sè hữu h¹n b­íc thùc hiƯn c¸c thao t¸c ta ®¹t ®­ỵc mơc tiªu ®Þnh tr­íc.	142	Ng­êi hoỈc m¸y thùc hiƯn mét thuËt to¸n ®­ỵc gäi lµ mét bé xư lý. 	Nh­ vËy mét bé xư lý cđa mét thuËt to¸n T nµo ®ã lµ mét c¬ chÕ cã khả năng thùc hiƯn c¸c thao t¸c trªn c¸c ®èi t­ỵng theo mét trình tù do T quy ®Þnh.	143	Cïng mét bµi to¸n cã thĨ cã nhiỊu thuËt to¸n kh¸c nhau. 	ThuËt to¸n ®¬n giản, dƠ hiĨu, cã ®é chÝnh x¸c cao, ®­ỵc bảo ®ảm vỊ mỈt to¸n häc, dƠ triĨn khai trªn m¸y, thêi gian thao t¸c ng¾n, ®­ỵc gäi lµ thuËt to¸n tèi ­u. 	144 	Nghiªn cøu thuËt to¸n lµ mét trong những vÊn ®Ị quan träng nhÊt cđa Tin häc.	Lý thuyÕt vỊ thuËt to¸n phải giải quyÕt c¸c vÊn ®Ị sau :	-Những bµi to¸n nµo giải ®­ỵc b»ng thuËt to¸n; bµi to¸n nµo kh«ng giải ®­ỵc b»ng thuËt to¸n	-Tìm thuËt to¸n tèt nhÊt, tèi ­u cđa mét bµi to¸n	-TriĨn khai thuËt to¸n trªn m¸y tÝnh	145Vài ví dụ	 ThuËt to¸n giải ph­¬ng trình bËc hai : A X2 + BX + C = 0 (A  0)  -B­íc 1 : TÝnh DELTA = B*B-4*A*C -B­íc 2 : So s¸nh DELTA víi sè 0 -B­íc 3 : RÏ lµm 3 tr­êng hỵp : -Tr­êng hỵp DELTA 0 :tÝnh hai nghiƯm ph©n biƯt:	X1, X2  th«ng b¸o nghiƯm ; kÕt thĩc thuËt to¸n.146ThuËt to¸n Hoocne tÝnh gi¸ trÞ cđa ®a thøc : Cho Pn(X)=AnXn + An-1Xn-1 +........ +A1X1 +A0TÝnh Pn(c) ? Pn(c)=(...((An.c +An-1).c + An-2 )...).c + A0  - B­íc 1 : Cho i = n ; Q = An - B­íc 2 : Cho i nhËn gi¸ trÞ cị cđa i trõ 1 : i = i - 1 So s¸nh i víi 0. - B­íc 3 : RÏ lµm 2 tr­êng hỵp :	 1-Tr­êng hỵp i >= 0 : tÝnh Q b»ng gi¸ trÞ cị cđa Q nh©n víi c céng víi Ai ; Quay trë l¹i b­íc 2. 2-Tr­êng hỵp i 0 vì m¸y kh«ng thĨ thùc hiƯn phÐp tÝnh khai căn DELTA.	TÍNH KHẢ THI153	ThuËt to¸n phải vÐt ®­ỵc hÕt c¸c tình huèng, c¸c khả năng cã thĨ xẩy ra, kh«ng bá sãt bÊt kỳ mét tr­êng hỵp nµo trong miỊn ¸p dơng.	ThuËt to¸n Hooc-ne và Giải phương trình bậc 2 kh«ng cã tÝnh ®Çy ®đ nÕu dữ liƯu nhËp tõ bµn phÝm TÍNH ĐẦY ĐỦ-VÉT CẠN154TÍNH ĐÚNG ĐẮN ThuËt to¸n phải cho kÕt quả ®ĩng cđa bµi to¸n nghÜa lµ phải ®­ỵc chøng minh vỊ mỈt to¸n häc . 	ThuËt to¸n tìm béi sè chung nhá nhÊt cđa hai sè nguyªn d­¬ng a,b ký hiƯu c=BSCNN(a,b) : -B1 : NÕu a = 1 thì c = b , dõng NÕu b = 1 thì c = a , dõng -B2 : NÕu a >1 vµ b >1 thì c = a*b , dõng Cã thĨ kiĨm tra 100 tr­êng hỵp cđa a, b ®Ịu cho kÕt qủa ®ĩng, nh­ng víi a = 4, b = 2 thì sai. ThuËt to¸n này kh«ng cã tÝnh ®ĩng ®¾n trªn N 155MỘT THUẬT TOÁN PHẢI THOẢ MÃN ĐỒNG THỜI CÁC TÍNH CHẤT TRÊN156CẤU TRÚC CƠ BẢN CỦA THUẬT TOÁN 157CẤU TRÚC TUẦN TỰTHAO TÁC 2 THAO TÁC 3 THAO TÁC 1 158CẤU TRÚC RẼ NHÁNHĐIỀU KIỆNTHAO TÁC 1THAO TÁC 2159CẤU TRÚC VÒNG LẶPĐIỀU KIỆNTHAO TÁC THAO TÁC 160CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN1611) Dïng ng«n ngữ mẹ đẻ hoặc 	ngơn ngữ mã giả2) Ng«n ngữ l­u ®å 3) Ng«n ngữ lËp trình BiĨu diƠn thuËt to¸n b»ng ng«n ngữ lËp trình chÝnh lµ thảo ch­¬ng, mơc tiªu quan träng trong Tin häc. 162Ngôn ngữ mã giả ThuËtTo¸nPh­¬ngTrinhBËcHai; BiÕn 	 A,B,C,DELTA,X1,X2 : SèThùc ; B¾tĐÇu 	 NhËp A,B,C; 	 DELTA:=B*B-4*A*C; NÕu DELTA 0 THEN	BEGIN	Writeln('Phuong trinh có 2 nghiem : ');	X1 := (-b+sqrt(delta))/(2*a);	X2 := (-b-sqrt(delta))/(2*a);	Writeln(' X1 = ', X1: 9 : 2);	Writeln(' X2 = ', X2: 9 : 2);	END;Readln;END.166    	 Kh¸i niƯm thuËt to¸n đã trình bày chÝnh lµ c¸nh cưa khÐp kÝn cho viƯc gỉai c¸c bµi to¸n vì:	-NhiỊu bµi to¸n kh«ng tháa c¸c ®Ỉc tr­ng c¬ bản cđa thuËt to¸n.	-Cã nhiều bµi to¸n ch­a tìm ra thuËt to¸n hoỈc ch­a chøng minh ®­ỵc lµ cã thuËt to¸n hay kh«ng. Cã những bµi to¸n cã thuËt to¸n nh­ng khã thùc hiƯn hoỈc kh«ng thùc hiƯn ®­ỵc THUËT GI¶I167 ·     	Cã những bµi to¸n ®­ỵc giải tuy vi ph¹m c¸c quy ®Þnh cđa thuËt to¸n nh­ng lêi giải vÉn ®­ỵc thùc tiƠn chÊp nhËn THUẬT GIẢI CŨNG LÀ THUẬT TỐN NHƯNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN168NHỮNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN·         Më réng tÝnh x¸c ®Þnh	TÝnh x¸c ®Þnh thùc chÊt lµ tÝnh ®¬n trÞ cđa c¸ch giải cđa mét thuËt to¸n vµ sù râ rµng tèi ®a. Trong thùc tÕ cã nhiỊu bµi to¸n vi ph¹m tÝnh x¸c ®Þnh mµ vÉn cho kÕt qủa. Nh­ vËy thay cho viƯc x©y dùng toµn bé qu¸ trình giải chØ cÇn chØ ra c¸ch chuyĨn tõ b­íc i sang b­íc i+1. 	C¸ch gỉai ngÉu nhiªn, ®Ư quy lµ më réng tÝnh x¸c ®Þnh 169	     Më réng tÝnh ®ĩng ®¾n	TÝnh ®ĩng ®¾n ®­ỵc hiĨu lµ cho kÕt quả ®ĩng. Nh­ng trong thùc tÕ thì sè gÇn ®ĩng lµ cã thĨ chÊp nhËn. Ngoµi ra dïng c¸ch gỉai heuristic ®¬n giản, ®éc ®¸o vÉn cã thĨ cho kÕt qủa mét c¸ch s¸ng t¹o. 170NĂM BƯỚC GIẢI BÀI TOÁN TRÊN MÁY TÍNH a) B­íc 1 	Nghiªn cøu kÜ néi dung, yªu cÇu cđa bµi to¸n vµ tìm ph­¬ng ph¸p, thuËt to¸n giải bµi to¸n 	Víi bµi to¸n lín, phøc t¹p viƯc tìm ph­¬ng ph¸p vµ thuËt to¸n rÊt khã khăn. NhiỊu tr­êng hỵp phải cã sù céng t¸c, giĩp ®ì cđa c¸c chuyªn gia vỊ ph­¬ng ph¸p tÝnh to¸n vµ thuËt to¸n . b) B­íc 2 	DiƠn tả thuËt to¸n b»ng l­u ®å hoỈc b»ng ng«n ngữ Mơ tả thuật tốn. 171 c) B­íc 3 DiƠn tả thuËt to¸n b»ng b»ng ng«n ngữ LËp trình Đ©y lµ c«ng viƯc chuyĨn l­u ®å hoỈc ng«n ngữ Mơ tả thuật tốn thµnh ng«n ngữ lËp trình. Qu¸ trình nµy gäi lµ thảo ch­¬ng . d) B­íc 4 Ch¹y thư vµ sưa lçi. B­íc nµy cã thĨ thùc hiƯn xen kÏ trong b­íc 3 vµ thùc hiƯn nhiỊu lÇn víi nhiỊu ng­êi kh¸c nhau nh»m ph¸t hiƯn tèi ®a c¸c sai sãt . Phải sưa hÕt tÊt cả c¸c lçi dï nhá nhÊt. 172 e) B­íc 5 иnh gi¸ sù ®ĩng ®¾n vµ ®é tin cËy cđa kÕt qđa.ViƯc ®¸nh gi¸ nµy th­êng dùa trªn : - ý nghÜa thùc tiƠn cđa bµi to¸n - Kinh nghiƯm dù ®ãan kÕt qđa cđa ng­êi giải - So s¸nh kÕt qđa víi kÕt qđa cđa bµi to¸n ®· cã lêi 	giai ®ĩng - Giải bµi to¸n trong những tr­êng hỵp ®Ỉc biƯt, 	tr­êng hỵp thu gän dƠ thÊy kÕt qđa lµ ®ĩng hay sai. NÕu kÕt quả sai phải rµ so¸t l¹i tõ b­íc 1 và cã thĨ sai tõ thuËt to¸n. C«ng viƯc tìm lçi sai vµ sưa lçi cđa thuËt to¸n rÊt khã NÕu kÕt qủa tìm ®­ỵc lµ ®ĩng ®¾n vµ tin cËy, ghi ch­¬ng trình lªn ®Üa ®Ĩ l­u .173CÁC PHƯƠNG PHÁP THÔNG DỤNGPH¦¬ng ph¸p ®ĩngPh­¬ng ph¸p gÇn ®ĩng -ph­¬ng ph¸p tÝnhPh­¬ng ph¸p ngÉu nhiªnPh­¬ng ph¸p kinh nghiƯm	HEURISTIC174