Đăng ký Đăng nhập
Trang chủ Giáo án - Bài giảng Sáng kiến kinh nghiệm Skkn hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán t...

Tài liệu Skkn hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính.

.DOC
27
1181
105

Mô tả:

Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN THÔNG TIN CHUNG VỀ SÁNG KIẾN 1. Tên sáng kiến: Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính. 2. Lĩnh vực áp dụng sáng kiến: Áp dụng trong giảng dạy lập trình môn tin học 11. 3. Thời gian áp dụng sáng kiến: Từ ngày 20, tháng 09, năm 2014 đến ngày 20, tháng 4, năm 2016. 4. Tác giả: Họ và tên: Nguyễn Thị Phương Ngân. Năm sinh: 1986. Nơi thường trú: Khu Tập thể giáo viên trường THPT Mỹ Tho. Trình độ chuyên môn: cử nhân sư phạm tin học. Chức vụ công tác: Giáo viên dạy môn Tin học. Nơi làm việc: Trường THPT Mỹ Tho. Điện thoại: 0975061791. 5. Đơn vị áp dụng sáng kiến: Tên đơn vị: Trường THPT Mỹ Tho. Địa chỉ: xã Yên Chính – Ý Yên – Nam Định. Trường THPT Mỹ Tho 1 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN MỤC LỤC Trang I. Điều kiện, hoàn cảnh tạo ra sáng kiến........................................................4 II. Mô tả giải pháp...........................................................................................5 1. Thực trạng....................................................................................................5 2. Các giải pháp trọng tâm..............................................................................5 2.1. Mục đích, yêu cầu.....................................................................................5 2.2. Nội dung.....................................................................................................6 2.2.1. Nhắc lại các bước lập trình giải bài toán trên máy tính.....................6 2.2.2. Một số khái niệm....................................................................................7 2.2.2.1. Khái niệm thuật toán..........................................................................7 2.2.2.1.1. Thuật toán là gì................................................................................7 2.2.2.1.2. Các tính chất của thuật toán...........................................................7 2.2.2.1.3. Vì sao phải lựa chọn thuật toán tối ưu...........................................7 2.2.3. Một số thuật toán cơ bản thường dùng................................................8 2.2.3.1. Thuật toán sắp xếp..............................................................................8 2.2.3.1.1. Bài toán.............................................................................................8 2.2.3.1.2. Thuật toán........................................................................................9 2.2.3.1.2.1. Thuật toán sắp xếp bằng tráo đổi................................................9 2.2.3.1.2.2. Thuật toán sắp xếp nhanh Qick-sort.........................................10 2.2.3.1.3. Nhận xét chung...............................................................................11 Trường THPT Mỹ Tho 2 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN 2.2.3.2. Thuật toán tìm kiếm.........................................................................11 2.2.3.2.1. Bài toán tìm kiếm...........................................................................11 2.2.3.2.1.1. Thuật toán tìm kiếm tuần tự......................................................12 2.2.3.2.1.2. Thuật toán tìm kiếm nhị phân...................................................13 2.2.3.2.2 Nhận xét chung...............................................................................14 2.2.4. Một số ví dụ minh chứng.....................................................................15 2.2.4.1. Ví dụ 1................................................................................................15 2.2.4.2. Ví dụ 2................................................................................................16 2.2.4.3. Ví dụ 3 (Đề thi học sinh giỏi tỉnh nam định năm học 2015 – 2016)..20 III. Hiệu quả do sáng kiến đem lại...............................................................23 1. Hiệu quả kinh tế.........................................................................................23 2. Hiệu quả về mặt xã hội..............................................................................24 IV. Đề xuất, kiến nghị:...................................................................................25 V. Cam kết không sao chép hoặc vi phạm bản quyền................................26 Trường THPT Mỹ Tho 3 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN Đề tài: Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính. I. Điều kiện, hoàn cảnh tạo ra sáng kiến Hiện nay trên thế giới, tin học ngày càng phát triển mạnh mẽ, có ứng dụng rộng rãi trong hầu hết các lĩnh vực của xã hội, sự phát triển của tin học được tính bằng giờ, cứ mỗi giờ lại có thêm phiên bản phần mềm tin học được nâng cấp hay có những phần mềm mới được tạo ra. Ở Việt Nam cũng vậy, tin học có mặt trợ giúp trong mọi ngành nghề, ở khắp mọi nơi, từ thành thị đến nông thôn và phổ biến với tất cả mọi người từ người già đến trẻ, từ những công nhân viên đến những người nông dân đều rất cần đến sự trợ giúp của tin học. Ngày nay, tin học đã trở thành một phần không thể thiếu trong cuộc sống của mỗi chúng ta. Lịch sử phát triển xã hội loài người đang ở nền văn minh thứ ba. Sự hình thành và phát triển của mỗi nền văn minh gắn liền với một công cụ lao động mới, chẳng hạn như máy hơi nước – đối với nền văn minh công nghiệp, máy tính điện tử - đối với nền văn minh thông tin. Máy tính chính là công cụ trợ giúp cho sự phát triển Tin học, có thể đáp ứng nhu cầu tính toán, lưu trữ, tìm kiếm,.., và xử lý thông tin một cách có hiệu quả. Máy tính có tốc độ xử lý nhanh (hàng tỉ lệnh trên 1 giây) nhưng nó cũng có giới hạn. Tất cả các máy tìm kiếm (ví dụ như google, yahoo hay gmail…) đều được lập trình bằng các đoạn lệnh của một Ngôn ngữ lập trình nào đó nhưng máy nào sử dụng thuật toán tối ưu (tốt nhất ) thì tìm kiếm được nhanh, chính xác và sẽ được đông đảo người dùng lựa chọn sử dụng. Trường THPT Mỹ Tho 4 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN Với một bài toán cũng vậy, một bài toán có thể có nhiều thuật toán để giải nhưng ta nên lựa chọn thuật toán tối ưu (có số phép tính ít nhất). Vậy việc lựa chọn một thuật toán đưa tới kết quả nhanh là một đòi hỏi thực tế cần được quan tâm đặc biệt. Do đó, trong khi viết chương trình ta nên tìm cách viết sao cho chương trình thực hiện càng ít phép toán càng tốt. Xuất phát từ thực tế đó tôi đưa ra đề tài: “Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính” nhằm định hướng cho các em học sinh biết phân tích, lựa chọn thuật toán tối ưu trước khi lập trình giải bài toán trên máy tính. II. Mô tả giải pháp 1. Thực trạng Nhận thấy tầm quan trọng của Tin học đối với thực tế cuộc sống, mọi lĩnh vực, ngành nghề, từ năm học 2007- 2008 Bộ giáo dục và đào tạo đã đưa môn Tin học thành môn học chính thức ở tất cả các trường Trung học cơ sở, Trung học phổ thông. Mỗi khối lớp được biên soạn chương trình từ cơ bản đến cụ thể từng vấn đề nhằm giúp học sinh có sự hiểu biết về Tin học, có sự tư duy, logic giữa Tin học với các môn học khác, từ đó giúp các em vận dụng vào thực tế. Trong chương trình Tin học 11 đi sâu vào dạy học lập trình, các em học sinh đã hiểu được những khái niệm cơ sở, kiến thức về lập trình, đã có thể vận dụng kiến thức để lập trình giải các bài toán trên máy tính. Tuy nhiên các em lập trình còn mang tính chất cảm tính, lập trình sao cho chương trình chạy được chứ chưa biết phân tích, lựa chọn thuật toán tối ưu để giải quyết bài toán. Trước thực tế đó tôi đưa ra đề tài: “Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính” nhằm định hướng cho các em biết thuật toán tối ưu là gì, vì sao phải lựa chọn thuật toán tối ưu, để từ Trường THPT Mỹ Tho 5 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN đó các em biết phân tích, lựa chọn thuật toán trước khi lập trình giải bài toán trên máy tính. 2. Các giải pháp trọng tâm 2.1. Mục đích, yêu cầu - Đề tài này đi sâu vào mục đích trao đổi cùng đồng nghiệp, các thầy cô giáo vai trò của việc lựa chọn được thuật toán tối ưu. - Giúp các em học sinh nhớ lại quy trình khi lập trình giải một bài toán trên máy tính, đặc biệt là bước lựa chọn thuật toán giải bài toán rất quan trọng. - Giúp các em học sinh hiểu được thuật toán ở đây là cái gì và vì sao nên lựa chọn thuật toán tối ưu để giải bài toán, từ đó đứng trước một bài toán học sinh biết nhận xét, phân tích các trường hợp để đề xuất, lựa chọn thuật toán tối ưu giải bài toán sao cho chương trình chạy nhanh hơn. - Thông qua một số thuật toán cơ bản (như sắp xếp, tìm kiếm,…) học sinh biết vận dụng để có thể giải quyết những bài toán phức tạp hơn. 2.2. Nội dung 2.2.1. Nhắc lại các bước lập trình giải bài toán trên máy tính Thông thường khi lập trình giải bài toán trên máy tính học sinh hay bị mắc sai lầm là viết chương trình luôn mà bỏ qua các bước giải bài toán trên máy tính, vì vậy có khi chương trình đã chạy nhưng sai kết quả vì hiểu sai đề, hoặc thuật toán chưa khả thi… Vì vậy khi dạy lập trình giáo viên nhắc học sinh không nên ngay lập tức viết chương trình mà nên nhớ lại các bước giải bài toán trên máy tính. Việc giải bài toán trên máy tính thường được tiến hành qua 5 bước sau: + Bước 1: Xác định bài toán; + Bước 2: Lựa chọn hoặc thiết kế thuật toán; + Bước 3: Viết chương trình; + Bước 4: Hiệu chỉnh; Trường THPT Mỹ Tho 6 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN + Bước 5: Viết tài liệu. Trong 5 bước giải bài toán trên máy tính thì bước lựa chọn hoặc thiết kế thuật toán đặc biệt rất quan trọng để các em có thể phân tích đề bài, tìm ra hướng giải, thuật toán phù hợp. 2.2.2. Một số khái niệm 2.2.2.1. Khái niệm thuật toán 2.2.2.1.1. Thuật toán là gì Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy từ Input của bài toán, ta nhận được Output cần tìm. 2.2.2.1.2. Cá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. 2.2.2.1.3. Vì sao phải lựa chọn thuật toán tối ưu a. Vì sao phải lựa chọn thuật toán tối ưu Sau khi đã xây dựng được một thuật toán và một chương trình tương ứng, mặc dù đã được cài đặt theo một thuật toán đúng và đáp ứng được các tính chất của thuật toán nhưng có thể không cho kết quả mong muốn đối với một bộ dữ liệu nào đó vì hoặc là nó đòi hỏi quá nhiều thời gian, hoặc là không có đủ bộ nhớ để lưu giữ dữ liệu và các biến của chương trình. Vì vậy ta cần phân tích thuật toán để đưa ra thuật toán tối ưu. b. Căn cứ vào đâu để xác định thuật toán là tối ưu Trường THPT Mỹ Tho 7 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN Với một bài toán, không chỉ có một thuật toán, vậy căn cứ vào đâu để có thể nói được thuật toán này nhanh hơn thuật toán kia? Ta có thể căn cứ vào thời gian và bộ nhớ cần thiết để thực hiện thuật toán. Trong đề tài này ta sẽ quan tâm đến thời gian thực hiện thuật toán. Việc đánh giá thời gian thực hiện của thuật toán dẫn tới một khái niệm “độ phức tạp về thời gian của thuật toán” đã được chứng minh và thường được gọi tắt là độ phức tạp của thuật toán, kí hiệu là O(..). Độ phức tạp của thuật toán càng nhỏ thì thuật toán càng chạy nhanh và khả thi. Thời gian thực hiện một thuật toán phụ thuộc vào rất nhiều yếu tố như: kích thước của dữ liệu đưa vào, lựa chọn, bố trí kiểu dữ liệu có hợp lý không… Vậy để tính toán thời gian thực hiện thuật toán ta sẽ đếm số câu lệnh mà nó thực hiện, hoặc trong một số trường hợp có thể đếm cụ thể phép tính số học, so sánh, gán…mà thuật toán đòi hỏi thực hiện hoặc có thể chạy trực tiếp chương trình bằng một ngôn ngữ lập trình cụ thể và thử nghiệm nó nhờ một số bộ dữ liệu nào đấy rồi so sánh kết quả thử nghiệm với kết quả mà ta đã biết. c. Ngôn ngữ thuật toán - Ngôn ngữ dùng để miêu tả thuật toán gọi là ngôn ngữ thuật toán. - Thuật toán thường được mô tả bằng một dãy các lệnh. Bộ xử lý sẽ thực hiện các lệnh đó theo một trật tự nhất định cho đến khi gặp lệnh dừng thì kết thúc. - Ngôn ngữ thuật toán bao gồm: + Ngôn ngữ liệt kê từng bước; + Sơ đồ khối; + Ngôn ngữ lập trình - Trong đề tài này tôi ưu tiên sử dụng ngôn ngữ liệt kê từng bước và ngôn ngữ lập trình Pascal. 2.2.3. Một số thuật toán cơ bản thường dùng Trường THPT Mỹ Tho 8 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN 2.2.3.1. Thuật toán sắp xếp 2.2.3.1.1. Bài toán * Bài toán: Cho số nguyên dương N và dãy A gồm N số nguyên: a 1, a2,…, aN. Sắp xếp dãy A thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau). * Ví dụ: Cho N=6, dãy A: 3 2 1 4 6 3 => Dãy sau khi sắp xếp: 1 2 3 3 4 6 2.2.3.1.2. Thuật toán Trong quá trình học tập và giảng dạy tôi đã được học và biết có rất nhiều phương pháp sắp xếp (chẳng hạn như sắp xếp kiểu lựa chọn, sắp xếp kiểu thêm dần, sắp xếp kiểu phân đoạn, sắp xếp kiểu vun đống, sắp xếp kiểu hòa nhập hai đường trực tiếp, sắp xếp tuần tự, tráo đổi, sắp xếp nhanh Quick sort…). Tuy nhiên trong chương trình tin học phổ thông tôi ưu tiên sử dụng phương pháp sắp xếp bằng tráo đổi và sắp xếp nhanh Quick-sort. Tôi nhận thấy: phương pháp sắp xếp bằng tráo đổi đơn giản dễ hiểu với học sinh, số lượng phép tính toán, chi phí thời gian thực hiện cũng không quá cao, tuy nhiên nếu tập dữ liệu đưa vào lớn thì phương pháp này bộc lộ hạn chế; còn phương pháp sắp xếp nhanh Quick sort thì quả là một thuật toán sắp xếp tuyệt vời, có chi phí thời gian thấp. Trong đề tài này tôi đưa ra hai thuật toán sắp xếp đó là: sắp xếp bằng tráo đổi và sắp xếp nhanh Quick sort để độc giả có sự so sánh và sử dụng linh hoạt trong trường hợp cụ thể. 2.2.3.1.2.1. Thuật toán sắp xếp bằng tráo đổi * Ý tưởng phương pháp: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đổi chỗ nào nữa. * Thuật toán: Trường THPT Mỹ Tho 9 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN Procedure sapxeptraodoi; Var i, j, tg: integer; begin For i:=1 to n-1 do For j:= n downto i+1 do If a[j]< a[j-1] then Begin Tg:=a[j]; A[j]:=a[j-1]; A[j-1]:=tg; End; End; * Nhận xét: Thuật toán trên sử dụng 2 vòng lặp for… => mỗi lần duyệt i phải thực hiện n-1 phép so sánh để tìm ra giá trị lớn nhất đẩy về cuối dãy. Vậy số n * (n  1) 2 phép toán cần thiết là: (n-1)+(n-2)+…+1= => Độ phức tạp của thuật toán xấp xỉ cỡ O(n2). 2.2.3.1.2.2. Thuật toán sắp xếp nhanh Qick-sort * Ý tưởng phương pháp: Để sắp xếp dãy trước tiên ta chọn một phần tử ngẫu nhiên trong dãy làm “chốt”. Mọi phần tử có giá trị nhỏ hơn “chốt” phải được xếp vào vị trí trước “chốt” (đầu dãy); mọi phần tử có giá trị lớn hơn “chốt” phải được xếp vào vị trí sau “chốt” (cuối dãy). Khi đó dãy cần sắp xếp được phân thành hai đoạn: một đoạn gồm các phần tử có giá trị nhỏ hơn “chốt”, một đoạn gồm các phần tử có giá trị lớn hơn “chốt”. Cứ tiếp tục sắp xếp lặp đi lặp lại như vậy với các đoạn con cuối cùng ta sẽ thu được dãy đã được sắp xếp theo chiều tăng dần. Trường THPT Mỹ Tho 10 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN * Thuật toán: procedure qs(l,h:longint); var i,j,k:longint; begin if l>=h then exit; i:=l; j:=h; k:=a[random(h-l+1)+l]; repeat while a[i]k do dec(j); if i<=j then begin if ij; qs(l,j); qs(i,h); end; * Nhận xét: Thuật toán Qick-sort có độ phức tạp cỡ ~ O(nlogn) 2.2.3.1.3. Nhận xét chung So sánh hai thuật toán trên ta thấy thuật toán sắp xếp nổi bọt tuy dễ cài đặt nhưng có độ phức tạp cỡ O(n 2) còn thuật toán Qick-sort chỉ có độ phức tạp cỡ O(nlogn), có nghĩa là thời gian thực hiện của Qick-sort nhanh hơn rất nhiều. Vậy tùy vào từng bài toán cụ thể mà ta nên lựa chọn phương pháp sắp xếp phù hợp. Nếu tập dữ liệu đưa vào nhỏ (<=10 3) thì không nhất thiết phải sử dụng Qick-sort còn nếu tập dữ liệu đưa vào lớn thì sử dụng thuật toán Qick-sort quả là một giải pháp tuyệt vời. Trường THPT Mỹ Tho 11 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN 2.2.3.2. Thuật toán tìm kiếm 2.2.3.2.1. Bài toán tìm kiếm Bài toán tìm kiếm được phát biểu như sau: Cho dãy A gồm N số nguyên khác nhau: a1, a2,…, aN và một số nguyên k. Cần biết có hay không chỉ số i (1<=i<=N) mà ai = k. Nếu có hãy cho biết chỉ số đó. * Ví dụ: Cho N=6, dãy A gồm các số: 4, 6, 3, 9, 2, 15 + Với k=9, trong dãy trên có số hạng a 4 có giá trị bằng k. Vậy chỉ số cần tìm là i=4. + Với k=5 thì không có số hạng nào trong dãy A có giá trị bằng k. * Trong mục này ta xét hai thuật toán: tìm kiếm tuần tự và tìm kiếm nhị phân. 2.2.3.2.1.1. Thuật toán tìm kiếm tuần tự * Xác định bài toán: - Input: dãy a gồm N số nguyên khác nhau a1, a2,…, aN và một số nguyên k. - Output: vị trí (vt) bằng chỉ số i mà a i = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k. * Ý tưởng: Trước hết ta so sánh k với a 1 nếu k = a1 thì vị trí là 1, nếu k <>a 1 ta so sánh tiếp k với a2. Nếu k = a2 thì vị trí của k là 2, còn trường hợp k <>a 2 thì so sánh tiếp k với a3… Quá trình trên được tiếp tục cho đến khi nếu k=a i (i<=n) thì vị trí là i, trường hợp k <> a i mà i>n thì k không có mặt trong dãy A. * Giải thuật TIM_KIEM_TUAN_TU: for i:= 1 to n do if a[i]=k then begin vt:=i; break; end; Trường THPT Mỹ Tho 12 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN if vt>0 then write(f2,'da tim thay tai vi tri:',vt) else write(f2,'khong tim thay'); * Nhận xét: Tìm kiếm tuần tự là kỹ thuật tìm kiếm rất đơn giản và cổ điển, trong thuật toán ta sử dụng thêm câu lệnh break để sau khi đã tìm thấy khóa k có trong dãy thì thoát luôn ra khỏi vòng lặp và kết thúc chương trình, điều này giúp giảm đi đáng kể số lượng phép toán. Ta thấy với giải thuật trên, trường hợp tốt nhất là tìm thấy khóa k nằm ngay đầu dãy thì chỉ cần 1 phép so sánh; trường hợp trung bình là khóa k nằm ở vị n 1 trí giữa dãy cần 2 phép so sánh, trường hợp xấu nhất là tìm thấy khóa k nằm ở cuối dãy cần n+1 phép so sánh => Thời gian thực hiện của giải thuật trên là ~ O(n). 2.2.3.2.1.2. Thuật toán tìm kiếm nhị phân * Xác định bài toán: - Input: dãy a gồm N số nguyên khác nhau a1, a2,…, aN (dãy A đã được sắp theo thứ tự tăng dần) và một số nguyên k. - Output: vị trí (vt) bằng chỉ số i mà a i = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k. * Ví dụ: Cho dãy A tăng dần: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18. Tìm số k=8 có trong dãy A không? Để giải bài toán này ta có thể sử dụng thuật toán tìm kiếm nhị phân. * Ý tưởng: So sánh khóa k với số hạng a Giua ở giữa dãy, trong đó Giua= [(n+1)/2]. Khi đó xảy ra một trong ba trường hợp: Trường THPT Mỹ Tho 13 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN + Nếu k = aGiua thì Giua là chỉ số cần tìm. Kết thúc việc tìm kiếm. + Nếu k > a Giua thì việc tìm kiếm k trên dãy gồm các số hạng a Giua+1, aGiua+2, …, aN; + Nếu k < aGiua thì việc tìm kiếm k sẽ thực hiện trên dãy gồm các số a 1, a2, …, aGiua-1 . Trong trường hợp một nếu k = a Giua thì việc tìm kiếm kết thúc quá đơn giản. còn nếu không thì cả hai trường hợp hai và ba đều đưa đến bài toán tìm kiếm trên bảng không lớn hơn [n/2] phần tử. Quá trình trên được thực hiện cho tới khi bảng liệt kê chỉ còn 1 phần tử và so sánh k với chính số hạng này. Việc tìm kiếm này giúp thu hẹp nhanh phạm vi tìm kiếm. Ta có thể mô tả thuật toán tìm kiếm nhị phân như sau: * Giải thuật TIM_KIEM_NHI_PHAN: i:=1;j:=n; while ia[giua] then i:=giua+1 else j:=giua; end; if a[i]=k then vt:=i else vt:=0; if vt>0 then writeln('da tim thay tai vi tri:',vt) else write('khong tim thay'); * Nhận xét: Trong giải thuật trên trường hợp tốt nhất là tìm thấy khóa k = a Giua thì việc tìm kiếm kết thúc quá đơn giản (chỉ cần 1 phép so sánh). Còn nếu không Trường THPT Mỹ Tho 14 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN trường hợp xấu nhất người ta cũng chứng minh được thời gian thực hiện của giải thuật trên là ~ O(log2n). 2.2.3.2.2 Nhận xét chung So với thuật toán tìm kiếm tuần tự, thuật toán tìm kiếm nhị phân thực hiện tìm kiếm trên bảng không lớn hơn [n/2] phần tử. Vậy trong trường hợp bảng liệt kê đã được sắp thứ tự thì thuật toán tìm kiếm nhị phân tốt hơn thuật toán tìm kiếm tuần tự rất nhiều, còn trong trường hợp dãy khóa chưa được sắp xếp thì thời gian chi phí cho sắp xếp cũng phải kể đến. Vì vậy tùy từng trường hợp đề bài ra ta nên cân nhắc lựa chọn thuật toán sao cho phù hợp để chi phí thực hiện là ít nhất. 2.2.4. Một số ví dụ minh chứng 2.2.4.1. Ví dụ 1 Giải bài toán cổ (SGK trang 51): Vừa gà vừa chó Bó lại cho tròn Ba mươi sáu con Một trăm chân chẵn Hỏi có bao nhiêu con mỗi loại? * Lựa chọn thuật toán cho bài toán: Bài toán cổ trên rất gần gũi với các em học sinh, các em có thể dễ dàng áp dụng toán học để giải ra kết quả. Có rất nhiều cách khác nhau để giải bài toán này. Một cách đơn giản và số phép toán thực hiện cũng tương đối ít, học sinh có thể dễ dàng đưa ra là: Gọi số gà là g; số chó là c. Khi đó ta sẽ có số chó nằm trong phạm vi từ 1 đến 25 và có thể dễ dàng xây dựng được chương trình như sau: Program bai_toan_co_1; Trường THPT Mỹ Tho 15 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN uses crt; var g,c: integer; begin clrscr; for c:=1 to 25 do begin g:=36-c; if ((4*c+2*g)=100) then write('So ga la: ',g,' So cho la: ',c); end; end. * Nhận xét: Ta thấy tổng số gà và chó là 36 và tổng số chân là 100. Giả sử tất cả là chó, thì số con tối đa là 100/4 = 25 (con); tối thiểu là 36 / 4 = 9 (con). Như vậy chúng ta chỉ cần sử dụng vòng lặp for từ 9->25. Cách này sẽ tối ưu hơn. Chương trình minh họa: Program bai_toan_co_2; uses crt; var g,c: integer; begin clrscr; for c:=9 to 25 do begin g:=36-c; if ((4*c+2*g)=100) then write('So ga la: ',g,' So cho la: ',c); Trường THPT Mỹ Tho 16 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN end; end. 2.2.4.2. Ví dụ 2 Cho mảng A gồm n phần tử. Hãy viết chương trình tạo mảng B[1..n], trong đó b[i] là tổng của i phần tử đầu tiên của A. ( Bài 2- Bài tập và thực hành 4SGK trang 66) * Xác định bài toán: + Input: mảng A gồm n phần tử; + Output: tạo mảng b[1..n], trong đó b[i] là tổng của i phần tử đầu tiên của a; * Để giải quyết 1 bài toán có thể có rất nhiều thuật toán để giải. Giả sử thoạt đầu có thể sử dụng chương trình sau (có trong SGK) để giải quyết bài toán này: program subsum1; const nmax=100; type myarray= array[1..nmax] of integer; var a,b:myarray; n,i,j:integer; begin randomize; write ('nhap n'); readln(n); { Tao ngau nhien mang gom n so nguyen} for i:=1 to n do a[i]:=random(300)-random(300); for i:=1 to n do write(a[i]:5); writeln; { Bat dau tao b} for i:=1 to n do Trường THPT Mỹ Tho 17 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN begin b[i]:=0; for j:=1 to i do b[i]:=a[i]+a[j]; end; { Ket thuc tao b} for i:=1 to n do write(b[i]:6); readln end. - Chạy thử chương trình với một số bộ test ngẫu nhiên ta có: n Mảng a Mảng b 3 103 226 -37 103 329 292 4 -106 -47 -212 48 -106 -153 -365 -317 9 -136 -122 -207 -63 95 152 60 55 -156 -136 -258 -465 -528 -433 -281 -221 -166 -322 * Quan sát từ đoạn{ Bat dau tao b} ta thấy phải sử dụng 2 vòng lặp for lồng nhau for i:=1 to n do begin b[i]:=0; for j:=1 to i do b[i]:=a[i]+a[j]; end; * Nếu sử dụng thuật toán trên thì máy tính phải thực hiện n(n+1)/2phép cộng. * Trong bài toán này ta thấy: b[1]=a[1] Trường THPT Mỹ Tho 18 Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin - KTCN b[i]=b[i-1]+a[i] , 1 độ phức tạp của thuật toán ~ O(n2), trong khi sử dụng cách 2 thì máy chỉ phải thực hiện n-1 phép cộng, tức độ phức tạp của thuật toán ~ O(n). Vì vậy nhờ việc phân tích như trên ta có thể tiết kiệm được một lượng tính toán đáng kể giúp chương trình chạy nhanh hơn. 2.2.4.3. Ví dụ 3 (Đề thi học sinh giỏi tỉnh nam định năm học 2015 – 2016) Sở công an Nam Định thực hiện công việc cấp thẻ căn cước công dân năm 2016. Mỗi ngày Sở tiếp nhận N người dân, người thứ i mất t i thời gian (phút) hoàn thành cấp thẻ. Biết rằng Sở cấp cho người dân theo thứ tự lần lượt, xong việc người này mới đến người tiếp theo. Yêu cầu: Em hãy xếp thứ tự cho N người dân sao cho tổng thời gian chờ và hoàn thành cấp thẻ của N người là ít nhất. Dữ liệu: vào cho trong tệp CANCUOC.INP - Dòng 1 là số tự nhiên N (N<=104) cho biết số lượng người dân. Trường THPT Mỹ Tho 20
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng