Tài liệu Sáng kiến kinh nghiệm những kỹ năng cơ bản để giải bài toán trên máy tính bằng ngôn ngữ lập trình pascal

Sáng kiến kinh nghiệm THCS Hải Cảng A.MỞ ĐẦU: I. ĐẶT VẤN ĐỀ : 1. Thực trạng của vấn đề đòi hỏi phải có giải pháp mới để giải  quyết: ­ Nhu cầu của xã hội ngày càng lớn cùng với sự  phát triển của khoa học kỹ  thuật đã kéo theo sự phát triển như vũ bão của tin học. Sự phát triển của tin học   đã đem lại hiệu quả to lớn cho hầu hết các lĩnh vực của xã hội, hơn thế nữa  nó  còn đi sâu vào đời sống của con người. ­ Nền tin học của một quốc gia được xem là sự  phát triển nếu nó đóng góp  được phần đáng kể vào nền kinh tế quốc dân và vào kho tàng tri thức chung của  thế giới. ­ Lịch sử  nhân loại đã chứng kiến những cuộc cách mạng về  công nghệ  thông tin với sự trợ  giúp của máy tính và hệ  thống máy tính, con người đã nâng   cao năng suất và tự  động hóa ngày một hiệu quả  hơn và một trong những  ứng   dụng không thể không nhắc đến đó là những ứng dụng phần mềm của máy tính  với nền công nghệ  thông tin hiện nay. Phần mềm máy tính ngày một đi lên và  phát triển với những ngôn ngữ  lập trình khác nhau và cụ  thể  là ngôn ngữ  lập  trình Pascal. Pascal là một ngôn ngữ  lập trình có cú pháp chặt chẽ, đơn giản và   dễ hiểu. ­ Do vậy, Việt Nam nói chung và ngành giáo dục đào tạo nói riêng phải đầu tư  phát triển về  mọi mặt. Đặc biệt là nguồn nhân lực tri thức tức là phải đào tạo ra   một thế hệ trẻ năng động, thông minh, độc lập, sáng tạo, nắm vững tri thức khoa  học công nghệ để làm chủ trong mọi hoàn cảnh công tác và hoạt động xã hội nhằm  đáp ứng được nhu cầu trong thời kì công nghiệp hoá, hiện đại hoá đất nước. ­ Để  đáp  ứng được các yêu cầu trên, môn Tin học đã được đưa vào giảng   dạy  ở các trường phổ thông với vai trò là môn học chính khóa với thời lượng 2   tiết/tuần cho tất cả các lớp ở cấp học.  GV : Phạm Thị Bích Diệp Năm 1 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng ­ Đặc trưng của môn Tin học lớp 8 là kiến thức về lập trình. Ngôn ngữ  lập   trình dường như rất xa lạ vì đây là kiến thức đầu tiên trong lập trình mà các em  được học. ­ Qua giảng dạy môn Tin học  ở  trường THCS Hải Cảng, bản thân tôi nhận  thấy rằng nhiều học sinh lớp 8 thấy môn lập trình Pascal khó, khô khan và cực  kỳ  loằng ngoằng. Mới đầu các em cũng rất sợ  vì khi thấy giải một bài toán  ở  ngoài thì đơn giản và chỉ trong vòng vài giây có thể nhẩm ra kết quả còn ở trong  lập trình cũng bài toán đó mà phải làm đến hàng chục phút mà có thể cho kết quả  sai. Pascal trở  nên quá xa lạ  và khó khăn đối với người sử  dụng và nhất là đối  với học sinh THCS là những người đang trực tiếp  ứng dụng ngôn ngữ  lập trình  này. ­ Tâm lý các em đều cho rằng môn Tin học không phải là môn học chính. Do  đó không cần phải để tâm đến "nó". Những tiết học lý thuyết thì ghi chép qua loa  cho xong chuyện bằng không thì ghi chép "giả  vờ" để  thầy cô khỏi chú ý hay  nhắc nhở  trong lúc giảng bài. Trong những tiết thực hành chỉ  một vài học sinh  thật sự  chú tâm suy nghĩ xây dựng thuật toán, viết chương trình đa số  còn lại  tranh thủ  chơi game hoặc làm việc riêng. Buồn thay cho một số  học sinh khi   được kiểm tra vở  tại thời điểm sắp kết thúc học kỳ  2 mà chỉ  ghi được 5 bảy  trang cho cả một chương trình khá dài trong cuốn Tin Học 3. ­ Xét  ở  một góc độ  nào đó Lập trình cũng là một môn học khó đối với học  sinh THCS. Khó  ở  đây không phải do tính phức tạp của môn học hay phạm vi   kiến thức quá  rộng lớn. Nếu đem so sánh môn học Lập trình và các phân môn   Toán học ở trường THCS thì Lập trình Pascal gọn nhỏ hơn nhiều lần. ­ Lập trình Pascal "khó" đối với học sinh THCS  ở chỗ: môi trường lập trình   Pascal có giao diện và các từ  khóa đều bằng tiếng Anh, các dòng thông báo hay  trợ giúp cũng vậy. Bình diện chung học sinh THCS vốn tiếng Anh không nhiều,  đa số  các em còn yếu về  tiếng Anh. Lấy đơn vị  lớp để  tính thì mỗi lớp chỉ  có   một vài em được gọi là "thông thạo" tiếng Anh qua các bài học. Hầu hết số còn  lại nằm trong trạng thái "mù tịt". Đây là một khó khăn cho việc hiểu được Pascal. GV : Phạm Thị Bích Diệp Năm 2 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng ­ Một vấn đề  nữa cũng là rào cản đối với việc các học sinh THCS tiếp cận  với lập trình Pascal đó là: tư duy Toán của các em dừng lại ở mức độ  Sách Giáo  Khoa Toán THCS do đó kỹ  năng phân tích, tổng hợp, xây dựng thuật toán cho   mỗi bài toán hay vấn đề cần lập trình chưa tốt.  Các em vẫn thụ động  trong việc  tiếp cận bài toán, sắp xếp tư duy, xây dựng thuật giải. ­ Từ thực tế trên, trong quá trình dạy học tôi luôn băn khoăn trăn trở làm thế  nào nâng cao chất lượng kỹ năng lập trình cho học sinh lớp 8. Việc tiếp cận với   môn học rất khó khăn, phải làm rất nhiều lần và thực hành rất nhiều tiết các em   mới hiểu việc nhập và xuất dữ liệu. Do đó sẽ rất khó khăn để các em hình thành   kỹ  năng viết chương trình. Nhất là những năm gần đây Ngành giáo dục luôn  thành lập đội tuyển tham dự kì thi Tin học trẻ, học sinh giỏi môn Tin học lớp 9, …. Điều đó đã thúc đẩy tôi trong quá trình giảng dạy phải nghiên cứu tìm tòi   biện pháp, kinh nghiệm để  giúp cho các em có sự  đam mê học tập về  lập trình,  giúp các em biết được quy trình lập trình như thế nào và định hướng cho học sinh  cách để trở thành một nhà lập trình thì cần phải biết  những kỹ năng cơ bản để   giải bài toán trên máy tính bằng ngôn ngữ  lập trình Pascal . Giúp các em yêu  thích lập trình và học lập trình trong sự hứng thú. 2. Ý nghĩa và tác dụng của giải pháp mới: Việc thực hiện nội dung này đã góp thêm một phương pháp mới trong việc  giảng dạy học sinh lớp 8 có được kỹ năng cơ bản để giải bài toán trên máy tính   bằng ngôn ngữ  lập trình Pascal. Tạo cho học sinh sự  thích thú nhằm nâng cao  tính tích cực, độc lập, sáng tạo và kỹ năng chuyên nghiệp của học sinh trong quá  trình sử dụng máy vi tính. Bên cạnh đó các học sinh sẽ  cùng hỗ  trợ  lẫn nhau và thúc đẩy nhau cùng   học tập, cùng tiến bộ. Những đối tượng khác có niềm đam mê lập trình, đam mê  nghiên cứu viết phần mềm tin học sẽ  ngày càng hứng thú khám phá trong quá  trình thực hành trên máy tính. Hạt nhân của chương trình máy tính là sự  lưu trữ và xử lý thông tin. Việc  tổ  chức dữ liệu như thế nào có ảnh hưởng rất lớn đến cách thức xử  lý dữ  liệu   đó, cũng như tốc độ thực thi và sự  chiếm dụng bộ nhớ của chương trình. Do đó   GV : Phạm Thị Bích Diệp Năm 3 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng mục đích của bài viết này là cung cấp  những hiểu biết nền tảng trong việc thiết   kế  một chương trình máy tính để  thấy rõ sự  cần thiết của việc phân tích, lựa   chọn cấu trúc dữ liệu phù hợp cho từng bài toán cụ thể. 3. Phạm vi nghiên cứu của đề tài:  Học sinh khối 8, 9 trong nhà trường trung học cơ sở Hải Cảng. II. PHƯƠNG PHÁP TIẾN HÀNH: 1. Cơ sở lý luận và thực tiễn có tính định hướng cho việc nghiên cứu,  tìm giải pháp của đề tài: Chúng ta   đang sống trong thời đại khoa học điện tử, thời đại bùng nổ  thông tin và mạng máy tính. Công nghệ  thông tin là tập hợp các phương pháp   khoa học, các phương tiện và công cụ kỹ thuật hiện đại nhằm tổ chức khai thác  và sử  dụng có hiệu quả  các nguồn tài nguyên thông tin rất phong phú và tiềm  năng trong mọi lĩnh vực hoạt động của con người và xã hội. Bộ GD&ĐT đã chỉ rõ: Nâng cao nhận thức về vai trò của CNTT; ứng dụng   và phát triển CNTT trong giáo dục và đào tạo sẽ  tạo một bước chuyển cơ bản  trong quá trình đổi mới nội dung, chương trình, phương pháp giảng dạy, học tập  và quản lí giáo dục. Đặc trưng của môn Tin học là môn khoa học gắn liền với công nghệ hiện  đại, do vậy dạy học Tin học trong nhà trường  nhằm trang bị cho học sinh kiến   thức khoa học về Tin học, phát triển tư duy thuật toán, kỹ năng lập trình và tiếp   cận những công nghệ  mới của Tin học phục vụ học tập và đời sống. Nội dung  chương trình của môn Tin học hiện hành  ở  các trường THCS đã đáp  ứng được  những yêu cầu trên. Trong nhà trường hiện  đang phấn đấu các mục tiêu cụ  thể của ngành là:  Tổ  chức tốt việc hướng dẫn học sinh biết cách lập trình để  tham gia các kỳ  thi  như Tin học trẻ, học sinh giỏi lớp 9,… * Thuận lợi: GV : Phạm Thị Bích Diệp Năm 4 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng ­ Được sự quan tâm của Ngành giáo dục trong công cuộc đổi mới phương   pháp dạy học. ­ Được sự quan tâm của BGH nhà trường trong việc đầu tư cơ  sở vật chất,  trang thiết bị dạy học tương đối đầy đủ  đảm bảo phục vụ giảng dạy bộ môn Tin  học. ­ Giáo viên giảng dạy được đào tạo theo đúng chuyên ngành và được bồi  dưỡng chuyên môn hàng năm. ­ Phân l ̀ ơn cac em hoc sinh co y th ́ ́ ̣ ́ ́ ưc tự ́  hoc cao, luôn tim toi hoc hoi nh ̣ ̀ ̀ ̣ ̉ ưng  ̃ kiên th ́ ưc m ́ ơí trong hoc tâp và ̣ ̣  rất hứng thú với môn Tin học. * Khó khăn: ­ Một bộ phận học sinh lớp 8 chưa ý thức việc học Tin. ­ Số lượng học sinh trong một lớp học còn quá đông trên 40 học sinh một   lớp, diện tích phòng máy nhỏ  hẹp, phòng máy có 20 máy nhưng là máy cũ nên  thường hay hư hỏng, thiết bị hỗ trợ thường bị hư hao, không khí trong phòng máy  không thoáng mát làm cho học sinh không tập trung vào bài giảng ...  ảnh hưởng  rất lớn trong quá trình giảng dạy và học tập. ­ Vân con môt sô em hoc sinh tiêp thu kiên th ̃ ̀ ̣ ́ ̣ ́ ́ ưc con châm,  ́ ̀ ̣ đặc biệt là kĩ  năng cơ  bản để  giải bài toán trên máy tính bằng ngôn ngữ  lập trình Pascal bởi   đây là một môn học mới (một môn ngoại ngữ mới). ­ Trương ̀  THCS Hải Cảng nằm trên phường Hải Cảng, là địa phương còn  nghèo nàn, đa số con em gia đình làm nghề biển, trình độ học vấn có nhiều hạn   chế nên sự quan tâm của phụ huynh đến việc học tập của con em còn hạn chế. Ít  có điều kiện chăm sóc, giáo dục và định hướng cho con em trong việc học tập. ­ Một số  học sinh chưa coi trọng môn học, xem đây là một môn phụ  nên   chưa có sự đầu tư thời gian cho việc học. Ngoài ra, ở chương trình Tin học 8, các   em phải làm quen, tiếp cận với ngôn ngữ  lập trình Pascal là một phần mềm có  cấu trúc phức tạp, ngôn ngữ  lập trình bằng tiếng anh. Mặc khác để  thực hiện  được một chương trình thì các em phải có một kiến thức toán học nhất định.  2. Các biện pháp tiến hành, thời gian tạo ra giải pháp: GV : Phạm Thị Bích Diệp Năm 5 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng Qua quá trình học tập, nghiên cứu và hướng dẫn, cộng với thực tiễn trong   công tác giảng dạy. Các phương pháp giúp cho tôi tập trung vào nghiên cứu   chính, đó là: ­ Phương pháp điều tra ­ Phương pháp quan sát. ­ Phương pháp phân tích tổng hợp ­ Phương pháp thống kê. GV : Phạm Thị Bích Diệp Năm 6 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng NỘI DUNG : I. MỤC TIÊU: Kinh qua những năm trực tiếp giảng dạy bộ môn cũng như trao đổi với đồng  nghiệp tôi nhận thấy: hầu như học sinh đều rất yêu thích và hứng thú với môn Tin   học. Tuy nhiên, chất lượng bộ môn Tin học lớp 8 qua các năm học chưa cao, đặc   biệt là kĩ năng lập trình còn hạn chế. Mục đích của tôi là giúp đỡ  học sinh lớp 8  nắm được những kĩ năng cơ bản để giải bài toán trên máy tính bằng ngôn ngữ   lập trình Pascal. Tạo cho học sinh niềm hứng thú và say mê trong lập trình để từ đó   giúp cho các em phát huy tính tích cực, tự giác, chủ  động, sáng tạo, rèn luyện thói  quen làm việc độc lập và kỹ  năng lập trình. Bên cạnh đó, học sinh còn biết vận  dụng để giải quyết các bài toán thường gặp trong thực tế; gây hứng thú trong học   tập, làm cho “học” là quá trình kiến tạo; là niềm say mê để từ đó học sinh biết khai  thác và xử lý thông tin, tự hình thành hiểu biết, năng lực và phẩm chất.  Khi thực hiện nội dung này bản thân tôi là giáo viên tin học cũng thấy mình  trở nên năng động, sáng tạo, phát huy được chuyên môn của mình.  II. MÔ TẢ GIẢI PHÁP CỦA ĐỀ TÀI: 1. Thuyết minh tính mới: 1.1  Kiểm tra học kỳ 1 năm học 2012­2013  môn Tin học: Qua kiểm tra chất lượng học kỳ 1 năm học 2012­2013, tôi thấy kỹ năng cơ  bản để giải bài toán trên máy tính bằng ngôn ngữ lập trình Pascal của học sinh lớp 8  là rất yếu. Khi giải bài toán trên máy tính học sinh chỉ quan tâm đến công thức để  tính toán ra kết quả bài toán mà quên các bước xác định thông tin vào, thông tin ra;   xây dựng thuật toán; chạy chương trình thì học sinh chưa nhận biết được kết quả  chương trình đúng hay sai. Vì thế, kết quả kiểm tra học kỳ 1 là rất thấp. Kết quả khảo học kỳ 1 năm học 2012­2013  T T Lớp Sĩ  Giỏi Kết quả kiểm tra TB Yế u Khá Kém Trên TB số SL % SL % SL % SL % SL % SL 1 8A1 36 5 13.9 7 19.4 9 25.0 7 19.4 8 22.3 21 2 8A2 38 4 10.5 8 21.1 6 15.8 10 26.3 10 26.3 18 GV : Phạm Thị Bích Diệp Năm 7 học 2013-2014 % 58. 3 47. Sáng kiến kinh nghiệm 3 8A3 37 Tổng cộng THCS Hải Cảng 2 5.4 6 16.2 7 18.9 12 32.4 10 27.0 15 11 9.9 21 18.9 22 19.8 29 26.1 28 25.2 54 4 40. 5 48. 6 1.2 Giải quyết vấn đề: Pascal là ngôn ngữ  lập trình cho máy tính thuộc dạng mệnh lệnh, được  Niklaus Wirth phát triển vào năm 1970, là ngôn ngữ đặc biệt thích hợp cho nhiều   thế hệ học sinh, là ngôn ngữ vỡ lòng trong chương trình học. Ở môi trường này,  học sinh sở hữu một lượng tài nguyên là các kiểu dữ liệu đơn giản, cùng với các   câu lệnh rõ ràng, trong sáng, nhất quán và rất dễ  thuộc. Tuy nhiên, nó đòi hỏi   người lập trình tài bố cục, thiết kế một thuật toán sao cho đúng đắn, hiệu quả và  tối  ưu, rồi vận dụng các quy tắc cú pháp để  viết ra được những câu lệnh phù  hợp. Vì thế  kỹ  năng cơ  bản để  giải bài toán trên máy tính bằng ngôn ngữ  lập   trình Pascal thì cần các bước sau : ­ Xác định bài toán ­ Tìm cấu trúc dữ liệu biểu diễn thuật toán ­ Xây dựng thuật toán ­ Viết chương trình ­ Kiểm thử chương trình ­ Tối ưu chương trình. 1.2.1 Xác định bài toán: a. Khái niệm bài toán: Đã là học sinh thì thường xuyên gặp các bài toán  ở  nhiều dạng khác nhau  trong mọi cấp học. Tuy nhiên không phải bài toán nào cũng dễ dàng để thực hiện   được và cho kết quả  tốt. Nhưng đối với bất kỳ  một bài toán nào thì học sinh  cũng được giáo viên hướng dẫn là phải đọc kỹ đề rồi xác định nó : A  B Trong đó:  A là giả thiết : Điều kiện ban đầu hay cái đã cho khi bắt đầu giải bài toán. GV : Phạm Thị Bích Diệp Năm 8 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng B là kết luận : Mục tiêu cần đạt được hay cái phải tìm, phải làm ra khi kết   thúc bài toán.  là suy luận : Giải pháp cần xác định hay một chuỗi các bước cần thực  hiện từ A đến B. b. Bài toán trên máy vi tính : Bài toán trên máy cũng mang đầy đủ  các tính chất của bài toán tổng quát  trên, nhưng nó lại được diễn đạt theo một các khác. ­ A : là  đưa thông tin vào – thông tin trước khi xử lý (Input ) ­ B: là đưa thông tin ra – kết quả sau khi xử lý (Output) ­  : là chương trình tạo từ các câu lệnh cơ bản của máy tính cho phép xử  lý từ A đến B. c. Xác định bài toán: Việc xác định bài toán là xác định xem ta phải giải quyết vấn đề  gì? Với giả  thiết nào đã cho và với lời giải cần đạt những yêu cầu gì. Khác với các bài toán   thuần túy trong toán học là chỉ  cần xác định rõ giả  thiết và kết luận chứ  không   cần xác định yêu cầu về lời giải, đôi khi những bài toán tin học trong thực tế chỉ  cần tìm lời giải tốt tới mức nào đó,  thậm chí là chỉ ở mức chấp nhận được (nếu   lời giải tốt nhất đòi hỏi quá nhiều thời gian và chi phí). Input   Process   Output (Dữ liệu vào   Xử lý   Kết quả ra) d. Một số ví dụ : Ví dụ 1: Tính diện tích hình vuông. Các bước xác định cho bài toán: + Thông tin vào (Input) : Cạnh hình vuông a + Thông tin ra (Output) : Kết quả diện tích khi đưa a vào + Các dữ liệu cần xử lý để chế biến thông tin như: Lần lượt đưa giá trị a vào (cho a = 4) Áp dụng công thức tính diện tích hình vuông: a*a Kết quả in ra là 16. Ví dụ 2: Nhập vào một xâu ký tự và in ra màn hình xâu đã được đổi thành in hoa. GV : Phạm Thị Bích Diệp Năm 9 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng Các bước xác định cho bài toán: + Input : Xâu ký tự  + Output : Xâu ký tự đã đổi thành in hoa + Các dữ liệu cần xử lý để chế biến thông tin như: Lần lượt đưa xây ký tự vào ( S = abcd) Áp dụng công thức :  Xác định chiều dài xâu ký tự bằng hàm Length(s) For i:=1 to length(St) do St[i]:=Upcase(St[i]);              Kết quả in ra là ABCD. Ví dụ 3: Giải phương trình bậc nhất dạng tổng quát bx + c =0 Các bước xác định cho bài toán: + Input : Các số b, c  + Output : Nghiệm của phương trình bậc nhất + Các dữ liệu cần xử lý để chế biến thông tin như: Lần lượt đưa giá trị b, c vào ( b = 3 ; c= ­ 6) Áp dụng công thức :  ­ Nếu b = 0 và c = 0 thì phương trình có vô số nghiệm ­ Nếu b = 0 và c ≠ 0 thì phương trình vô nghiệm ­ Nếu b ≠  0 thì phương trình có nghiệm x = ­c/b;    Kết quả in ra là x = 2 Ví dụ 4: Tìm giá trị lớn nhất của một dãy số nguyên Các bước xác định cho bài toán: + Input : số nguyên dương N và dãy N số nguyên a1, …., aN  N = 5 ;  (7, 5, 9, 4, 10) + Output : Giá trị lớn nhất Max của dãy số. + Các dữ liệu cần xử lý để chế biến thông tin như: Khởi tạo giá trị Max = a1 Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai  > Max thì Max nhận giá trị mới là ai. GV : Phạm Thị Bích Diệp Năm 10 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng Kết quả in ra là Max = 10. 1.2.2 Tìm cấu trúc dữ liệu biểu diễn thuật toán: * Cấu trúc dữ  liệu (data structure) : Là kiểu dữ  liệu mà bên trong nó có  chứa nhiều thành phần dữ liệu và các thành phần dữ liệu đấy được tổ chức theo  một cấu trúc nào đó. Nó dùng để biểu diễn cho các thông tin có cấu trúc của bài  toán. Cấu trúc dữ  liệu thể  hiện khía cạnh logic của dữ  liệu. Ví dụ  cấu trúc dữ  liệu đơn giản nhất trong chương trình tin học lớp 8 là mảng.  Còn các dữ liệu không có cấu trúc được gọi là các dữ liệu vô hướng hay  các dữ  liệu đơn giản. VD: các kiểu dữ liệu số nguyên (integer), số  thực (real),  logic (boolean) là các kiểu dữ liệu đơn giản.   * Khi giải một bài toán, ta cần phải định nghĩa tập hợp dữ liệu để biểu diễn  tình trạng cụ thể. Việc lựa chọn này tùy thuộc vào vấn đề cần giải quyết và những   thao tác sẽ  tiến hành trên dữ  liệu vào. Có những thuật toán chỉ  thích ứng với một   cách tổ chức dữ liệu nhất định, đối với những cách tổ chức dữ liệu khác thì sẽ kém  hiệu quả hoặc không thể thực hiện được. Chính vì vậy nên bước xây dựng cấu trúc  dữ liệu không thể tách rời bước tìm kiếm thuật toán giải quyết vấn đề. * Các tiêu chuẩn khi lựa chọn cấu trúc dữ liệu: ­ Cấu trúc dữ  liệu trước hết phải biểu diễn được đầy đủ  các thông tin  nhập và xuất của bài toán. ­ Cấu trúc dữ  liệu phải phù hợp với các thao tác của thuật toán mà ta lựa  chọn để giải quyết bài toán. ­ Cấu trúc dữ liệu phải cài đặt được trên máy tính với ngôn ngữ  lập trình   đang sử dụng. * Đối với một số bài toán, trước khi tổ chức dữ liệu ta phải viết một đoạn   chương trình nhỏ để khảo sát xem dữ liệu cần lưu trữ lớn tới mức độ nào.  1.2.3 Xây dựng thuật toán: Đây là bước khó nhất đối với học sinh và cũng cho giáo viên khi dạy phần   này vì các em quen giải bài toán cụ thể nào đó và giải bài toán bằng ngôn ngữ tự  GV : Phạm Thị Bích Diệp Năm 11 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng nhiên mà các em đã học còn bây giờ các em phải xây dựng thuật toán của một bài   toán tổng quát và bằng ngôn ngữ lập trình của máy.  a. Khái niệm thuật toán: Thuật toán 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 thao tác trên cấu trúc dữ  liệu sao cho: với một bộ  dữ  liệu vào (Input),   sau số hữu hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được kết quả đã định   (Output). INPUT ALGORITHM OUTPUT b. Phương pháp biểu diễn thuật toán: Trong phần này chúng ta cần đưa ra một phương  pháp mô tả  thuật toán  một cách khoa học để  học sinh nhận biết được quy trình làm việc của máy vi  tính (Ngôn ngữ  lập trình) làm việc như  thế  nào. Mô tả  thuật toán là bước quan  trọng nhất đối với người lập trình, nếu người lập trình mô tả thuật toán sai hoặc  dài dòng thì dẫn đến khi viết chương trình sẽ khó khăn hoặc sẽ cho kết quả sai.  Ở bước này đòi hỏi người lập trình cần có những hiểu biết cơ bản về toán học  thì khả năng biểu diễn thuật toán sẽ trở nên đơn giản hơn và sẽ thấy bài toán trở  nên gần gủi. Vì vậy trong phần này tôi sẽ đã đưa ra hai phương pháp mô tả thuật   toán một cách rõ ràng và khoa học nhất để các em dễ dàng mô tả thuật toán đúng  theo ý tưởng của mình. b.1 : Phương pháp biểu diễn từng bước: * Phương pháp:  ­ Các thao tác của giải thuật được liệt kê từng bước ­ Tại mỗi bước, sử dụng ngôn ngữ tự nhiên để diễn tả công việc phải làm. ­ Bước đứng trước (có số thứ tự nhỏ hơn) được thực hiện trước, thực hiện   xong bước này mới chuyển sang bước khác, không nhập nhằng. * Ưu ­ nhược điểm: ­ Dễ hiểu, dễ làm GV : Phạm Thị Bích Diệp Năm 12 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng ­ Phụ thuộc vào “cách hành văn” của người diễn đạt ­ Với những giải thuật phức tạp, cách diễn đạt này trở nên rườm rà,.. * Ví dụ: Thuật toán “Tìm vị  trí xuất hiện đầu tiên của một số  nguyên trong dãy   số nguyên đã cho”: ­ Bước 1: Nhập dãy số nguyên ­ Bước 2: Nhập số nguyên a ­ Bước 3: Gán cho phần tử so sánh (s) giá trị của số đầu tiên trong dãy ­ Bước 4: So sánh a với s      + Nếu a = s thì ghi nhận vị trí của phần tử s (p)      + Nếu a ≠ s và s chưa phải phần tử cuối cùng trong dãy thì gán s bằng   phần tử tiếp theo và lặp lại bước 4     + Nếu a ≠ s và s là phần tử cuối cùng của dãy thì gán p = 0 ­ Bước 5: Nếu p ≠ 0 thì đưa ra vị trí cần tìm là p, ngược lại thông báo không  tìm thấy. Kết thúc Thuật toán “Tìm ước số chung lớn nhất của 2 số nguyên dương a,b. ­ Bước 1: Nhập 2 số nguyên dương là a,b ­ Bước 2: So sánh giá trị a và b. Nếu a bằng b thì sang bước 3, ngược lại a  khác b thì sang bước 4 ­ Bước 3: Tìm được ước số chung là a và kết thúc chương trình. ­ Bước 4: Nếu a lớn hơn b thì  ư ớc số chung lớn nhất là a:=a­b và quay trở  lại bước 2. Ngược lại ước số chung là b:=b­a và quay trở lại bước 2 Thuật toán “giải phương trình bậc nhất dạng tổng quát bx + c = 0” ­ Bước1. Nhập b, c là các số nguyên. ­ Bước2. Nếu b = 0 chuyển đến bước 4 ­ Bước 3. Tính nghiệm phương trình x = ­ c /b và chuyển tới bước 5 GV : Phạm Thị Bích Diệp Năm 13 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng ­ Bước 4. Nếu c ≠ 0, thông báo phương trình đã cho vô nghiệm. ngược lại  (c = 0) thông báo phương trình có vô số nghiệm. ­ Bước 5. Kết thúc. Thuật toán “Tính chu vi, diện tích hình chữ nhật” ­ Bước1. Nhập hai cạnh a,b ­ Bước 2. Tính chu vi  C = 2*(a+b) ­ Bước 3. Tính diện tích  S = a*b ­ Bước 4. In chu vi C ­ Bước 5. In diện tích S ­ Bước 6. Kết thúc Thuật toán “Tìm giá trị lớn nhất của một dãy số nguyên” ­ Bước 1: Nhập N và dãy a1, ……, aN. ­ Bước 2: Max   a1 ; i   2 ; ­ Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc. ­ Bước 4: Nếu ai > Max thì Max   ai ;       i   i+1 ; rồi quay lại bước 3 ;  b.2 : Phương pháp biểu diễn bằng sơ đồ khối: * Phương pháp:  ­ Sử dụng mũi tên để quy định trình tự thực hiện các thao tác ­ Sử dụng các hình khối để minh hoạ cho các lệnh hay thao tác. + Khối bắt đầu + Khối kết thúc + Khối thao tác thực hiện tính toán + Khối kiểm tra điều kiện + Khối vào/ra dữ liệu + Khối gọi chương trình con,… GV : Phạm Thị Bích Diệp Năm 14 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng Các ký hiệu trong phương pháp biểu diễn này: ­ Gọi chương trình con A Khối bắt đầu và kết thúc Begin A End Thực hiện công việc A A ­ Kiểm tra điều kiện: Tùy thuộc  điều kiện(Đúng hay Sai) mà rẽ  nhánh thích hợp   Điều kiện Vào/ra dữ liệu sai Đúng Từ các khối ở trên có một số cấu trúc như sau: Cấu trúc rẽ nhánh § iÒu KiÖn Cấu trúc lặp Xö lý If…then… § iÒu KiÖn If…then… else… Né i dung lÆ p § iÒu KiÖn § óng while… do… Né i dung lÆ p Xö lý nÕu ®óng repeat… until… S ai Xö lý nÕu s ai § iÒu KiÖn * Ưu ­ nhược điểm: Đây là cách diễn đạt khoa học, có tính nhất quán cao * Ví dụ:    Be g in Thuật toán “Tính chu vi, di ện tích hình chữ nhật”      §äc  c ¹nh a,b C := 2*(a+b) S  := a*b   In ra C, S   GV : Phạm Thị Bích Diệp Năm 15 học 2013-2014 End Sáng kiến kinh nghiệm THCS Hải Cảng Thuật toán “Tính chu vi, diện tích hình tam giác” Be g in §äc  a,b,c (a+b>c ) and (b+c >a) and (a+c >b) S ai In “Không tạo thành TG” §ó ng begin C := (a+b+c ) p := C/2  S  := p * ( p a) * ( p b) * ( p c) Nhập N và dãy a1, .., aN In ra C,S Max   a1 , i   2 End Sai i  “Tìm giá tr >N Thuật toán ị lớn nhất của một dãy số nguyên” Đúng Đưa ra Max Ai > Max Đúng Max   ai i  i+1 GV : Phạm Thị Bích Diệp Năm 16 học 2013-2014 End. Sai Sáng kiến kinh nghiệm THCS Hải Cảng c. Tính chất của thuật toán: * Tính dừng:  Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện   các thao tác. * Tính xác định : Sau khi thực hiện một thao tác thì hoặc là thuật toán kết  thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo. * Tính đúng đắn : Sau khi thuật toán kết thúc, ta phải nhận được Output cần   tìm. Ví dụ: Với thuật toán tìm giá trị lớn nhất của dãy số nguyên đã xét ở trên Tính dừng : Vì giá trị của i mỗi lần tăng lên 1 nên sau N lần thì i> N, khi đó  kết quả phép so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc. Tính xác định : Thứ tự thực hiện các bước của thuật toán được mặc định  là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả các phép so   sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực  hiện. Tính đúng đắn : Vì thuật toán so sánh Max với từng số hạn của dãy số và   thực hiện Max ai nếu ai > Max nên sau khi so sánh hết N số hạng của dãy thì  Max là giá trị lớn nhất. 1.2.4 : Viết chương trình GV : Phạm Thị Bích Diệp Năm 17 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng ­ Viết chương trình là dùng ngôn ngữ lập trình cụ thể nào (Ngôn ngữ Pascal)   để diễn tả thuật toán, cấu trúc dữ liệu thành câu lệnh để máy tính có thể thực hiện   được và giải quyết đúng bài toán mà người viết chương trình mong muốn. Và đây   cũng là một trong những bước then chốt của người lập trình. ­  Sau khi đã có thuật toán ta phải lập trình để thực hiện thuật toán đó. Muốn  lập trình đạt hiệu quả cao, cần phải có kỹ thuật lập trình tốt. Kỹ thuật lập trình tốt  thể hiện ở kỹ năng viết chương trình, khả năng gỡ rối và thao tác nhanh. ­  Lập trình tốt không chỉ nắm vững ngôn ngữ lập trình là đủ, mà phải biết   cách viết chương trình một cách uyển chuyển, khôn khéo và phát triển dần dần để  chuyển các ý tưởng ra thành chương trình hoàn chỉnh. Để đạt được những điều trên   thì cơ bản học sinh phải nắm được cấu trúc chung của một chương trình Pascal cần   có những thành phần nào. Một chương trình Pascal có các phần: PROGRAM Tên_chương_Trình ; - Tên chương trình USES - Thư viện …… LABEL …… Phần khai báo - Nhãn CONST …… - Hằng TYPE ……. - Kiểu VAR - Biến ……. PROCEDURE …… FUNCTION …… BEGIN …… END. GV : Phạm Thị Bích Diệp Phần mô tả thủ tục / hàm chương trình con Bắt đầu thân chương trình chính Các câu lệnh của chương trình Kết thúc thân chương trình chính Năm 18 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng * Phần khai báo :             ­ Phần này bắt đầu bằng từ khóa Program rồi tiếp đến là tên của chương   trình và chấm dứt bằng dấu chấm phẩy (;).Tên chương trình phải được đặt theo  đúng qui cách của danh hiệu tự  đặt (thỏa mãn quy  ước đặt tên trong Pascal).  Phần này có hay không cũng được.  Ví dụ:  Program  Phuong_trinh_bac2 ; Program Vidu ; ­ Tiếp đến là khai báo các thư viện bằng từ khóa Uses. Mỗi ngôn ngữ lập  trình thường có sẵn một số  thư  viện cung cấp một số  chương trình   và lệnh  thông dụng đã được lập sẵn.Ví dụ  thư  viện crt, graph……Và để  sử  dụng các   chương trình đó thì phải khai báo thư viện chứa nó. Ví dụ:  Uses   crt ; {khai báo thư viện crt } Thư  viện crt trong Pascal cung cấp các chương trình có sẵn để  làm việc   với màn hình và bàn phím. Ví dụ  muốn xóa những gì đang có trên màn hình kết  quả  ta dùng lệnh Clrscr. (Nếu như  ta sử  dụng lệnh này mà không khai báo thư   viện Crt thì máy tính sẽ báo lỗi).            ­ Trình tự tiếp theo của một chương trình Pascal có thể có một số hoặc tất  cả các khai báo dữ liệu sau: LABEL    :  khai báo nhãn           CONST    :  khai báo hằng           TYPE       :  định nghĩa  kiểu dữ  liệu mới           VAR        :  khai báo các biến có dùng trong chương trình + Khai báo hằng thường được sử  dụng cho những giá trị  xuất hiện nhiều  lần trong chương trình  (có nghĩa là giá trị  nào thường xuyên xuất hiện trong   chương trình thì ta cần khai báo hằng) Ví dụ : Khai báo hằng  Const  MaxN = 1000 ; Pi = 3.1416 ; KQ = ‘Ketqua’ ; GV : Phạm Thị Bích Diệp Năm 19 học 2013-2014 Sáng kiến kinh nghiệm THCS Hải Cảng Và khi viết chương trình thay vì ghi giá trị cụ thể thì ta sử  dụng tên hằng   đã khai báo (đã khai báo hằng MaxN = 1000 thì quá trình viết chương trình chỉ   cần sử dụng hằng MaxN thay cho giá trị 1000) + Trong quá trình lập trình nếu phát sinh những kiểu dữ  liệu mới cần sử  dụng thì phải khai báo bằng từ khóa Type.  Ví dụ 1 :   Khai báo kiểu mảng một chiều Type Kmang = array [1 .. 100] of integer ; Ví dụ 2: Khai báo kiểu bản ghi  Type  Hocsinh = record Hoten : string [30] ; Ngaysinh : string [10] ; Tin, toan, ly : real ; End; + Tất cả  các biến dùng trong chương trình đều phải đặt tên và phải khai  báo (sử  dụng từ khóa Var) cho chương trình dịch biết để  lưu trữ  và xử  lí. Biến  chỉ nhận một giá trị tại mỗi thời điểm thực hiện chương trình. Tên biến dùng để  xác lập quan hệ giữa biến với địa chỉ bộ nhớ nơi lưu trữ giá trị biến và mỗi biến   chỉ được khai báo một lần.  Var < danh sách biến >  : < kiểu dữ liệu> ; Trong đó  : Danh sách biến là một hay nhiều tên biến, các tên biến được  viết cách nhau bởi dấu phẩy (,). Kiểu dữ liệu thường là một trong các kiểu dữ  liệu chuẩn hay kiểu dữ liệu do người lập trình định nghĩa. Ví dụ :  Var  x , y : real ; N : Kmang ; { Kmang đã được định nghĩa }     +Phần khai báo chương trình con (thủ tục Procedure hoặc hàm Function):  Phần này mô tả  một nhóm lệnh được đặt tên chung là một chương trình con để  khi thân chương trình chính gọi đến thì cả nhóm lệnh đó được thi hành. Phần này  có thể  có hoặc không tùy theo nhu cầu. Và trong chương trình tin học lớp 8 thì  GV : Phạm Thị Bích Diệp Năm 20 học 2013-2014