trêng ®hsp hµ néi
K56A_Khoa CNTT
2
Giáo án số 2:Bài thực hành số 4
A. Mục đích , yêu cầu :
Học sinh củng cố lại được các kiến thức cơ bản khi lập trình với kiểu dữ
liệu mảng .
Học sinh biết nhận xét , phân tích , đề xuất các cách giải bài toán để cho
chương trình chạy nhanh hơn .
Làm quen với dữ liệu có cấu trúc và bài toán sắp xếp .
Yêu cầu học sinh có thái độ chủ động , tự giác trong khi thực hành
B. Phương pháp , phương tiện :
1. Phương pháp :
Kết hợp nhiều phương pháp dạy học như thuyết trình , vấn đáp , hình ảnh ...
với thực tế.
2. Phương tiện :
Đối với thầy : Phòng máy vi tính , giáo án .
Đối với trò : Sách giáo khoa , vở ghi lý thuyết , vở thực hành , máy tính
(nếu có ) , chương trình đã được viết sẵn .
C. Tiến trình lên lớp và nội dung bài giảng :
I_ổn định lớp :(1')
ổn định trật tự lớp .
Yêu cầu lớp trưởng báo cáo sĩ số .
II_Kiểm tra bài cũ: (3')
Câu hỏi kiểm tra bài cũ :Em hãy cho biết cách khai báo mảng ?
Câu trả lời mong muốn : Khai báo tên gọi có kiểu dữ liệu mảng một
chiều có dạng :
Var tên mảng :ARRAY[kiểu chỉ số] of kiểu thành phần;
Trong đó : - Var , ARRAY, of là từ khóa .
- Tên biến mảng là một tên gọi tự đặt .
- Kiểu thành phần là tên kiểu của phần tử mảng.
- Kiểu chỉ số:
+ Chỉ số có kiểu dữ liệu miền con : Cận_đầu ... Cận_cuối , trong
đó Cận_đầu , Cận_cuối xác định giá trị chỉ số đầu và chỉ số cuối .
trêng ®hsp hµ néi
K56A_Khoa CNTT
3
+ Chỉ số có kiểu dữ liệu liệt kê .
III_Nội dung bài giảng :
STT
Nội dung Hoạt động giữa thầy và trò T.gian
1. Đặt vấn đề và gợi động cơ
-
Thuy
ết tr
ình
:Như bài trước cô đã nói ,
hôm nay chúng ta sẽ thực hành về phần
mảng . Trong quá trình thực hành cô sẽ
kết hợp kiểm tra việc học lý thuyết của
các em và sẽ cho điểm .
1’
2. Nội dung bài giảng :
I_Bài 1:
a) Hãy tìm hiểu và chạy thử chương
trình thực hiện thuật toán sắp xếp dãy
số nguyên bằng thuật toán tráo đổi với
các giá trị khác nhau của n dưới
đây.Qua đó nhận xét về thời gian chạy
của chương trình ?
Uses Crt ;
Const Nmax=250 ;
Type ArrInt = array[1..Nmax] of
integer ;
Var n , i , j , t : integer ;
A : ArrInt ;
Begin
ClrScr;
Randomize ;
Write (‘Nhap n = ‘) ;
Readln(n);
For i :=1 to n do
A[i] :=random(300)- random(300);
- Thuyết trình : Đối với bài này các em
cần phải liệt kê được các bước cơ bản của
bài toán .
- Đặt câu hỏi : Bài toán này thực hiện
chương trình gì ? Nội dung của nó bao
gồm mấy bước cơ bản? Nêu giới hạn và
nội dung từng bước ?
Câu trả lời : Bài toán 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 , nó gồm 4 bước . Đó là :
+b1: Khai báo
Từ đầu chương trình đến “ A:ArrInt “ .
+b2: Thực hiện chương trình .
Từ “Begin“đến “writeln (‘Day so duoc sap
xep : ‘); “.
+b3: In kết quả ra màn hình
Tiếp theo đến “Readln“.
+b4: kết thúc chương trình (end).
- Đi vào từng bước và đặt câu hỏi cho
nhằm diễn giải cho học sinh hiểu. Từ đó
15’
trêng ®hsp hµ néi
K56A_Khoa CNTT
4
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 duoc sap xep : ‘) ;
For i := 1 to n do
Write (A[i] :7 );
Writeln ;
Readln
End.
- b1: Khai báo
+ Khai báo đơn vị chuẩn : Uses Crt ;
Uses là từ khóa ding để khai báo có
dùng các đơn vị chuẩn .
Crt là đơn vị chuẩn cung cấp phương
tiện xử lý màn hình , bàn phím .
+ Khai báo hằng Nmax =250 ( xác
định số phần tử tối đa của kiểu mảng ).
+ Khai báo kiểu mảng tên ArrInt :
Type ArrInt = array[1..Nmax] of
integer;
+ Khai báo các biến :
Var n , i , j , t : integer;
A : ArrInt ;
biết được những chỗ nào học sinh không
hiểu và cần giải thích cụ thể .
-Đặt câu hỏi : Sau từ khóa bắt đầu
chương trình thực hiện công việc gì ?
Câu trả lời :
+ Nhập vào n và gán n vào phần tử của
mảng A .
+ Thực hiện thuật toán sắp xếp .
- Đặt câu hỏi : Hãy nêu cách thực hiện
thuật toán của chương trình ?
Câu trả lời : Cách thực hiện thuật toán
là :
+ Dùng 2 biến i , j làm chỉ số .
+ Dùng 2 vòng For để đưa mảng vào , mỗi
vòng lặp For ứng với mỗi phép duyệt lần
lượt .
+ Lấy từng phần tử của mảng ra kiểm tra :
nếu A[i] >A[i+1] thì thực hiện tráo đổi vị
trí của 2 phần tử trên .Cứ như thế cho đến
phần tử cuối cùng của mảng . Nếu sai thì
dừng vòng lặp .
- Đặt câu hỏi :Như vậy 3 lệnh t := A[i] ;
A[i] := A[i+1] ; A[i+1] := t có ý nghĩa gì
?
Câu trả lời :3 lệnh trên dùng để đổi giá trị
của 2 phần tử A[i] và A[i+1] .
- Đặt câu hỏi : Nhận xét gì về thời gian
trêng ®hsp hµ néi
K56A_Khoa CNTT
5
- b2: Thực hiện chương trình.
+ Nhập vào n và gán n vào phần tử
của mảng A .
Xóa màn hình : ClrScr ;
Khởi hàm tạo sinh số ngẫu nhiên
Randomize ;
Các phần tử của mảng A lấy từ -299
đến 299 :
A[i] := Random(300) - Random(300) ;
+ Thực hiện thuật toán sắp xếp : Đưa
mảng vào bằng 2 vòng For . Lấy từng
phần tử của mảng ra kiểm tra và thực
hiện tráo đổi thông qua biến t .
t :=A[i];
A[i] := A[i+1];
A[i+1] := t ;
- b3: In kết quả .
In ra mảng 1 chiều : For i:=1 to n do
Write (A[i] :7);
Writeln ;
- b4: Kết thúc chương trình .
b) Khai báo thêm biến nguyên Dem và
bổ sung vào chương trình những câu
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 .Đưa
kết quả tìm được ra màn hình .
II_Bài 2 :
chạy của chương trình ?
Câu trả lời : Thời gian thực hiện
chương trình nhanh do chương trình lấy
từng phần tử của mảng ra kiểm tra chứ
không so sánh từng phần tử của mảng với
tất cả các phần tử còn lại (rất mất thời gian
).
- Đặt câu hỏi : Ta phải giải quyết phần
này như thế nào đây ? Biến Dem sẽ nằm ở
vị trí nào trong chương trình ?
Câu trả lời :
+ Khai báo : n , i , j ,t , d :integer ;
+ Bổ sung chương trình :
Dem :=0 ;
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 ;
Dem:=Dem+1 ;
End ;
- Thuyết trình : Các em hãy soạn chương
trình vào máy và nhập dữ liệu rồi đánh giá
kết quả .
20’
trêng ®hsp hµ néi
K56A_Khoa CNTT
6
Hãy đọc và tìm hiểu những phân tích
để viết chương trình giải bài toán :
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.
Program SubSum1;
Const max=100;
Type MyArray=array[1..max] of
integer;
Var A , B : MyArray;
n , i , j : integer ;
Begin
Radomize;
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 i :=1 to n do
Begin
B[i]:=0;
For j :=1 to i do B[i]:=B[i]+A[j];
End ;
For i :=1 to n do write (B[i] :6);
Readln
End.
- Đặt câu hỏi : Trước tiên các em cần xác
định dữ liệu đầu vào , dữ liệu đầu ra và
thuật toán để giải ?
Câu trả lời :
+ Vào : Mảng A gồm n phần tử.
+ Ra : Mảng B gồm n phần tử .
+ Thuật toán : tại vị trí i ta tính tổng giá
trị các phần tử từ 1 đến i .
-Đặt câu hỏi : Với đoạn chương trình trên
máy phải thực hiện bao nhiêu phép cộng ?
Câu trả lời : Máy phải thực hiện
n(n+1)/2 phép cộng .
- Đặt câu hỏi : Ta nhận thấy việc thực
hiên phép cộng để tạo ra phần tử mới cho
mang B phải lặp đi lặp lại rất nhiều lần .
Vậy có cách nào khắc phục được điều đó
không ?
Câu trả lời : Để tính bước i ta sử dụng kết
quả đã tính ở bước i-1 .
Do đó có đoạn chương trình khác là :
B[1]:=A[1] ;
For i :=2 to n do B[i]:=B[i-1]+A[i] ;