Giáo án Tin học lớp 11 - Tiết 25, 26: Bài tập thực hành 4

Bài tập thực hành 4
(Tiết PPCT: 25, 26)
	Ngày soạn: .
	Ngày ĐK giáo án: .........................
Người duyệt giáo án (TTCM duyệt, BGH duyệt):
.....................................................................................................................................
.....................................................................................................................................
I. Mục tiêu:
1. Kiến thức
- Củng cố lại các kiến thức cơ bản khi lập trình với kiểu dữ liệu mảng. 
- Làm quen với thuật toán sắp xếp đơn giản.
2. Kĩ năng
- Rèn luyện kĩ năng sử dụng kiểu dữ liệu có cấu trúc, kĩ năng diễn đạt thuật toán bằng chương trìn sử dụng dữ liệu kiểu mảng. 
- Rèn luyện kĩ năng nhận xét, phân tích và đề xuất cách giải bài toán sao cho chương trình chạy nhanh hơn. 
II. Chuẩn bị:
1. Chuẩn bị của giáo viên
- Phòng máy vi tính, máy chiếu Projector để hướng dẫn. 
2. Chuẩn bị của học sinh
- SGK, chương trình đã được viết sẵn. 
III. hoạt động dạy và học
1. Hoạt động 1: Tìm hiểu chương trình diễn đạt của thuật toán sắp xếp. 
a. Mục tiêu
- Học sinh hiểu chương trình và thuật toán sắp xếp đơn giản. 
b. Nội dung
Bài 1: Viết chương trình sắp xếp các phần tử của mảng theo thứ tự không giảm. 
- Chương trình minh hoạ: 
	Uses CRT;
	Const nmax=250;
	Type arrint=arrray[1...nmax] of integer;
	Var n,i,j,y:integer;
	a:arrint;
	Begin
	clrscr;
	Randomize;
	Write(‘Nhap n=’);
	Readln(n);
	For i:=1 to n do a[i]:=random(300)-random(300);
	For i:=1 to n do write(a[i]:5);
	Writeln;
	For j:=n downto 2 do
	For i:=1 to j-1 do
	If a[i]>a[i+1] then
	Begin
	t:=a[i];
	a[i]:=a[i+1];
	a[i+1]:=t;
	End;
	Writeln(‘Day so sau khi sap xep’);
	For i:=1 to n do write(a[i]:7);
	Writeln;
	Readln;
	End.
	- Yêu cầu: Soạn chương trình vào máy, chạy thử với các giá trị khác nhau của n. Rút ra nhận xét về thời gian thực hiện của chương trình. 
c. Các bước tiến hành
Hoạt động của giáo viên
Hoạt động của học sinh
1. Gợi ý cho HS thuật toán sắp xếp tăng dần. 
- Lấy một ví dụ thực tiễn: Người mù sắp xếp một dãy các viên bi theo kích thước không giảm. 
- Yêu cầu: Vạch ra các bước để sắp xếp các phần tử của một mảng không gian. 
2. Tìm hiểu chương trình ví dụ, sách giáo khoa trang 65. 
- Chiếu chương trình ví dụ lên bảng. 
- Hỏi: Vai trò của biến i, j trong chương trình? Mỗi vòng lặp For trong đoạn chương trình sắp xếp có ý nghĩa gì?
- Hỏi: ba lệnh tg:=a[i]; a[i]:=a[i+1]; a[i+1]:=tg; có ý nghĩ gì?
- Thực hiện chương trình, nhập dữ liệu để học sinh thấy kết quả chương trình. 
- Hỏi: Chương trình làm công việc gì?
3. Sửa chương trình để giải quyết bài toán ở câu b. 
- Đặt yêu cầu mới: Khai báo thêm biến nguyên Dem và bổ sung vào chương trình đoạn lệnh cần thiết để biến Dem tính số lần thực hiện tráo đổi trong thuật toán. In kết quả tìm được ra màn hình. 
- Hỏi: Đoạn chương trình nào dùng để thực hiện tráo đổi giá trị?
- Yêu cầu HS viết lệnh để đếm số lần tráo đổi. 
- Hỏi: Lệnh này được viết ở vị trí nào trong chương trình?
- Yêu cầu HS soạn chương trình vào máy. 
- Yêu cầu HS nhập dữ liệu vào của giáo viên và thông báo kết quả. 
- Đánh giá kết quả của học sinh. 
1. Chú ý theo dõi những dẫn dắt của giáo viên để trả lời câu hỏi. 
- Lần lượt lấy từng phần từ trái qua phải. 
- Cứ mỗi phần tử ta đem so sánh lần lượt với các phần tử đứng bên phải của nó. 
- Nếu nhỏ hơn thì đổi chỗ. 
2. Quan sát chương trình, suy nghĩ câu hỏi và trả lời. 
- Biến i, j dùng làm chỉ số. 
- Mỗi vòng lặp For ứng với mỗi phép duyệt lần lượt. 
- Dùng để đổi giá trị của hai phần tử a[i] với a[i+1].
- Quan sát giáo viên thực hiện chương trình. 
- Chương trình sắp xếp dãy số theo thứ tự không giảm. 
3. Quan sát yêu cầu mới, chú ý định hướng giải quyết của giáo viên. 
tg:= a[i]; a[i]:=a[i+1]; a[i+1]:=tg;
- Dem := Dem+1;
- Ngay sau đoạn lệnh tráo đổi. 
- Soạn chương trình vào máy, thực hiện chương trình và thông báo kết quả. 
- Nhập dữ liệu theo yêu cầu của giáo viên, thực hiện chương trìn và thông báo kết quả sau khi thực hiện. 
2. Hoạt động 2: Rèn luyện kĩ năng nhận xét, phân tích và đề xuất cách giải bài toán sao cho chương trình chạy nhanh hơn. 
a. Mục tiêu: 
- HS biết sử dụng kiểu mảng để lập trình giải một bài toán. Biết nhận xét, phân tích để đề xuất phương pháp giải hay. 
b. Nội dung:
Cho mảng A gồm n phần tử. Viết chương trình tạo mảng B[1...n], trong đó B[i] là tổng giá trị của i phần tử đầu tiên của mảng A. 
Chương trình minh hoạ: 
	Const nmax=100;
	Type myarray=arrray[1...nmax] of integer;
	Var n,i,j:integer;
	a,b:arrint;
	Begin
	Randomize;
	Write(‘Nhap n=’);
	Read;m(n);
	For i:=1 to n do a[i]:=random(300)-random(300);
	For i:=1 to n do write(a[i]:5);
	Writeln;
	For i:=1 to n do 
	Begin
	B[i]:=0;
	For i:=1 to n do write(B[i]:5);
 	Readln;
	End.
c. Các bước tiến hành
Hoạt động của giáo viên
Hoạt động của học sinh
1. Xác định bài toán
- Chiếu đề bài lên bảng. 
- Yêu cầu: Xác định dữ liệu vào, dữ liệu ra?
- Gợi ý để học sinh đề xuất thuật toán thô. 
2. Giới thiệu chương trình chưa cải tiến. 
- Chiếu chương trình diễn đạt thuật toán. 
- Thực hiện chương trình để học sinh biết thời gian thực hiện chương trình và kết quả của chương trình. 
- Hỏi: Trong chương trình phải thực hiện bao nhiêu phép cộng?
- Hỏi: Có cách nào để cải tiến?
- Lệnh này được thay lệnh nào trong chương trình? Viết ở vị trí nào?
3. Yêu cầu: Viết chương trình hoàn thiện.
4. Tiểu kết: Cùng một bài toán, có nhiều cách giải quyết khác nhau. Người lập trình cần chọn cách sao cho máy thực hiện nhanh nhất. 
1. Quan sát đề bài và trả lời câu hỏi. 
- Vào: Mảng A gồm n phần tử. 
- Ra: Mảng B gồm n phần tử.
- Tại vị trí i ta tính tổng giá trị các phần tử từ 1 đến i. 
2. Quan sát chương trình trên bảng. 
- Quan sát giáo viên thực hiện, nhận xét về thời gian thực hiện chương trình. 
- Phải thực hiện n(n+1)/2 phép cộng.
- Để tính bước thứ i, ta sử dụng kết quả đã tính ở bước thứ i-1.
B[i]:=B[i-1]+A[i];
- Thay đoạn lệnh
For j:=1 to i do B[i]:=B[i]+A[j];
3. Soạn chương trình vào máy, thực hiện chương trình và thông báo kết quả. 
- Nhận xét về thời gian thực hiện của chương trình này so với chương trình trước khi cải tiến. 
IV. Đánh giá cuối bài
- Thuật toán sắp xếp đơn giản. 
- Một bài toán có thể có nhiều cách viết thành một chương trình. Cần chọn cách có số phép tính ít nhất.