Tài liệu Sáng kiến kinh nghiệm phân bậc hệ thống bài tập xây dựng thuật toán giải bài toán trên máy tính

      SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ       TRƯỜNG THPT BA ĐÌNH NGA SƠN      SÁNG KIẾN KINH NGHIỆM    PHÂN BẬC HỆ THỐNG BÀI TẬP       XÂY DỰNG THUẬT TOÁN GIẢI BÀI TOÁN TRÊN MÁY TÍNH Họ và tên: Vũ Thị Huệ                    Chức vụ: Giáo Viên                         Đơn vị công tác: Trường THPT Ba Đình  Nga Sơn                              SKKN thuộc môn: Tin Học                                       THANH HOÁ NĂM  2016 Mục lục I.  Mở đầu.........................................................................................................1 1. Lý do chọn đề tài......................................................................................1 2. Mục đích nghiên cứu.................................................................................1 3. Đối tượng nghiên cứu...............................................................................1 4. Phương pháp nghiên cứu..........................................................................2 II. Nội dung sáng kiến kinh nghiệm..............................................................2      1. Cơ sở lý luận của vấn đề.........................................................................2      2. Thực trạng của vấn đề trước khi áp dụng sáng kiến kinh nghiệm........2      3. Giải pháp và tổ chức thực hiện................................................................3      4.  Hiệu quả của đề  tài nghiên cứu“ Phân bậc hệ thống bài tập xây dựng   thuật toán giải bài toán trên máy tính”...............................................................17 III . Kết luận và đề xuất……………………………………………………… 17 1.     Kết   ……………………………..17 luận……………………….………….. 2.   Đề   ………………………………………………………………….18 Xuất  I.   Mở đầu 1. Lý do chọn đề tài. Xây dựng thuật toán là định hướng và hình thành cho học sinh ý tưởng  lập trình giải các bài toán trên máy tính. Trong chương trình Tin Học lớp 10,   bài học số  4 “BÀI TOÁN VÀ THUẬT TOÁN” các em bước đầu được làm  quen và hình thành xây dựng các thuật toán đơn giản để giải các bài toán trong  chương trình phổ thông. Qua thực tế  giảng dạy cho các em cá nhân tôi nhận   thấy các em biết đưa ra các bài toán, hiểu khái niệm bài toán, biết xác định rõ  INPUT, OUTPUT và đưa ra các ý tưởng để giải các bài toán đó rất tốt.  Tuy nhiên, “ Thuật toán” hiểu môn na là thủ thuật để giải một bài toán,   mà còn rộng hơn là thuật giải, là sáng tạo và tư  duy của con người, không   phải của máy tính. Đó là một khái niệm mới và tương đối khó với các em học   sinh. Các em hãy còn nhiều lúng túng và khó khăn khi xây dựng thuật toán  cũng như mô tả cho thuật toán. Trăn trở với những vấn đề  này bản thân tôi đã tích cực nghiên cứu nội  dung sách giáo khoa, các tài liệu tập huấn dạy học, tham gia các chuyên đề  đổi mới phương pháp dạy học, đặc biệt tích cực dự  giờ  các đồng nghiệp  cùng môn và đúc rút kinh nghiệm, tôi lấy các ví dụ  gần gũi với các em trong  cuộc sống, tích hợp kiến thức từ  các môn học như  vật lý, toán học…từ  các   bài toán dễ  đến các bài toán khó và bám sát theo ba dạng cấu trúc lập trình:  Tuần tự, rẽ nhánh và lặp. Tôi đã mạnh dạn ứng dụng sáng kiến kinh nghiệm   “ Phân bậc hệ thống bài tập xây dựng thuật toán giải bài toán trên máy  tính”  vào giảng dạy và đã thu được các tiết học thực sự  lý thú và có hiệu  quả. 2. Mục đích nghiên cứu Đứng trước một bài toán cần giải trên máy tính, tôi muốn cho các em  hiểu việc  xác định bài toán, đặt vấn đề cho bài toán rồi tìm và xây dựng thuật   toán là vấn đề quan trọng, chủ chốt để viết lên chương trình. Các em sẽ phải   biết đưa ra các thuật toán với một tập hữu hạn các thao tác, phép toán…được  đặt tên, được thực hiện theo một trình tự  thích hợp đối với một đối tượng   nào đó để  đạt được điều mong muốn – Đó là một thuật toán tối  ưu. Các em  biết mô tả thuật toán đối với một số bài toán trong chuẩn kiến thức. Như vậy   việc lựa chọn ngôn ngữ viết chương trình để diễn tả thuật toán không còn là  vấn đề  khó khăn. Các em sẽ  thấy hứng thú và yêu thích môn học hơn. Giúp   các em có kiến thức về lập trình. 3. Đối tượng nghiên cứu ­  Là các thuật toán cho các bài toán có tính phân bậc từ dễ  đến khó và  theo ba cấu trúc lập trình: Tuần tự, rẽ nhánh và cấu trúc lặp, phù hợp với nội  dung chương trình và đối tượng dạy học Tin Học lớp 10. 1 ­ Tôi đã áp dụng với các em  học sinh khối 10 trường THPT Ba Đình –  Nga Sơn – Thanh Hóa, dạy cho các em biết và thấy được việc xây dựng thuật   toán giải bài toán trên máy tính không phải là khó, các em thực sự yêu thích và   đam mê lập trình Tin Học.  4. Phương pháp nghiên cứu Đề tài sử dụng phương pháp nghiên cứu xây dựng cơ sở lý thuyết, phân  tích tổng hợp, điều tra khảo sát thực tế và xử lý số liệu. II. Nội dung sáng kiến kinh nghiệm  1. Cơ sở lý luận của vấn đề Để  học tốt lập trình, dù là ngôn ngữ  nào thì xác định bài toán và trình  bày thuật toán là điều đầu tiên học sinh cần phải nắm vững. Thuật toán để  giải một bài toán là một khái niệm mới mẻ  và khó đối   với các em học sinh. Các em còn nhiều lúng túng, không tìm ra cách giải quyết  cũng như trình bầy một thuật toán, chưa hình dung được các bước thực hiện  theo trình tự để máy tính thực hiện, chưa mô tả được thuật toán bằng những  ví dụ. Các em chưa biết thực hiện hay lựa chọn được thuật toán tối ưu cũng  như chỉ ra ba tính chất của thuật toán là tính đúng đắn, tính chính xác và tính   dừng. Điều này sẽ   ảnh hưởng tới khả  năng tiếp thu về  kiến thức lập trình  của các em lại càng khó khăn hơn, dẫn đến các em có tâm lí học chán nản,   không thích học môn lập trình. Hiện nay trong các tài liệu về các ngôn ngữ lập trình, các ví dụ về thuật  toán còn hạn chế, rất ít, các tài liệu tham khảo về thuật toán cho các em học  sinh chưa có nhiều. Việc đưa ra hệ thống các bài tập có tính phân bậc cho các   em hoc sinh giúp các em dễ  dàng nắm bắt nội dung của bài học mà còn định   hướng và phát triển tư  duy cho các em về  khả  năng ngôn ngữ  lập trình, linh   hoạt và hình thành năng lực tích cực, thiết thực cho các em. Xây dựng cơ  sở  cả về lý thuyết lẫn vận dụng, đem lại hiệu quả cao cho người học và người   dạy.   2. Thực   trạng   của   vấn   đề   trước   khi   áp   dụng   sáng   kiến   kinh  nghiệm ­ Thực trạng việc dạy nội dung  “Bài toán và thuật toán”. Các ví dụ về bài toán và thuật toán như trong sách giáo khoa Tin Học 10, sách   bài tập, đó là các bài toán rất điển hình, hay và cũng rất khó với các em học   sinh.  Để các em có thể  tiếp thu được, mặc dù sách giáo khoa đã trình bầy rất  cụ  thể  từ  ý tưởng giải bài toán, thuật toán thực hiện, các ví dụ  mô tả  thuật  toán. Thế nhưng  làm thế nào để học sinh có thể hiểu, nắm vững và ghi nhớ  các thuật toán này, nhiều giáo viên vẫn chưa tìm ra cách giảng dạy phù hợp   với khả năng tiếp thu của các em, còn lúng túng trong cách truyền đạt, áp đặt  2 như  trong sách giáo khoa dẫn đến các em chỉ  nhớ  thuật toán máy móc chứ  không hiểu bản chất của thuật toán. Việc tiếp thu kiến thức của các em  không sâu và nhanh quên. ­ Thực trạng của việc học nội dung “ Bài toán và thuật toán”.  Các em còn gặp nhiều khó khăn trong quá trình nắm bắt cũng như việc mô tả  thuật toán nếu như tôi lấy ví dụ  bằng các bộ  INPUT khác. Rất ít các em tìm   được các bước để giải một bài toán, nếu có tìm được các em cũng không nhớ  lâu và nhớ  theo kiểu máy móc. Các em chưa hình dung ra được trình tự  thực   hiện các bước theo các chu trình khi điều kiện được thỏa mãn hay chưa, hay  quá trình thực hiện lặp đi lặp lại để thực hiện công việc. Hay nói đúng hơn là   các em chưa biết thể hiện theo các bước của thuật toán, lựa chọn thuật toán   tối ưu, chỉ ra được ba tính chất của thuật toán. Chính vì các hạn chế trên dẫn  tới chất lượng học sinh mắn bắt được thuật toán và mô tả  thuật toán còn ít,  làm cho kết quả môn học thấp. Cũng vì những kết quả  như  trên  nên khi lên  lớp 11 các em  rất bỡ ngỡ và cảm thấy xa lạ với môn học lập trình., khó khăn  để áp dụng các câu lệnh đã được  học để viết một chương trình cụ thể. ­ Kết quả.  Qua khảo sát  ở  các em khối 10 năm học 2014 – 2015, sau khi học xong bài  học số 4 “ Bài toán và thuật toán” khi chưa áp dụng những giải pháp phân bậc  hệ thống bài tập xây dựng thuật toán giải bài toán hướng tới lập trình giải các  bài toán trên máy tính, qua bài kiểm tra 15 phút với câu hỏi và kết quả  thu   được như sau. Câu 1. Hãy trình bầy thuật toán và mô tả cho thuật toán giải bài toán sau  bằng cách liệt kê hoặc bằng sơ đồ khối. a. Tính giá trị của  Y= 5 n 1 n n 1 . Đa số các em chưa hình dung và biểu diễn được chu trình lặp của biến  điều khiển, còn lúng túng khi mô tả  thuật toán, hiểu về  bản chất của thuật   toán chưa sâu. Cụ thể kết quả thu được . Lớp Số HS 10A 10B 10G 45 45 45 Nắm vững thuật toán Chưa nắm vững thụât toán Số lượng 25 18 12 Số lượng 20 27 33 % 56 40 27 % 44 60 73 Vậy nên tôi đã đưa ra các bài toán trong cuộc sống, gần với chương   trình học của các em như bài toán vo gạo, tính giá trị biểu thức, chuyển động  ném ngang, tính gia tốc của vật rơi tự do, giải phương trình bậc nhất một ẩn   hay đơn giản là bài toán tính chu vi, diện tích của hình chữ nhật, hình vuông,  khi biết trước các cạnh. Các em đã tiếp cận nhẹ  nhàng, làm rất tốt, từ  từ và  dần dần hiểu rõ về thuật toán, biết trình bày thuật toán từ dễ đến khó sau đó  hình dung và hiểu được cách giải  một bài toán  trên máy tính thực hiện.  3  sau đây là hệ thống các bài tập có tính phân bậc từ mức độ dễ đến khó  theo ba cấu trúc tuần tự, rẽ nhánh và cấu trúc lặp, dẫn dắt cho các em trước  khi làm quen tiếp thu với các ví dụ về thuật toán như trong sách giáo khoa Tin  Học lớp 10. 3. Giải pháp và tổ chức thực hiện a. Phân bậc hệ thống bài tập thuật toán theo cấu trúc tuần tự Các bài toán thực hiện theo cấu trúc tuần tự  các em dễ  hiểu, dễ  nắm   bắt hơn nhất, gần với các bài toán tự nhiên. Các em đưa ra ý tưởng và nhanh  chóng trình bày được các bước của bài toán. Từ đó ta dễ dàng dẫn dắt tới các   bước của thuật toán để giải các bài toán đó cho các em ở mức độ cao hơn. Bài toán 1: Thuật toán nấu cơm ( là công việc hàng ngày của các em) INPUT: Gạo, nước, nồi. OUTPUT: Cơm chín ngon. B1. Lấy gạo theo định lượng cần thiết; B2. Vo gạo rồi đổ gạo, nước vào nồi; B3. Đun sôi cạn nước; B4. Giữ nhỏ lửa; B5. Cách 5 phút một: Nếm cơm chín chưa? + Nếu chưa chín, quay lại B5; + Nếu cơm chín chuyển sang B6; B6. Tắt lửa và bắc nồi cơm ra, kết thúc; Bài toán 2: Bài toán luộc rau muống INPUT: Rau muống, nước, muối, nồi, chanh, mì chính. OUTPUT: Rau chín tới, nước xanh ngon. B1. Nhặt rau, rửa rau, rửa nồi, đổ nước vào nồi vừa đủ ăn; B2. Bắc nồi lên bếp, vắt 5 giọt nước chanh vào nồi, đun sôi nước; B3. Cho rau vào nồi khoảng 1 phút đảo rau một lần đến khi sôi đều, rau  mềm vừa tới thì tắt bếp; B4. Vớt rau ra đĩa, pha mì chính, muối, chanh vừa đủ vào nước rau;     Bài toán 3. Thuật toán tính tổng của hai số a và b nhập vào từ bàn phím. ­ INPUT: Hai số a, b. ­ OUTPUT: Tổng S. B1. Nhập a, b; B2. S←a+b; B3. Đưa ra S; Nhập   a,b B1 S   ←  a+b B2 S B3 Ví dụ:          B1.    7    9; 7       9 S      ← 7+9          16 4 B2.    S←7+9; B3.    16; Bài toán 4: Xây dựng thuật toán tính giá trị  biểu thức y= (3x 2+7x)/5, Với x  nhập vào từ bàn phím. ­ INPUT: x. ­ OUTPUT: Giá trị y. B1: Nhập x; B2: y ← (3*x*x+7*x)/5; Nhập   x B1 Y←  (3*x*x+7*x)/5; B2 Y B3 B3: Hiển thị y và kết thúc; Bài toán 5  : Thuật toán tính diện tích, chu vi của hình vuông có chiều dài các  cạnh là a nhập vào từ bàn phím. ­ INPUT: Độ dài các cạnh hình vuông là a.  ­ OUTPUT: S, C. B1. Bắt đầu; B2. Nhập độ dài cạnh là a; Bắt đầu Nhập   a S←  a*a, C← a+a+a+a; B3. Tính  S ← a*a, C← a+a+a+a;           B4. Hiển thị S, C ; S,   C           B5. kết thúc; Kết thúc Mô tả cho thuật toán Bắt đầu B1. Bắt đầu; B2.   7; B3. S←  7*7,  C← 7+7+7+7; B4.   49    28; B1 B2 B3 B4 B5 7 S←  7*7,  C← 7+7+7+7; 49   28 Kết thúc 5 B5. Kết thúc; Bài toán 6: Xây dựng thuật toán tính và đưa ra màn hình diện tích phần được   gạch chéo trong hình sau, với a(a>0) nhập vào từ bàn phím. Ý  tưởng:  Tính  diện  tích  hình  tròn  có  bán  kính  a,  diện  tích  phần  gạch  chéo  bằng  1/2  diện  tích  hình  tròn. ­  INTPUT: Số a >0.      ­  OUTPUT:  Diện tích phần gạch chéo Sgc Hình vẽ Nhập   a B1 Sgc←π*a*a/2 B2 Sgc B3 B1. Nhập a>0; B2. Sgc←π*a*a/2; B3. Hiển thi Sgc và kết thúc; Bài toán 7. Xây dựng thuật toán tính và đưa ra màn hình vận tốc v khi chạm   đất của một vật rơi từ độ  cao h, biết rằng v =  2 gh , trong đó g là gia tốc rơi  tự do và g=9,8m/s2. Độ cao h (m) được nhập từ bàn phím. ­ INPUT: Độ cao h. B1 Bắt đầu ­ OUTPUT: Vận tốc v. B1. Bắt đầu; B2: Nhập h; B2 Nhập h B3 v← ; B3: Tính v←  2 * g * h ; B4: Hiển thị v ; B5. Kết thúc; B4 v B5 Kết thúc 6 Bài toán 8: Xây dựng thuật toán hoán đổi gía trị của hai biến a và c qua biến  trung gian b ­ Ý tưởng: Chuyển gía trị của biến a sang biến b, chuyển gía trị của biến   c sang biến a sau cùng chuyển gía trị của biến b sang biến c. ­ INPUT: a,b,c. ­ OUTPUT: Giá trị của a và c đã được hoán đổi cho nhau. B1.  Nhập giá trị a, b; B2. b ← a; B3. a← c; B4. c←b; B5. Đưa ra giá trị mới của a và c rồi kết thúc; x Nhập a, b B1 x Ban đầu b ← a B2 x b lấy gía  trị của a a ← c B3 x a lấy giá  trị của c c ← b B4 c  lấy giá  trị của b Đưa ra giá trị mới của  a và c rồi kết thúc x x x B5 b. Phân bậc hệ thống bài tập Thuật toán theo cấu trúc rẽ nhánh Với cấu trúc rẽ  nhánh giúp cho học sinh biết lựa chọn thực hiện công   việc khi điều kiện được thoả mãn hay không thoả mãn, ban đầu tôi đưa ra bài  7 toán tìm giá trị lớn nhất của hai số a, b sau đó dẫn dắt tới bài toán tìm giá trị  lớn nhất của dãy số  nguyên, các em đã nắm bài rất tốt. Các ví dụ  sau đó sát  với cấu trúc lập trình rẽ nhánh chương trình Tin Học 11. Phần lớn tôi hướng   dẫn, gợi ý cho học sinh làm bằng hai cách liệt kê và sơ đồ khối. Bài toán 1: Xây dựng thuật toán tìm gía trị lớn nhất trong hai số nguyên a và b  được nhập vào từ bàn phím. ­ INPUT:  a, b là hai số nguyên. ­ OUTPUT: Đưa ra số Max là số lớn nhất trong hai số a, b. B1. Nhập a, b; B2. Nếu a>b thì Max← a; Nhập a, b B3. Nếu b>a thì Max← b; B4. Kết luận Max là số cần tìm và kết thúc; Sai Mô tả cho thuật toán B1. a=8,   b=5 ;  a  >  b Đúng Max ← a Max ← b Đúng   B2. a>b               Max ← 8 ;  Kết luận  Max cần tìm B4  Hiển thị Max = 8 và kết thúc ;  Bài toán 2. Xây dựng thuật toán kiểm tra một số được nhập vào từ bàn phím   là số âm hay số dương. ­ INPUT:   a. ­ OUTPUT: Kết luận a âm hoặc dương. B1 Nhập a   B1. Nhập số  a; B2. Nếu a>0  Kết luận a dương, đến B4; B3.  Kết luận a là số âm, đến B4 ; Sai B4. Kết thúc; a  >  0 Đúng a là số  dương a là số  âm Kết thúc  B2 B3 B4 8 Mô tả cho thuật toán B1.  36; B2.  36>0 số vừa nhập là một số dương;  B4. Kết thúc; Bài toán 3.  Xây dựng thuật toán giải phương trình bậc nhất ax+b= 0 với a, b   nhập từ bàn phím. ­ INPUT:  Hai số a, b. ­ OUTPUT: Kết luận về nghiệm của phương trình ax+b=0. B1. Nhập a, b; B2. Nếu a=0, b# 0 thông báo phương trình vô nghiệm và kết thúc; B3. Nếu a=0, b=0 thông báo phương trình có vô số nghiệm và kết  thúc; B4. a#0, x← ­b/a thông báo có nghiệm rồi kết thúc; B1 Nhập a,b,c B2 a = 0 b # 0 Đúng Phương trình  vô  nghiệm Đúng Phương trình  có vô số nghiệm Sai B3 a = 0 b =  0 Sai B4 a  ≠  0 Đúng x  ← ­b/a Kết thúc B5 9 Bài toán 4. Xây dựng thuật toán nhập ba số bất kỳ a, b, c. Hãy kiểm tra ba số  đó có thể là độ dài của một tam giác hay không? Nếu đúng hãy tính và hiển thị  chu vi của tam giác đó. ­ Ý tưởng: Ba số  a, b, c là ba cạnh của một tam giác khi thoả  mãn điều  kiện      (a+b>c) và (b+c>a) và (a+c>b) , chu vi Cv = a+b+c. ­ INPUT: Ba số a,b,c. ­ OUTPUT: Kết luận ba số đó có phải ba cạnh của 1 tam giác, nếu phải   tính chu vi Cv.   B1. Nhập ba số a,b,c; B2. Nếu (a+b>c) và (b+c>a) và (a+c>b) thông báo ba số là ba cạnh của một   tam giác, Cv  ← (a+b+c), đến B4; B3. Kết luận ba số không là ba cạnh của một tam giác, đến B4; B4. Kết thúc;  Bài toán 5: Xây dựng thuật toán tính giá trị của biểu thức             x y  nếu điểm (x,y) thuộc hình tròn bán kính r(r>0), tâm (a,b) B1 Nhập x, y, r Z =             x+y trong trường hợp còn lại B2 B1. Nhập x, y, r; x2+y2  <=  r2 B2. Nếu x2+y2 <= r2, Z ← |x| + |y|; Sai B3. Z ← x + y; B3 Z ← x + y Đúng Z ← |x| + |y| Đưa ra Z và  kết thúc B4 10 B4. Đưa ra Z và kết thúc; c.  Phân bậc hệ thống bài tập thuật toán theo cấu trúc lặp. Với dạng cấu trúc này học sinh khó nắm bắt hơn cả, các em khó hình  dung ra công việc khi biến điều khiển tăng lên và thực hiện quá trình lặp, các   ví dụ  mà tôi đã đưa ra sát với các bài toán tìm kiếm, kiểm tra số  như  trong   sách giáo khoa đã trình bầy, giúp cho các em nhanh chóng tiếp cận các bài toán  điển hình theo chuẩn kiến thức, kỹ năng. Các em làm quen với dãy số  lặp có quy luật và lặp không có quy luật.   Biến điều khiển có thể tăng từ giá trị  đầu đến giá trị  cuối hoặc có thể  giảm  từ giá trị cuối đến giá trị đầu. Bài toán 1. Xây dựng thuật toán tính tổng của 5 số tự nhiên đầu tiên. ­  Ý tưởng: Cộng lần lượt các số từ 0 đến 5,  gán kết quả cho biến S. ­ INPUT. Các số nguyên 0,1,2,3,4,5. ­ OUTPUT. Tổng S. B1. Nhập N; B2. i←1, S←0; B3. Nếu i> 5 thì đưa ra S và kết thúc; B4.  thì S ← S+ i; B5. Gán  i←i+1 quay lại B3; Ví dụ  mô tả quy trình thực hiện cho thuật toán trên  B1. Nhập  N=5; B2. i← 1, S← 0; B3. i=1<5;  B4. S← S+i= 0+1=1; 11 B5. i←i+1=1+1=2  quay lại B3; B3. i=2<5; B4. S←S+i=1+2=3; B5. i←i+1= 2+1=3 quay lại B3; B3. i=3<5; B4. S←S+i=3+3=6; B5. i←i+1=3+1=4 quay lại B3; B3. i=4<5; B4. S←S+i=6+4=10; B5. i←i+1=4+1=5 quay lại B3; B3. i=5; { chưa lớn hơn 5} B4. S←S+i=10+5=15; B5. i←i+1=5+1=6 quay lại B3; B3. i=6 >5 thuật toán kết thúc và đưa ra S=15;    Bài toán 2. Xây dựng thuật toán tính tổng các phần tử có giá trị dương trong  dãy số N phần tử a1, a2, a3…,aN. ­ Ý tưởng: So sánh lần lượt các phần tử trong dãy số  với 0, nếu a i>0 thì  cộng giá trị của  ai vào tổng d ­ INPUT: Số nguyên dương N và các a1, a2, a3,….aN. ­ OUTPUT: Tổng các số dương trong dãy d. B1. Nhập N, a1, a2, a3…,aN; B2.  i← 1, d← 0; B3. Nếu  i>N  thì đưa ra d và kết thúc; B4. Nếu ai>0 thì d←d+ai; B5 i←i+1 quay lại B3; Ví dụ: Cho dãy số có N=5 các phần tử a1=6, a2 = ­3, a3=45, a4=12, a5=­13 12 B1. Nhập N = 5     6    ­3    45  12    ­13  B2. i ← 1, d←0; B3. i=1<5; B4. a1=6>0, d←d+a1=0+6=6; B5. i←i+1=1+1=2 quay lại B3; B3. i=2<5; B4. a2= ­3<0; { Không tính d} B5. i←i+1=2+1=3 quay lại B3; B3. i=3<5;  B4. a3=45>0, d←d+a3=6+45=51; B5. i←i+1=3+1=4 quay lại B3; B3. i=4<5; B4. a4= 12>0, d←d+a4=51+12=63; B5. i←i+1=4+1=5 quay lại B3; B3. i=5;{ chưa lớn hơn 5} B4. a5=­13<0; {không tính d} B5. i←i+1=5+1=6 quay lại B3; B3. i=6>5 Thuật toán dừng lại và đưa ra tổng các phần tử có giá   trị dương  trong dãy đã cho là d= 63. Bài toán 3. Xây dựng thuật toán tìm vị  trí các phần tử có giá trị  dương trong  dãy số N phần tử a1, a2, a3…,aN. ­ Ý tưởng: So sánh lần lượt các phần tử ai của dãy số  với 0, nếu  ai  > 0  thì đưa ra i. ­ INPUT: Số nguyên dương N và N số a1, a2, a3…,aN. ­ OUTPUT: Vị trí các số dương trong dãy số aN. B1. Nhập N, a1, a2, a3…,aN; 13 B2. i← 1; B3. Nếu i>N thì kết thúc; B4. Nếu ai > 0 thì đưa ra i; B5 i← i+1 quay lại B3; Ví dụ: Cho dãy số có 4 phần tử N=4, a1=­7, a2=12, a3= 56, a4=­43. Mô tả thuật toán cho dãy số trên B1. N=4, ­7   12   56   ­43; B2. i←1; B3. i =10 Hiển thị i =2; B5. i←i+1=2+1=3 quay lại B3; B3. i=3<4; B4. a3=56>0 Hiển thị i=3; B5. i←i+1=3+1=4 quay lại B3; B3. i=4 ;{ i chưa nhỏ hơn 4} B4. a4= ­43<0; { không đưa ra chỉ số i=4} B5. i←i+1=4+1=5 quay lại B3; B3. i=5>4 Thuật toán dừng lại. Hiển thị kết quả  2  3; Bài toán 4. Xây dựng thuật toán đếm các số  âm trong dãy số  A={ a1,a2,,..,an}  cho trước. ­ Ý tưởng: So sánh các phần tử trong  dãy với 0, nếu ai<0 thì biến đếm d  tăng lên một đơn vị. ­ INPUT: Số nguyên dương N và N số a1, a2,,.., aN  của dãy A. 14 ­ OUTPUT: Số các số âm trong dãy d. B1. Nhâp số nguyên dương N và N số a1,a2,,..,aN; B2. i←1, d←0; B3. Nếu i> N thì đưa ra d rồi kết thúc; B4. Nếu ai <0 thì d←d+1; B5. i←i+1, rồi quay lai B3; Thuật toán thể hiện tính dừng khi i >N sẽ kết thúc. Ví dụ: Cho dãy số có 6 phần tử N=6 gồm các giá trị a1= 12, a2=­22, a3=36, a4=­ 15, a5=­67, a6=32. Mô tả thuật toán cho dãy số trên. B1. N=6, 12  ­22  36  ­15  ­67  32; B2.i←1, d←0; B3. i=10 ; {không tăng d} B5. i←i+1=1+1=2 quay lai B3; B3. i=2; { không tăng d} B5. i←i+1=3+1=4 quay lai B3; B3. i=40; { không tăng d} B5. i←i+1=6+1=7 quay lại B3; B3. i=7>N=6  Thuật toán dừng lại và đưa ra số phần tử âm trong  dãy số là 3 ;  Bài toán 5:  Xây dựng thuật toán  tính S= 1+3+5+…+ (2n­1) với N nhập vào  từ bàn phím. ­ INPUT: N ­ OUTPUT: Tổng S ­ Thuật toán có thể thực hiện với biến điều khiển tăng hoặc giảm hoặc theo  quy luật gán cho i. Cách 1.                                                                Cách 2 B1. Nhập N; B1. Nhập N; B2. i ← N, S←0; B2. i ← 1, S←0; B3. S← S+ (2*i­1); B3. S← S+ (2*i­1); B4. i←i­1; B4. i←i+1; B5. Nếu  i<=0đưa ra S  B5. Nếu  i>N  đưa ra S  và kết thúc; và kết thúc; B6. Quay lại B3 B6. Quay lại B3 Với cấu trúc lặp có quy luật như ví dụ bài toán 5 trên đây, tôi muốn học   B1. Nh sinh khai thác được quy luật tăng hay giảm c ủa biậ ếp N; n điều khiển, đó là những  mấu chốt của bài toán và tính tổng S theo biến điều khiển. Điều này hướng   ← 2*N­1, S←0; học sinh tới cấu trúc lặp trong các ngôn ngữB2. i  lập trình nói chung. B3. S← S+ i; B4. i←i­2; Cách 3                                                               Cách 4  B1. Nhập N; B2. i←1, S←0; B5. Nếu  i>0 Quay lại B3  B6. Đưa ra S và kết thúc; 16 B3. S← S+i; B4. i←i+2; B5. Nếu  i> 2*N­1  Đưa ra S  và kết thúc; B6: Quay lại B3 ­  Ví dụ mô tả cho thuật toán Theo cách 2                                                      Theo cách 4  B1. N=3; B1. N=3; B2. i←3, S←0; B2. i←(2*N­1)=(2*3­1)=5, S←0; B3. S← S+ (2*i­1)= 0+(2*3­1)=5; B3. S←S+i=0+ 5=5; B4. i←i­1=3­1=2; B4. i←i­2=5­2=3; B5. i=2>0; { đúng} B5. i=3>0; { đúng} B3. S← S+ (2*i­1)= 5+(2*2­1)=5+3=8; B3. S←S+i=5+3=8; B4. i←i­1=2­1=1; B4. i←i­2=3­2=1; B5. i=1>0; {đúng} B5. i=1>0; {đúng} B3. S← S+ (2*i­1)= 8+(2*1­1)=8+1=9; B3. S←S+i=8 +1=9; B4. i←i­1=0 ; B4.  i←i­2=1­2=­1 ; B5. i=0<1 đưa ra S= 9, Kết thúc; B5. i<=0 đưa ra S= 9, Kết thúc; Một số các bài toán các em có thể tìm hiểu nâng cao hơn.   Xây dựng và mô tả  thuật toán giải các bài toán sau: a.   Kiểm tra một số  nhập vào từ  bàn phím có phải   một số  hoàn hảo hay   không ? b. Tính   S1= 2 2 .... 2 c. Tính   S2= 1+ 1/2! +1/3!+…+1/n! 4.   Hiệu quả  của đề  tài nghiên cứu“ Phân bậc hệ  thống bài tập xây  dựng thuật toán giải bài toán trên máy tính”  17