Sáng kiến kinh nghiệm THPT: Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán

SỞ GIÁO DỤC VÀ ĐÀO TẠO BẮC GIANG

TRƯỜNG THPT YÊN DŨNG SỐ 2

-----------&&&-------------

THUYẾT MINH

MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN

“ Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai

thác tư duy một số thuật toán”

Người thực hiện: Trần Thị Thơm

Giáo viên môn: Tin Học

Đơn vị: Trường THPT Yên Dũng số 2.

Yên Dũng, tháng 4 năm 2021

2

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

Độc lập – Tự do – Hạnh phúc

THUYẾT MINH MÔ TẢ GIẢI PHÁP

VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN

1. Tên sáng kiến: “Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai

thác tư duy một số thuật toán’’

2. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử : 09/2020

3. Các thông tin cần bảo mật: không có.

4. Mô tả các giải pháp cũ thường làm :

Thuật toán là nội dung quan trọng trong lập trình. Một học sinh không học

thuật toán vẫn có khả năng lập trình, nhưng nếu muốn là một lập trình viên giỏi thì

học sinh đó phải học thuật toán thật cẩn thận và chuyên xâu. Sau đây là một số giải

pháp vẫn được các thầy cô nhóm Tin – Trường THPT Yên Dũng số 2 áp dụng trong

quá trình giảng dạy thuật toán.

4.1. Giải pháp 1: Sử dụng phương pháp thuyết trình

Đây là phương pháp dạy học mà phượng tiện cơ bản dùng để thực hiện là lời

nói của giáo viên. Vì vậy, ưu điểm lớn nhất của phương pháp này là có thể truyền

tải một lượng lớn kiến thức tin học đến với người học.

Tuy nhiên, phương pháp thuyết trình còn hạn chế là làm cho học sinh thụ động

trong việc tiếp nhận và lưu giữ lại kiến thức. Đặc biệt là với phương pháp này chỉ

dừng lại ở việc tái hiện lại các kiến thức trong nhận thức của học sinh. Vì vậy,

phương pháp này chưa hướng tới mức độ thông hiểu đặc biệt là vận dụng của học

sinh. Đồng thời, học sinh chỉ rèn luyện kĩ năng ghi nhớ còn học sinh chưa được rèn

luyện kĩ năng phân tích, tổng hợp và tư duy logic. Dẫn đến hạn chế khả năng lập

trình sau này của học sinh.

3

4.2 Giải pháp 2: Sử dụng phương pháp vấn đáp

Đây là phương pháp dạy học mà ở đó giáo viên sẽ là người đưa ra các câu

hỏi và học sinh sẽ trả lời, học sinh có thể cùng nhau tranh luận hoặc tranh luận với

giáo viên, từ đó giúp học sinh tiếp thu được kiến thức của bài giảng.

Với phương pháp này, giáo viên tạo ra hứng thú, kích thích tư duy, làm việc

độc lập hoặc làm việc theo nhóm của học sinh.

Tuy nhiên, khi sử dụng phương pháp này, giáo viên cần phải chuẩn bị hệ thống

bài tập ở các mức độ nhận thức. Nhưng do thời lượng dành cho một chủ đề ôn tập

ngắn trong khi lượng kiến thức cần truyền tải cho học sinh nhiều nên giáo viên không

thể kiểm tra hết được kiến thức thu nhận cũng như sự chuẩn bị của học sinh.

5. Sự cần thiết phải áp dụng giải pháp sáng kiến:

Vậy với 2 giải pháp trên thì nội dung kiến thức thuật toán hầu như chỉ là lưu

giữ thụ động, ghi nhớ một cách máy móc (học thuộc) và chỉ dừng lại ở các thuật

toán cơ bản trong sách giáo khoa Tin Học 10. Dẫn đến tình trạng khi học lập trình

lớp 11 học sinh thường thấy môn học này rất khó (khó hiểu, khó làm) kể cả đối với

học sinh giỏi được chọn vào đội tuyển Tin học 11.

Trong quá trình ôn luyện đội tuyển học sinh giỏi năm 2019 – 2020 tôi đã vận

dụng các phương pháp mới với mục đích tạo hứng thú học lập trình cho học sinh:

phương pháp hoạt động nhóm, phương pháp khám phá, phương pháp nghiên cứu

trường hợp nhưng không hiệu quả. Cụ thể năm 2019 – 2020 đội tuyển học sinh giỏi

của trường đạt thành tích không tốt: 01 em giải khuyến khích, 01 em không có giải.

Nguyên nhân quan trọng là các em đội tuyển rất yếu về thuật toán.

Xuất phát từ vấn đề đó tôi mạnh dạn chọn nghiên cứu chuyên đề “Ứng dụng

thuật toán trong lập trình” và áp dụng vào trong quá trình giảng dạy đội tuyển trong

năm học 2020 – 2021.

4

6. Mục đích của giải pháp sáng kiến

6.1 Đối với giáo viên:

- Với sáng kiến kinh nghiệm ‘Ứng dụng thuật toán trong lập trình’, giáo viên tiếp

tục củng cố nâng cao chuyên môn của bản thân.

- Thông qua hệ thống kiến thức và bài tập được phân chia theo mức độ giáo viên có

thể đánh giá kết quả học tập của học sinh. Qua các nội dung giáo viên rèn luyện tư

duy logic và kĩ năng giải quyết vấn đề cho học sinh.

- Thay đổi thực trạng của đội tuyển, khắc phục nhược điểm của giải pháp cũ, góp

phần nâng cao chất lượng đội tuyển.

6.2 Đối với học sinh:

- Hệ thống lại kiến thức cơ bản về thuật toán từ đó giúp học sinh có thể hiểu, nhớ và

vận dụng các thuật toán cơ bản vào giải quyết các bài toán khó.

- Biết cách tính độ phức tạp thuật toán từ đó biết cách lựa chọn thuật toán tối ưu.

- Phát triển tư duy logic và hình thành kĩ năng giải quyết vấn đề.

- Tiếp cận với một số thuật toán tối ưu trong lập trình.

- Tạo hứng thú học lập trình cho học sinh.

7. Nội dung:

7.1 Thuyết minh giải pháp mới hoặc cải tiến

- Tên giải pháp: Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư

duy một số thuật toán.

- Nội dung:

7.1.1 Thuật toán

Khái niệm: là 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 ta nhận được output cần tìm.

Phân loại : + Thuật toán dưới dạng liệt kê

+ Thuật toán dưới dạng sơ đồ khối:

5

• : Thể hiện thao tác nhập xuất dữ liệu.

• : Thể hiện thao tác tính toán.

• : Thể hiện thao tác so sánh.

• : Chỉ chiều thực hiện thao tác.

Các bước xây dựng thuật toán:

+ Xác định bài toán: Xác định input và output.

+ Ý tưởng giải quyết bài toán.

+ Viết thuật toán.

+ Xác định độ phức tạp thuật toán.

Ví dụ: Tìm giá trị lớn nhất của dãy số gồm N số nguyên a1, a2, ..., aN.

+ Xác định bài toán

- Input: Số nguyên dương N và dãy N số nguyên a1,..., aN.

- Output: Giá trị lớn nhất Max của dãy số.

+ Ý tưởng:

• 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.

+ Thuật toán:

Liệt kê :

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.

Bước 4.1. Nếu ai > Max thì Max := ai;

Bước 4.2. i := i + 1 rồi quay lại bước 3;

6

Sơ đồ khối

Độ phức tạp thuật toán:

Tính độ phức tạp thuật toán:

+ Thời gian thực hiện một lệnh đơn không phụ thuộc vào kích thước dữ liệu

nên sẽ là O(1).

+ Thời gian thực hiện một câu lệnh hợp thành sẽ được tính theo quy tắc cộng

và quy tắc max.

+ Thời gian thực hiện câu lệnh điều kiện If: Giả sử thời gian thực hiện hai câu

lệnh thành phần dạng đủ là f(n) và g(n) thì thời gian thực hiện của câu lệnh

If sẽ được tính theo quy tắc max nên sẽ là O(max(f(n), g(n))).

7

+ Thời gian thực hiện câu lệnh lặp sẽ áp dụng theo quy tắc nhân, nghĩa là

O(k(n)F(n)) nếu k(n) là số lần lặp và f(n) là thời gian thực hiện câu lệnh trong

vòng lặp.

+ Hàm và thủ tục là một chương trình độc lập nên về nguyên tắc có thể áp dụng

các quy tắc trên để đánh giá thời gian thực hiện.

Ví dụ 1: Thuật toán tìm giá trị lớn nhất có độ phúc tạp : O(N)

Ví dụ 2:

(1) S:= 0;

(2) for i:= 1 to n do

(3) S:= S + A[i];

(4) for i:= 1 to n do

(5) For j:= 1 to n do

(6) S:= S +1;

Thời gian thực hiện chương trình phụ thuộc vào n:

+ Các lệnh (1), (3), (6) có thời gian thực hiện là O(1).

+ Lệnh lặp (2) có số lần lặp là n, như vậy thời gian thực hiện lệnh (2) là O(n)

+ Lệnh lặp (5) có số lần lặp là n, như vậy thời gian thực hiện là O(n). Lệnh lặp

(4) có số lần lặp là n, như vậy thời gian thực hiện là O(n2)

Vậy thời gian thực hiện đoạn chương trình trên là: max(O(1), O(n), O(n2)) = O(n2)

Kết luận: Một bài toán sẽ có nhiều thuật toán, nhưng một thuật toán chỉ giải quyết

được 1 bài toán. Đứng trước một bài toán học sinh sẽ hơn nhau ở việc lựa chọn

thuật toán cho bài toán. Thuật toán có độ phức tạp càng nhỏ thì khả năng lập trình

của học sinh càng tốt. Nếu học sinh muốn tiến sâu và tiến xa trong lập trình thì cần

và rất cần học tốt phần thuật toán. Đây là hành trang đầu đời và có tính quyết định

tới khả năng lập trình của học sinh trong tương lai.

8

7.1.2 Áp dụng thuật toán vào giải quyết các bài toán cơ bản và bài toán

nâng cao trong lập trình pascal Tin học 11. (Phụ lục I)

- Các bước tiến hành giải pháp:

Bước 1: Hệ thống lại toàn bộ kiến thức cơ bản về thuật toán, đặc biết chú ý

tới các thuật toán cơ bản đã học trong chương trình lớp 10.

Bước 2: Xây dựng hệ thống bài tập mức độ vận dụng đối với từng thuật toán

cơ bản trong bước 1.(thể hiện dưới dạng phiếu bài tập trong từng buổi học).

Bước 3: Tìm hiểu một số thuật toán tối ưu (sắp xếp nhanh, tìm kiếm nhị phân,

quay lui, quy hoạch động) và hệ thống bài tập mức độ vận dụng cao.

Trong quá trình tiến hành giải pháp

+ bước 1: học sinh thuần túy là viết thuật toán,

+ bước 2: ngoài viết thuật toán học sinh bắt đầu lập trình trên máy,

+ bước 3: học sinh chủ yếu lập trình dựa trên ý tưởng thuật toán giải

quyết bài toán.

- Kết quả khi thực hiện giải pháp:

+ Sản phẩm được tạo ra từ giải pháp: (Phụ lục II)

+ Bảng số liệu đánh giá kết quả trước và sau khi thực hiện giải pháp : Kết quả

thi học sinh giỏi văn hóa cấp tỉnh.

9

Năm 2019 – 2020: 1 giải khuyến khích.

Năm 2020 – 2021: 1 giải 3, 1 giải khuyến khích.

10

7.2 Thuyết minh về phạm vi áp dụng sáng kiến

Sáng kiến kinh nghiệm đề cập đến việc góp phần nâng cao hiệu quả ôn luyện

đội tuyển văn hóa cấp tỉnh môn Tin học 11 cho đối tượng học sinh trường Trung học

phổ thông Yên Dũng số 2 thông qua việc xây dựng hệ thống các thuật toán cơ bản,

nâng cao và hệ thống các bài tập ở mức vận dụng hoặc vận dụng cao.

7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến

- Tạo tiền đề vững chắc cho học sinh khi bước vào ngành công nghệ.

- Hình thành kĩ năng giải quyết vấn đề giúp học sinh giải quyết các vấn đề không

chỉ trong học tập mà còn cả trong cuộc sống. Đây là một tiêu chí quan trọng được

các công ti lớn sử dụng khi phỏng vấn xin việc.

- Thông qua mạng lưới truyền thông và các sản phẩm công nghệ sơ khai của học

sinh đã từng bước thay đổi quan điểm của phụ huynh về môn tin học. Từ đó niềm

tin của phụ huynh vào con em, vào môn học và vào nhà trường ngày càng được nâng

cao.

* Cam kết : Chúng tôi cam đoan những điều khai trên đây là đúng sự thật và không

sao chép hoặc vi phạm bản quyền

KT. HIỆU TRƯỞNG Yên Dũng, ngày 5 tháng 4 năm 2021

PHÓ HIỆU TRƯỞNG Tác giả sáng kiến

(Chữ ký, dấu) (Chữ ký)

Lê Đình Khương Trần Thị Thơm

11

PHỤ LỤC I

I. MỘT SỐ THUẬT TOÁN CƠ BẢN:

1. Kiểm tra nguyên tố .

1.1 Xác định bài toán

- Input: N là là một số nguyên dương.

- Output: "N là số nguyên tố " hoặc "N không là số nguyên tố ".

1.2. Ý tưởng: Ta nhắc lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu

nó có đúng hai ước khác nhau là và chính nó. Từ định nghĩa đó, ta suy ra

- Nếu N = 1 thì N không là số nguyên tố;

- Nếu 1 < N < 4 thì N là số nguyên tố;

- Nếu N > 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai

của N thì N là số nguyên tố.

1.3. Thuật toán

Liệt kê

Bước 1: Nhập số nguyên dương N;

Bước 2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;

Bước 3: Nếu N < 4 thì thông báo N nguyên tố rồi kết thúc;

Bước 4: i ← 2;

Bước 5: Nếu i > [√𝑁] thì thông báo N là sô nguyên tố rồi kết thúc.

Bước 6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;

Bước 7: i ← i + 1 rồi quay lại bước 5.

12

Sơ đồ khối:

1.4. Ví dụ mô phỏng:

Với N= 29

2 3 4 5 6 2 3

29/2 29/3 29/4 29/5 45/2 45/3

Chia hết Chia hết Không Chia Không Không Không Không không ? không? hết

29 là số nguyên tố 45 không là số nguyên tố

1.5. Độ phức tạp thuật toán: O(√𝑁 )

1.6. Bài tập vận dụng: (phiếu học tập 1 – Phụ lục II)

13

2. Sắp xếp tráo đổi: (EXCHANGE SORT)

2.1. Xác bài toán:

- Input: Dãy A gồm N số nguyên a1, a2, …, aN.

- Output: Dãy A đước sắp xếp lại thành dãy không giảm.

2.2. Ý tưởng: Với mỗi cặp số hạ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

sảy ra nữa.

2.3. Thuật toán:

14

2.4. Ví dụ mô phỏng:

2.5. Độ phức tạp thuật toán: O(N2)

2.6. Bài tập vận dụng: (Phiếu bài tập 3 – phụ lục II)

3. Tìm kiếm tuần tự: (SEQUENTIAL SEARCH)

3.1. Xác định bài toán:

- Input: Dãy A gồm N số nguyên a1, a2, …, aN và khóa k.

- Output: Chỉ số i mà ai = 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.

3.2. Ý tưởng:

Tìm kiếm tuần tự là một kỹ thuật tìm kiếm đơn giản. Nội dung của nó như sau: Bắt

đầu từ bản ghi đầu tiên, lần lượt so sánh khoá tìm kiếm với khoá tương ứng của các

bản ghi trong danh sách, cho tới khi tìm thấy bản ghi mong muốn hoặc đã duyệt hết

danh sách mà chưa thấy {Tìm kiếm tuần tự trên dãy khoá k[1..n]; hàm này thử tìm

xem trong dãy có khoá nào = X không, nếu thấy nó trả về chỉ số của khoá ấy, nếu

không thấy nó trả về 0. Có sử dụng một khoá phụ k[n+1] được gán giá trị = X}

15

3.3. Thuật toán:

3.4. Cài đặt

function SequentialSearch(X: TKey): Integer;

var i: Integer;

begin

i := 1;

while (i <= n) and (k[i] ≠ X) do i := i + 1;

if i = n + 1 then SequentialSearch := 0

else SequentialSearch := i;

end;

Dễ thấy rằng độ phức tạp của thuật toán tìm kiếm tuần tự trong trường hợp tốt nhất

là O(1), trong trường hợp xấu nhất là O(n) và trong trường hợp trung bình là Θ(n).

16

3.5. Ví dụ mô phỏng

3.6. Bài tập vận dụng: (Phiếu bài tập 3 – Phụ lục II)

II. MỘT SỐ THUẬT TOÁN TỐI ƯU VÀ BÀI TẬP VẬN DỤNG:

1. Tìm kiếm nhị phân (BINARY SEARCH)

Phương pháp tìm kiếm nhị phân được áp dụng trên mảng đã sắp thứ tự. Tức là

A[1] ≤ A[2] ≤ ... ≤ A[n]

1.1 Ý tưởng:

Giả sử cần tìm K trong đoạn A[L ... R] (L đoạn A[Giua] với Giua = (L + R) div 2

• Nếu A[Giua] < K nghĩa là đoạn A[L ... Giua] chứa toàn khóa < K. khi đó ta

tiến hành tìm kiếm K trên đoạn A[Giua+1 ... R]

• Nếu A[Giua] > X nghĩa là đoạn A[L ... Giua] chứa toàn khóa > K. khi đó ta

tiến hành tìm kiếm K trên đoạn A[R ... Giua - 1]

• Nếu A[Giua] = K thì tìm kiếm thành công (kết thúc quá trình tìm kiếm). Quá

trình tìm kiếm sẽ thất bại nếu một bước nào đó đoạn tìm kiếm là rỗng tức là L > R

1.2 .Cài đặt

* Code của ngôn ngữ lập trình PASCAL

Function TK_NhiPhan(K: Key): integer;

var L, R, Giua: integer;

Begin

L :=1; R := N;

While (L <= R) do

17

Begin

Giua := (L + R) div 2;

if A[Giua] = K then exit(Giua); {tìm thấy K thì trả ra vị trí của nó}

if A[Giua]< K then L := Giua + 1

else R := Giua – 1;

end;

exit(0); {không tìm thấy x thì trả ra kết quả bằng 0}

End;

1.3. Độ phức tạp thuật toán.

Người ta chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm nhị

phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(lgN). Tuy

nhiên không nên quên rằng trước khi sử dụng phương pháp tìm kiếm nhị phân thì

dãy khóa phải được sắp xếp, tức là thời gian chi phí cho việc sắp xếp phải được tính

đến.

1.4. Bài tập vận dụng

Bài 1. Dãy con (Đề thi HSG tỉnh Bắc Giang năm 2019 – 2020)

Cho một dãy số nguyên dương a1, a2, ..., aN (10 < N < 100.000), ai ≤ 10.000

với mọi i=1..N và một số nguyên dương S (S < 100.000.000).

Yêu cầu: Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có

tổng các phần tử lớn hơn hoặc bằng S.

Dữ liệu vào: Đọc từ file SUB.INP gồm 2 dòng, dòng 1 chứa N và S ở dòng đầu.

Dòng 2 chứa các phần tử của dãy.

Dữ liệu ra: Kết quả ghi vào file SUB.OUT, chứa độ dài của dãy con tìm được.

18

Ví dụ :

SUB.INP SUB.OUT

10 15 2

5 1 3 5 10 7 4 9 2 8

* Hướng dẫn giải:

Bài toán này có thể giải theo 2 cách sau:

Cách 1: dễ dàng giải bài toán với 1 cách làm trâu bò là xét 2 vòng lặp lồng

nhau để tìm tất cả các tổng của các đoạn con đồng thời kết hợp tìm đoạn con có tổng

>= S và có số phần tử ít nhất. Độ phức tạp là O(N2)

Cách 2: Sử dụng phương pháp tìm kiếm nhị phân để giải bài toán:

Gọi T[i] là tổng của các số A[1] đến A[i] (mảng tiền tố).

Vì A[i] là các số dương => Dãy T là dãy tăng dần.

Khi đó ta sẽ tiến hành tìm kiếm nhị phân trên dãy T như sau:

* Xét T[i]:

d = 1, c = i-1,

g = (d + c) div 2

Nếu T[i] – T[g] >= S thì kq = min(kq, i – g) và tìm kq tiếp tục ở đoạn bên phải T[g]

Nếu T[i] – T[g] < S thì tìm kq ở đoạn bên trái T[g].

Độ phức tạp là O(NlogN).

Bài 2: Đếm tam giác (Đề thi tin học trẻ tỉnh Bắc Giang năm 2019 – 2020)

Cho 3 dãy số dương A, B, C cùng có N phần tử. Hãy đếm xem có bao nhiêu bộ 3 số

A[i], B[j] và C[k] mà 3 số này là 3 cạnh của 1 tam giác.

Dữ liệu vào: từ file TRIANGLE.INP với cấu trúc:

- Dòng đầu chứa số nguyên n (n <= 1000)

19

- Dòng thứ hai chứa các số A1, A2, ..., An.

- Dòng thứ ba chứa các số B1, B2, ..., Bn.

- Dòng thứ tư chứa các số C1, C2, ..., Cn.

Các số Ai, Bi, Ci đều không vượt quá 104 và được ghi cách nhau bởi dấu cách.

Dữ liệu ra: file văn bản TRIANGLE.OUT gồm một số S duy nhất là số lượng bộ

ba số tìm được.

TRIANGLE.IN

TRIANGLE.IN P TRIANGLE.OU T TRIANGLE.OU T P

2 8 3 2

2 3 1 2 3

4 4 9 3 1

8 5 2 4 7

* Hướng dẫn:

Chúng ta có thể giải bài này bằng 2 cách như sau:

Cách 1: Bài toán được giải một cách dễ dàng bằng phương pháp vét cạn: dùng 3

vòng lặp lồng nhau để xét từng bộ ba số (ai, bj, ck).

Độ phức tạp là O(N3).

Cách 2: Ta có cách giải với độ phức tạp là O(N2*logN) như sau:

Trước hết ta giải bài toán phụ như sau: Cho dãy không giảm A, và hai số x <

y. Hãy sử dụng phương pháp tìm kiếm nhị phân để đếm xem có bao nhiêu số A[i]

thỏa mã x < A[i] < y.

Bài 3: Love in war (liw.pas) – Đề thi HSG cụm Yên Dũng năm 2019 – 2020

Nếu như nói đến chiến tranh là nói đến sự khốc liệt, sự mất mát, những đau khổ,

những hy sinh lớn lao thì khi nói đến tình yêu ta nghĩ tới sự êm dịu, ngọt ngào, hạnh

phúc. Chiến tranh có thể hủy diệt mọi thứ trên đường nó đi qua, những con người có

thể bị bao thương tật, biến dạng hình thể trong chiến tranh, song tình yêu như một

20

sức mạnh không thể giập vùi, tình yêu ấy đã giúp bao anh lính bộ đội cụ Hồ đã chắc

tay súng để bảo vệ tổ quốc và có niền tin vào một ngày mai đất nước độc lập thống

nhất, tình yêu bị kìm nén ấy sẽ lại bùng cháy và thăng hoa cùng dân tộc. Những con

người đấy phần đông là thanh niên, khi đó tại các trường đại học khi có lệnh tổng

động viên nhiều sinh viên cả nam nữ gác bút nghiên đi theo tiếng gọi của lịch sử.

Trường đại học hồi đó quản lý sinh viên bằng mã sinh viên, hai sinh viên khác nhau

sẽ có 2 mã khác nhau. Trong khi học tập các cặp nam nữ sinh viên đã nảy sinh những

tình cảm đẹp giành cho nhau. Các cặp nam nữ sinh viên nói trên ghi lại mã sinh viên

của nhau trước khi lên đường nhập ngũ để ngày giải phóng họ dễ tìm lại nhau trong

trường đại học.

Năm 1975, khi chiến tranh kết thúc, đất nước hoàn toàn giải phóng, những

sinh viên năm nào người đã ngã xuống trên mặt trận, một số may mắn còn lại và có

điều kiện quay về trường tiếp tục học tập. Biết rằng có n sinh viên nam và m sinh

viên nữ đã trở về trường. n sinh viên nam, trong hoàn cảnh chiến tranh khốc liệt, họ

đã để thất lạc mã số của những người sinh viên nữ và chỉ nhớ được mã sinh viên của

chính họ: b1, b2, b3, … bn; m sinh viên nữ vẫn giữ lại được mã sinh viên của mình:

g1, g2, g3,….,gm và của các sinh viên nam mà họ đã dành tình cảm thời sinh viên

trước đó: y1, y2, y3,….,ym (gi giữ yi). Cặp sinh viên bi và gj sẽ tìm được nhau nếu yj

= bi.

Yêu cầu: Em hãy thống kê xem có bao nhiêu cặp sinh viên nam nữ trong số trên có

thể tìm được nhau và chỉ ra các cặp sinh viên đó.

Dữ liệu vào: tệp LIW.INP gồm:

- Dòng 1: n m

- Dòng 2: mã sinh viên nam b1, b2, b3, … bn

- Dòng 3: mã sinh viên nữ g1, g2, g3,….,gm

- Dòng 4: mã các sinh viên nam mà sinh viên nữ đã dành tình cảm thời sinh viên

trước đó: y1, y2, y3,….,ym (gi giữ yi).

Dữ liệu ra: tệp LIW.OUT gồm:

21

- Dòng 1: Số cặp sinh viên nam nữ tìm được nhau.

- Các dòng tiếp theo là các cặp mã sinh viên nam nữ tìm được nhau, mã sinh viên

nữ được sắp tăng dần (gj1 < gj2 < LIW.INP LIW.OUT

…

Giới hạn: 1 <= n, m <= 104. 1 <= 8 6 2 4 4 1

bi, gi, yi <= 1016 1 7 5 3 11 2 7

4 2 10 12 6 6 11

Bài 4: Trung điểm – Đề thi HSG tỉnh Bắc Giang năm 2018 - 2019

Trên trục tọa độ Ox, cho N điểm khác nhau P1, P2, …., PN. Điểm Pi được gọi là trung

điểm của đoạn PjPk nếu 2Pi = Pj + Pk

Yêu cầu: Cho biết tọa độ của N điểm P1, P2, …., PN. Hỏi có bao nhiêu điểm là điểm

trung bình của các đoạn thẳng tạo ra từ các điểm đã cho?

Dữ liệu: vào từ tệp văn bản TDD.INP gồm:

- Dòng 1: Ghi số nguyên dương N

- Dòng 2: Ghi lần lượt các số x1, …, xN (|xi| ≤ 105) tương ứng là tọa độ của các

điểm P1, P2, …., PN

Kết quả: Ghi ra tệp văn bản TDD.OUT gồm một số duy nhất là kết quả tìm được

của bài toán.

Ví dụ:

TDD.INP TDD.OUT Giải thích

5 3 Đoạn 1: 5 -1, trung điểm 2

3 -1 2 5 4 Đoạn 2: 2 4, trung điểm 3

Đoạn 3: 3 5, trung điểm 4

22

2. Sắp xếp nhanh (QUICKSORT)

2.1. Ý tưởng: Sắp xếp dãy khoá k[1..n] thì có thể coi là sắp xếp đoạn từ chỉ số 1 tới

chỉ số n trong dãy khoá đó. Để sắp xếp một đoạn trong dãy khoá, nếu đoạn đó có ít

hơn 2 khoá thì không cần phải làm gì cả, còn nếu đoạn đó có ít nhất 2 khoá, ta chọn

một khoá ngẫu nhiên nào đó của đoạn làm "chốt" (Pivot). Mọi khoá nhỏ hơn khoá

chốt được xếp vào vị trí đứng trước chốt, mọi khoá lớn hơn khoá chốt được xếp vào

vị trí đứng sau chốt. Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm

hai đoạn khác rỗng mà mọi khoá trong đoạn đầu đều ≤ chốt và mọi khoá trong đoạn

sau đều ≥ chốt. Hay nói cách khác: Mỗi khoá trong đoạn đầu đều ≤ mọi khoá trong

đoạn sau. Và vấn đề trở thành sắp xếp hai đoạn mới tạo ra (có độ dài ngắn hơn đoạn

ban đầu) bằng phương pháp tương tự.

2.2. Cài đặt:

procedure QuickSort;

procedure Partition(L, H: Integer); {Sắp xếp dãy khoá k[L..H]}

var i, j: Integer;

Pivot: TKey; {Biến lưu giá trị khoá chốt}

begin

if L ≥ H then Exit; {Nếu đoạn chỉ có ≤ 1 khoá thì không phải làm gì cả}

Pivot := k[Random(H - L + 1) + L]; {Chọn một khoá ngẫu nhiên trong đoạn

làm khoá chốt}

i := L; j := H; {i := vị trí đầu đoạn; j := vị trí cuối đoạn}

repeat

while k[i] < Pivot do i := i while k[j] > Pivot do j := j - 1; {Tìm từ cuối

đoạn khoá ≤ khoá chốt}

+ 1; {Tìm từ đầu đoạn khoá ≥ khoá chốt}

{Đến đây ta tìm được hai khoá k[i] và k[j] mà k[i] ≥ key ≥ k[j]}

23

if i ≤ j then

begin

if i < j then {Nếu chỉ số i đứng trước chỉ số j thì đảo giá trị hai khoá k[i]

và k[j]}

〈Đảo giá trị k[i] và k[j]〉; {Sau phép đảo này ta có: k[i] ≤ key ≤ k[j]}

i := i + 1; j := j - 1;

end;

until i > j;

end;

Partition(L, j); Partition(i, H); {Sắp xếp hai đoạn con mới tạo ra}

begin

Partition(1, n);

end;

3. Quay lui: (BACKTRACKING).

3.1. Quay lui dùng để giải bài toán liệt kê các phương án. Mỗi phương án được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách

thử tất cả các khả năng. Giả sử phương án cần liệt kê có dạng x[1..n], khi đó thuật

toán quay lui thực hiện qua các bước:

Bước 1: Xét tất cả các giá trị x[1] có thể nhận, thử cho x[1] nhận lần lượt các giá trị

đó. Với mỗi giá trị thử gán cho x[1] ta sẽ:

Bước 2: Xét tất cả các giá trị x[2] có thể nhận, lại thử cho x[2] nhận lần lượt các giá

trị đó. Với mỗi giá trị thử gán cho x[2] lại xét tiếp các khả năng chọn x[3] … cứ tiếp

tục như vậy đến bước: …

Bước n: Xét tất cả các giá trị x[n] có thể nhận, thử cho x[n] nhận lần lượt các giá trị

đó, thông báo phương án tìm được .

24

Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các

phương án n phần tử dạng x[1..n] bằng cách thử cho x[1] nhận lần lượt các giá trị có

thể. Với mỗi giá trị thử gán cho x[1] bài toán trở thành liệt kê tiếp phương án n - 1

phần tử x[2..n].

3.2. Mô hình của thuật toán quay lui:

procedure Try(i: Integer);

begin

for do

begin

;

if then

else

begin

;

Try(i + 1); {Gọi đệ quy để chọn tiếp x[i+1]}

khác>;

end;

end;

end;

Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1)

25

3.3. Ví dụ:

Ví dụ 1: Liệt kê các dãy nhị phân độ dài N

Biểu diễn dãy nhị phân độ dài N dưới dạng x[1..n]. Ta sẽ liệt kê các dãy này

bằng cách thử

dùng các giá trị {0, 1} gán cho x[i]. Với mỗi giá trị thử gán cho x[i] lại thử các giá

trị có thể gán cho x[i+1].Chương trình liệt kê bằng thuật toán quay lui có thể viết:

program BinaryStrings;

const InputFile = 'BSTR.INP';

OutputFile = 'BSTR.OUT';

max = 30;

var x: array[1..max] of Integer;

n: Integer; f: Text;

procedure PrintResult; {In phương án tìm được}

var i: Integer;

begin

for i := 1 to n do Write(f, x[i]);

WriteLn(f);

end;

procedure Try(i: Integer); {Thử các cách chọn x[i]}

var j: Integer;

begin

for j := 0 to 1 do {Xét các giá trị có thể gán cho x[i], với mỗi giá trị đó}

begin

26

x[i] := j; {Thử đặt x[i]}

if i = n then PrintResult {Nếu i = n thì in kết quả}

else Try(i + 1); {Nếu i chưa phải là phần tử cuối thì tìm tiếp x[i+1]}

end;

end;

BEGIN

Assign(f, InputFile); Reset(f); ReadLn(f, n); {Nhập dữ liệu}

Close(f);

Assign(f, OutputFile); Rewrite(f); Try(1); {Thử các cách chọn giá trị x[1]}

Close(f);

END.

Vẽ cây ví dụ

27

3.4. Bài tập vận dụng:

Bài 1:Bài toán cái túi (Câu 3 đề thi cấp tỉnh V1 năm 2011-2012)

Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b. Có

n đồ vật cần đem theo. Đồ vật thứ j có trọng lượng là aj và giá trị sử dụng là cj (j =

1, 2, 3, ..,n). Hỏi rằng nhà thám hiểm cần đem theo các đồ vật nào để cho tổng giá

trị sử dụng của các đồ vật đem theo là lớn nhất?

Input: Vào từ file văn bản CAITUI.INP:

• Dòng đầu ghi 2 số nguyên dương n và b (n < 100).

• Dòng thứ hai ghi các số nguyên không âm a1, a2, .. ,an.

• Dòng thứ ba ghi các số nguyên không âm c1, c2, .. ,cn.

Output: Ghi ra file CAITUI.OUT:

• Dòng đầu ghi tổng giá trị các đồ vật đem theo ứng với phương án tìm được.

• Ghi chỉ số của các đồ vật đem theo

CAITUI.INP CAITUI.OUT

4 8 15

5 3 2 4 1 2

10 5 3 6

4. Quy hoạch động. (DYNAMIC PROGRAMMING)

4.1. Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy,

tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu

của một số hữu hạn các bài toán con.

4.2. Các bước cài đặt một chương trình sử dụng quy hoạch động:

+ Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng

phương án.

28

+ Dùng công thức truy hồi phối hợp những lời giải của những bài toán nhỏ đã

lưu trong bảng phương án để tìm lời giải của những bài toán lớn hơn và lưu

chúng vào bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải.

+ Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.

4.3. Ví dụ

Ví dụ 1: Bài toán Tính N! GT.PAS

Ta có định nghĩa như sau: n! = nếu

Cho một số nguyên dương n (0  n  13).

Yêu cầu: Hãy tính n! bằng phương pháp quy hoạch động (lập bảng phương án).

Dữ liệu vào: Ghi trong file văn bản GT.INP có cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương n.

Dữ liệu ra: Ghi ra file văn bản GT.OUT theo cấu trúc như sau:

- Dòng 1: Ghi giá trị tính được của n!

Ví dụ:

GT.INP GT.OUT

3 6

Thuật toán:

Gọi GT[i] là giá trị của i! (0  i  13)

Ta có công thức quy hoạch động như sau:

GT[i] := GT[i-1]*i;

Như vậy, việc tính n! sẽ được thực hiện bằng vòng lặp:

GT[0] :=1;

For i:=1 to n do

29

GT[i] := GT[i-1]*i;

Kết quả: giá trị của n! nằm trong phần tử GT[n].

Ví dụ 2: Dãy con đơn điệu:

Bài toán: Cho dãy số nguyên A = a1, a2, …, an. (n ≤ 1000, -10000 ≤ ai ≤ 10000).

Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự.

Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.

Đặc trưng:

Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta

sẽ dùng vòng For duyệt qua các phần tử A[i] trong dãy, các phần tử trong dãy có thể

được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng

dần từng đơn vị.

Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu.

Công thức quy hoạch động:

Hàm mục tiêu: f : độ dài dãy con.

Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên bảng phương

án là mảng một chiều. Gọi Li là độ dài dãy con tăng dài nhất, các phần tử lấy trong

miền từ A1 đến Ai và phần tử cuối cùng là Ai.

Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các

bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công

thức truy hồi để phối hợp kết quả của các bài toán con.

Ta có công thức QHĐ để tính Li như sau:

L[n+1] = 1. (Hiển nhiên)

Li = L[jmax] + 1 với mọi phần tử j thỏa mãn: 0 < j < i và Aj ≤ Ai

Tính Li: phần tử đang được xét là Ai. Ta tìm đến phần tử Aj < Ai có Lj lớn nhất.

Khi đó nếu bổ sung Ai vào đầu dãy con ...Aj ta sẽ được dãy con tăng dần dài nhất

xét từ A1...Ai.

30

Truy vết:

Tại bước xây dựng dãy L, mỗi khi tính L[i] := L[jmax] + 1, ta đặt T[i] = jmax.

Để lưu lại rằng: Dãy con dài nhất bắt đầu tại Ai sẽ có phần tử thứ hai kế tiếp là

Ajmax. Sau khi tính xong hay dãy L và T, ta bắt đầu từ 0.

T[0] là phần tử đầu tiên được chọn,

T[T[0]] là phần tử thứ hai được chọn,

T[T[T[0]]] là phần tử thứ ba được chọn ...

Quá trình truy vết có thể diễn tả như sau:

i := T[0];

while i <> n + 1 do

{Chừng nào chưa duyệt đến số an+1=+∞ ở cuối}

begin

i := T[i];

end;

Cài đặt : Ví dụ: với A = (5, 2, 3, 4, 9, 10, 5, 6, 7, 8).

Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ Li

và mảng giá trị T sử dụng để lưu trữ vị trí của các phần tử trong dãy con.

31

0 1 2 3 4 5 6 7 8 9 10 11 i

-∞ 5 2 3 4 9 10 5 7 8 +∞ 6 ai

L[i] 9 5 8 7 6 3 2 5 3 2 1 4

T[i] 2 8 3 4 7 6 11 8 10 11 9

Truy vết

Cài đặt:

Const max:=1000;

Var a, L, T: array [1..max+1] of longint;

N: longint;

Procedure nhapdl; { Nhap du lieu cho mang A}

Procedure QHD_daycondondieu;

Var I, j, jmax: longint;

Begin

A[0] := -32768; A[n+1] := 32767;

L[n+1] := 1;

For i:= n downto 0 do

Begin

Jmax:= n+1;

For j:= i+1 to n+1 do

If (A[j]>A[i]) and (L[j]> L[jmax]) then jmax:= j;

L[i] := L[jmax] + 1; T[i] := jmax;

End;

Writeln(‘Chieu dai cua day con la: ’, L[0] - 2);

32

{Truy vet tim va hien thi day con}

i:= T[0];

while i <> n+1 do

begin

write (A[i]); i:= T[i];

end;

End;

BEGIN

Nhapdl; QHD_daycondondieu;

END.

Như vậy độ phức tạp bộ nhớ của bài toán là O(n), độ phức tạp thời gian là O(n2).

Có một số phương pháp cài đặt tốt hơn so với phương pháp trên, cho chi phí thời

gian là O(nlogn), một trong những cách đó là dùng cây nhị phân.

4.4. Bài tập vận dụng:

Bài 1: Cho hai số nguyên dương M, N (0 ≤ M, N ≤ 100) và hai dãy số nguyên: A1,

A2,..., AM và B1, B2,..., B N. Tìm một dãy dài nhất C là dãy con chung dài nhất của

hai dãy A và B, nhận được từ A bằng cách xoá đi một số số hạng và cũng nhận được

từ B bằng cách xoá đi một số số hạng.

Dữ liệu vào trong file LCS.INP có dạng:

+ Dòng thứ nhất chứa M số A1, A2,..., AM

+ Dòng thứ hai chứa N số B1, B2,..., B N.

Dữ liệu ra trong file LCS.OUT có dạng:

+ Dòng thứ nhất ghi số k là số số hạng của dãy C.

33

+ Dòng thứ hai chứa k số là các số hạng của dãy C.

Hướng dẫn: Công thức QHĐ

Cần xây dựng mảng L[0..M, 0..N] với ý nghĩa: L[i, j] là độ dài của dãy chung dài

nhất của hai dãy A[0.. i] và B[0..j].

Đương nhiên nếu một dãy là rỗng (số phần tử là 0) thì dãy con chung cũng là rỗng

vì vậy L[0, j] = 0 với j = 1.. N, L[i, 0] = 0 với i = 1.. M. Với M ≥ i > 0 và N ≥ j > 0

thì L[i, j] được tính theo công thức truy hồi sau:

L[i,j] = Max{L[i, j-1], L[i-1, j], L[i-1, j-1] + x}

(với x = 0 nếu A[i] ≠ B[j] , x=1 nếu A[i]=B[j])

Bài 2: Biến đổi xâu:

a) Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu

Cho xâu ký tự X, xét 3 phép biến đổi:

b) Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X

X.

c) Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X.

bởi ký tự C.

Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu

X thành xâu Y.

- Dòng 1: Chứa xâu X (độ dài ≤ 100)

- Dòng 2: Chứa xâu Y (độ dài ≤ 100)

Input: file văn bản STR.INP

Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại

mỗi phép biến đổi.

34

STR.INP STR.OUT

PBBCEFATZ 7

QABCDABEFA PBBCEFATZ -> Delete(9) -> PBBCEFAT

PBBCEFAT -> Delete(8) -> PBBCEFA

PBBCEFA -> Insert(4, B) -> PBBCBEFA

PBBCBEFA -> Insert(4, A) -> PBBCABEFA

PBBCABEFA -> Insert(4, D) -> PBBCDABEFA

PBBCDABEFA -> Replace(2, A) -> PABCDABEFA

PABCDABEFA -> Replace(1, Q) -> QABCDABEFA

Hướng dẫn: Công thức QHĐ:

Hàm mục tiêu: f: số phép biến đổi.

Dễ thấy số phép biến đổi phụ thuộc vào vị trí i đang xét của xâu X và vị trí j đang

xét của xâu F. Do vậy để cài đặt cho bảng phương án ta sẽ dùng mảng 2 chiều.

Gọi L[i,j] là số phép biến đổi ít nhất để biến xâu Xi gồm i kí tự phần đầu

của X (Xi=X[1..i]) thành xâu Fj gồm j kí tự phần đầu của F (Fj=F[1..j]).

Công thức QHĐ:

L[0,j]=j

L[i,0]=i

L[i,j] =L[i−1,j−1] nếu Xi=Yj.

L[i,j] = min(L[i−1,j], L[i,j−1], L[i-1,j-1]) +1 nếu Xi≠Fj.

35

Bài 3: Xâu con chung dài nhất:

Cho 2 xâu X, Y. Hãy tìm xâu con của X và của Y có độ dài lớn nhất. Biết xâu con

của một xâu thu được khi xóa một số kí tự thuộc xâu đó (hoặc không xóa kí tự nào).

Hướng dẫn: Công thức QHĐ:

Gọi L[i,j] là độ dài xâu con chung dài nhất của xâu Xi gồm i kí tự phần đầu

của X(Xi=X[1..i]) và xâu Yj gồm j kí tự phần đầu của Y (Yj=Y[1..j]). Ta có công

thức quy hoạch động như sau:

L[0,j] = L[i,0] = 0

L[i,j] = L[i−1,j−1] + 1 nếu Xi=Yj

L[i,j] = max(L[i−1,j], L[i,j−1]) nếu Xi≠Yj.

Bài 4: Xâu đối xứng (Palindome):

Bài toán: Một xâu gọi là xâu đối xứng (palindrome) nếu xâu đó đọc từ trái sang phải

hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm

vào S để S trở thành xâu đối xứng.

Hướng dẫn: Công thức QHĐ:

Gọi L[i,j] là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở

thành đối xứng.

Đáp số của bài toán sẽ là L[1,n] với n là số kí tự của S. Ta có công thức sau

để tính L[i,j]:

L[i,i]=0.

L[i,j]=L[i+1,j−1] nếu Si=Sj

L[i,j]=max(L[i+1,j],L[i,j−1]) nếu Si≠Sj

36

PHỤ LỤC II

THIẾT KẾ BÀI GIẢNG ÔN LUYỆN ĐỘI TUYỂN

CHỦ ĐỀ / BÀI HỌC: THUẬT TOÁN TÌM GIÁ TRỊ LỚN NHẤT CỦA

DÃY SỐ.

Chủ đề gồm nội dung:

- Nội dung 1: Thuật toán tìm Max.

- Nội dung 2: Bài tập vận dụng.

I. MỤC TIÊU BÀI HỌC

Sau khi học chủ đề, học sinh cần:

- Biết cách viết thuật toán tìm giá trị lớn nhất của một dãy số.

- Biết đánh giá độ phức tạp thuật toán từ đó lựa chọn ra thuật toán tối ưu tương

ứng với từng bài toán.

- Biết vận dụng thuật toán vào giải quyết các bài toán trong thực tế và ở một

số các môn học: Toán, Lý, …

- Phát triển tư duy logic và bước đầu hình thành kĩ năng giải quyết vấn đề cho

học sinh.

- Bước đầu có cảm hứng và đam mê lập trình.

II. ĐỒ DÙNG DẠY HỌC

- Máy tính.

- Tài liệu: Sách giáo khoa tin học 10, cấu trúc dữ liệu và giải thuật.

- Phiếu học tập.

III. CÁC HOẠT ĐỘNG DẠY HỌC

1. Khởi động

- Mục đích: Tạo hứng thú cho học sinh trong việc tìm hiểu kiến thức.

37

- Phương pháp tiến hành: Giáo viên giao nhiệm vụ cho học sinh về nhà đọc và tìm

hiểu thuật toán tìm giá trị lớn nhất của dãy số với các nội dung:

+ Xác định bài toán.

+ Ý tưởng giải quyết bài toán.

+ Viết thuật toán.

+ Đánh giá độ phức tạp thuật toán.

- Định hướng kết quả: Học sinh hệ thống và nắm được thuật toán cơ bản tìm giá trị

lớn nhất trong chương trình lớp 10.

b. Hoạt động ôn tập

- Mục đích: Kiểm tra việc thực hiện nhiệm vụ của học sinh trong phần khởi động.

- Phương thức tiến hành: Yêu cầu học sinh hoàn thành phiếu học tập.

- Định hướng sản phẩm:

Nội dung Tìm giá trị lớn nhất của dãy số

Xác định - Input: Số nguyên dương N và dãy N số nguyên a1,..., aN.

bài toán - Output: Giá trị lớn nhất Max của dãy số.

Ý tưởng - Khởi tạo Max = a1

giải quyết - Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với Max, nếu

bài toán ai > Max thì Max nhận giá trị mới là ai.

Thuật toán Liệt kê :

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.

Bước 4.1. Nếu ai > Max thì Max := ai;

38

Bước 4.2. i := i + 1 rồi quay lại bước 3;

Sơ đồ khối

Độ phức - Độ phức tạp thuật toán là O(N)

tạp thuật

toán.

39

c. Luyện tập vận dụng và cũng cố

- Mục đích:

+ Giúp học sinh củng cố kiến thức về thuật toán tìm giá trị lớn nhất và vận

dung thuật toán đó giải quyết các bài toán khác.

+ Giúp học sinh đưa ra được ý tưởng tối ưu ( Sử dụng thuật toán sắp xếp).

- Phương thúc tiến hành: Giáo viên tổ chức cho học sinh làm bài tập vận dung:

Bài 1: Tìm giá trị nhỏ nhất của một dãy số nguyên.

Dãy A gồm N số nguyên a1, a2, …, aN (N<= 100). Viết thuật toán đưa ra giá trị

Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 thì giá trị nhỏ nhất của dãy là 1

nhỏ nhất của dãy.

Bài 2: Tìm giá trị lớn thứ nhì của một dãy số nguyên.

Dãy A gồm N số nguyên a1, a2, …, aN (N<= 100). Viết thuật toán đưa ra giá trị

Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 thì giá trị lớn thứ nhì của dãy là 8

lớn thứ nhì của dãy.

Bài 3: Tìm giá trị lớn thứ k của một dãy số nguyên.

Dãy A gồm N số nguyên a1, a2, …, aN (N<= 100). Viết thuật toán đưa ra giá trị

Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 với k = 2 thì giá trị lớn thứ 2 của dãy là 8

lớn thứ k của dãy (k nguyên dương có giá trị được nhập vào từ bàn phím)

40

MỘT SỐ HÌNH ẢNH SẢN PHẨM CỦA HỌC SINH

Thuật toán tìm Max và đếm số lượng số có giá trị bằng Max

41

Bài 1: Tìm giá trị nhỏ nhất của một dãy số nguyên.

Bài 3: Tìm giá trị lớn thứ k của một dãy số nguyên.

42

Bài 2: Tìm giá trị lớn thứ nhì của một dãy số nguyên.

43

MỘT SỐ PHIẾU HỌC TẬP ÁP DỤNG TRONG QUÁ TRÌNH GIẢNG DẠY

44

45

TÀI LIỆU THAM KHẢO

1. Giải thuật và lập trình - Lê Minh Hoàng - ĐHSP Hà Nội.

2. Tài liệu chuyên Tin Học quyển 1 - Hồ Sĩ Đàm (Chủ biên ) - NXB Giáo Dục.

3. Sách giáo khoa Tin Học 10 - Hồ Sĩ Đàm (Chủ biên ) - NXB Giáo Dục.

4. Trang http://vnoi.info.

5. Chuyên đề “Quy hoạch động” - Nguyễn Thanh Tùng - ĐHSP Hà Nội.

6. Quy hoạch động - Nhóm tác giả Trường THPT chuyên Bắc Giang.

7. Đề thi học sinh giỏi văn hóa cấp tỉnh Tin Học 11 từ năm 2018 đến 2021.

46

MỤC LỤC Trang

1. Tên sáng kiến ................................................................................................ 2

2. Ngày sáng kiến được áp dụng ....................................................................... 2

3. Các thông tin bảo mật .................................................................................... 2

4. Mô tả giải pháp cũ thường làm ..................................................................... 2

5. Sự cần thiết phải áp dụng giải pháp sáng kiến .............................................. 3

6. Mục đích của giải pháp ................................................................................. 4

7. Nội dung ........................................................................................................ 4

7.1 Thuyết minh giải pháp mới hoặc cải tiến ............................................ 4

- Tên giải pháp ................................................................................. 4

- Nội dung .......................................................................................... 4

7.1.1 Thuật toán ........................................................................ 4

7.1.2 Áp dụng thuật toán vào giải quyết các bài toán ............... 8

- Các bước tiến hành thực hiện giải pháp ......................................... 8

- Kết quả khi thực hiện giải pháp ...................................................... 8

+ Sản phẩm được tạo ra từ giải pháp ........................................ 8

+ Các bảng số liệu, biểu đồ so sánh .......................................... 8

7.2 Thuyết minh về phạm vi áp dụng sáng kiến ...................................... 10

7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến ........................ 10

Phụ lục I ............................................................................................................ 11

Phụ lục II .......................................................................................................... 36