Kiểu dữ liệu có cấu trúc - Bài 11: Kiểu mảng

Chương IV : KIỂU DỮ LIỆU CÓ CẤU TRÚC Bài 11 : KIỂU MẢNG I. MỤC ĐÍCH, YÊU CẦU :  Hiểu khái niệm mảng một chiều và hai chiều .  Hiểu cách khai báo và truy cập đến các phần tử của mảng .  Cài đặt được thuật toán của một số bài toán đơn giản với kiểu dữ liệu mảng một chiều .  Thực hiện được khai báo mảng, truy cập, tính toán các phần tử của mảng . II. PHƯƠNG PHÁP, PHƯƠNG TIỆN :  Phương pháp : Thuyết trình, vấn đáp .  Phương tiện : Máy chiếu, máy tính, phông chiếu hoặc bảng . III. LƯU Ý SƯ PHẠM :  Cần cho học sinh thấy cần phải có một kiểu dữ liệu mới, ích lợi của kiểu dữ liệu đó, có thể minh họa bằng hình ảnh .  Khi làm việc với mảng, học sinh khó hiểu nhất vẫn là cách truy xuất tới các phần tử của mảng. Cần làm rõ các khái niệm như : đánh số các phần tử của mảng, chỉ số, kiểu chỉ số. IV. NỘI DUNG BÀI GIẢNG : HOẠT ĐỘNG CỦA GIÁO VIÊN VÀ HỌC SINH NỘI DUNG Ổn định lớp : - Chào thầy cô . - Cán bộ lớp báo cáo sĩ số . - Chỉnh đốn trang phục . Trước khi vào bài, giáo viên đưa ra một số vấn đề cần giải quyết như sau : Với những kiểu dữ liệu như đã biết, làm thế nào để : - Lưu trữ và xử lý một dãy số ? - Lưu trữ và xử lý Họ và tên của một người ? - Lưu trữ và xử lý bảng kết quả thi tốt nghiệp ? HS : Đưa ra các phương án để trả lời cho 3 câu hỏi trên . GV : Các ngôn ngữ lập trình thường cung cấp một số kiểu dữ liệu được xây dựng từ những kiểu dữ liệu chuẩn gọi là kiểu dữ liệu có cấu trúc . Chương này chúng ta sẽ tìm hiểu một số kiểu dữ liệu trong ngôn ngữ Pascal để trả lời 3 câu hỏi trên . GV : Đưa ra ví dụ, cần lập lập trình xử lý một dãy số nguyên, hãy tìm cách lưu trữ một dãy số nguyên trong khi lập trình ? Bằng cách nào để lưu trữ được thông tin dưới dạng bảng khi lập trình ? HS : Đưa ra ý kiến . GV : Đánh giá ý kiến của học sinh, sau đó đưa ra mục đích của việc sử dụng cấu trúc mảng trong chương trình . GV : Đưa ra khái niệm mảng một chiều và một số yếu tố liên quan trong lập trình nói chung . Có thể sử dụng ví dụ trong SGK để học sinh dễ theo dõi, gõ trước chương trình để có thể sử dụng cho các phần tiếp theo . Trong lập trình thường có 2 loại mảng : - Mảng một chiều . - Mảng hai chiều . 1. Kiểu mảng một chiều - Mảng một chiều là một dãy hữu hạn các phần tử có cùng kiểu, mảng được đặt tên và mỗi phần tử mang một chỉ số. Để mô tả mảng một chiều ta cần xác định kiểu của các phần tử và cách đánh chỉ số các phần tử . Với mảng một chiều ta quan tâm đến : - Tên mảng một chiều . - Số lượng phần tử trong mảng . - Kiểu dữ liệu của phần tử . - Cách khai báo biến mảng một chiều . - Cách truy cập vào từng phần tử của mảng . Xét ví dụ : Nhập vào nhiệt độ trung GV : Đi sâu phân tích hai chương trình để cho học sinh nhận thấy sự tiện lợi khi sử dụng mảng . HS : Trong khi giáo viên phân tích hai chương trình, học sinh sẽ đưa ra ý kiến nhận xét về 2 chương trình. GV : Đưa ra cách khai báo mảng một chiều trong ngôn ngữ Pascal, giải thích ý nghĩa của các từ khóa mới . GV : Khai báo bằng cách nào tiện lợi hơn ? HS : Thường thì học sinh trả lời cách 1 tiện lợi hơn ? GV : Tùy trường hợp cụ thể mà ta dùng cách 1 hay cách 2 nhưng thông thường ta sử dụng cách 1 . GV : Sử dụng một sồ hình ảnh trực quan minh họa cho học sinh cấu trúc mảng và chỉ số của phần tử Chỉ 1 2 3 4 5 6 7 8 bình mỗi ngày trong tuần . Tính và đưa ra màn hình nhiệt độ trung bình của cả tuần và đếm số ngày có nhiệt độ lớn hơn nhiệt độ trung bình này . Quan sát hai chương trình viết bằng ngôn ngữ Pascal cùng để giải bài toán trên . - Chương trình 1 : Không sử dụng kiểu mảng . - Chương trình 2 : Sử dụng kiểu mảng một chiều . a> Khai báo mảng một chiều Trong ngôn ngữ Pascal, mảng một chiều được khai báo bằng hai cách như sau : Cách 1 : Var : Array[kiểu chỉ số] of ; Cách 2 : Type = Array [] of ; Var : ; Trong đó : - Type là từ khóa dùng để khai báo biến, Array là từ khóa để khai báo mảng . - Kiểu chỉ số thường là đoạn số nguyên liên tục có n1..n2, với n1 là chỉ số đầu và n2 là chỉ số cuối. - Kiểu thành phần là kiểu dữ liệu của phần tử mảng . - Để truy cập vào phần tử mảng ta viết : số Giá trị 53 81 62 18 26 41 24 53 Đưa ra một số khai báo mảng trong Pascal . GV : Đưa ra ví dụ . HS : Xây dựng thuật toán để giải bài toán (thuật toán đã học ở lớp 10) . GV soạn sẵn chương trình và cho học sinh quan sát chương trình . Nếu có nhiều thời gian, giáo viên sẽ tiến hành soạn chương trình từ đầu để học sinh có thể dễ dàng nhận ra các thao tác cần phải thực hiện khi viết chương trình . - [Chỉ số] Ví dụ : A[20] Truy cập phần tử mang chỉ số 20 trong mảng A . Ví dụ : Khai báo biến mảng thông qua kiểu mảng : Type ArrayInteger=Array[1..100] of Integer; ArrayReal=Array[1.50] of Real; Var A : Array[1..50]; B : Array[1..50] of Real; Khai báo mảng trực tiếp : Var A : Array[1..100] of Integer ; B : Arrat[1..50] of Real ; b> Một số ví dụ : Ví dụ 1 : Tìm phần tử lớn nhất của một dãy số nguyên . - Input : Số nguyên dương N và dãy số A1, A2, ….., AN - Output : Chỉ số và giá trị của số lớn nhất trong dãy - Ý tưởng : + Đặt số A1 là số lớn nhất (max) + Cho i lặp từ 2 đến N, nếu A[i]> thì đổi max = A[i] vả lưu lại vị trí i . Chương trình như sau : Program timmax ; Uses crt ; var a : array[1..250] of integer ; n,i,max,csmax : Integer ; Begin GV : Đưa ra ví dụ, nhắc lại ý tưởng của thuật toán . HS : Xây dựng thuật toán để giải bài toán (thuật toán đã học ở lớp 10) . GV soạn sẵn chương trình và cho học sinh quan sát chương trình . Nếu có thời gian, giáo viên sẽ tiến hành soạn chương trình từ đầu để học sinh có thể dễ dàng nhận ra việc chuyển đổi ngôn ngữ từ ngôn ngữ thuật toán sang ngôn ngữ lập trình . clrscr ; Write('Nhap n = ') ; Readln(n) ; For i := 1 to n do Begin Write('a[',i,'] = ') ; readln(a[i]) ; End ; max := a[i] ; csmax := 1 ; For i := 2 to n do If a[i] > max then Begin max := a[i] ; csmax :=i ; End ; Writeln('Gia tri lon nhat : ',max) ; Writeln('chi so ptu lon nhat : ',csmax) ; Readln ; End . Ví dụ 2 : Sắp xếp dãy số nguyên theo bằng thuật toán tráo đổi . - Input : Số nguyên dương N và dãy số A1, A2, …, AN - Output : Dãy A được sắp xếp theo thứ tự không giảm . - Ý tưởng : + Đổi để đưa số lớn nhất về vị trí cuối cùng . + Làm tương tự đối với những số còn lại . Chương trình như sau : Program sapxep ; Uses crt ; var A : Array[1..250] of integer ; GV : Đưa ra ví dụ, nhắc lại ý tưởng của thuật toán . HS : Xây dựng thuật toán để giải bài toán (thuật toán đã học ở lớp 10) . GV soạn sẵn chương trình và cho học sinh quan n,i,j,tg : Integer ; Begin clrscr ; Write('Nhap so phan tu mang n = ') ; Readln(n) ; For i := 1 to n do Begin Write('A[',i,'] = ') ; readln(A[i]) ; End ; For j := n downto 2 do Begin For i := 1 to j-1 do If A[i] > A[i+1] then Begin tg := A[i] ; A[i] := A[i+1] ; A[i+1] := tg ; End ; End ; Writeln('day sau khi sap xep : ') ; For i := 1 to n do write(a[i]:8) ; readln ; End . Writeln('chi so ptu lon nhat : ',csmax); readln ; End . Ví dụ 3 : Tìm kiếm nhị phân . - Input : Dãy số A1, A2,………, AN đã được sắp xếp tăng dần . - Output : Có hay không chỉ số i mà A[i] = k hoặc thông báo không tìm thấy . sát chương trình . Nếu có thời gian, giáo viên sẽ tiến hành soạn chương trình từ đầu để học sinh có thể dễ dàng nhận ra việc chuyển đổi ngôn ngữ từ ngôn ngữ thuật toán sang ngôn ngữ lập trình . - Ý tưởng : Xem lại thuật toán tìm kiếm nhị phân trong SGK lớp 10 . Chương trình như sau : Program sapxep ; Uses crt ; var A : Array[1..250] of integer ; n,i,k : Integer ; dau,cuoi,giua : Integer ; TK : boolean ; Begin clrscr ; Write('Nhap so ptu mang n = ') ; Readln(n) ; For i := 1 to n do Begin Write('A[',i,'] = ') ; readln(A[i]) ; End ; Write('nhap so can tim k : ') ; Readln(k); dau := 1 ; cuoi := n ; TK := false ; while (dau <= cuoi) and Not TK Do Begin giua := (dau+cuoi) div 2 ; If A[giua] = k then TK := true Else If a[giua]>k then cuoi := giua - 1 Else dau := giua + 1 ; End ; If TK then write('Chi so la : ',giua) else write(' Khong tim thay '); readln ; End . GV : Quay lại ví dụ về lưu trữ dữ liệu dạng bảng để các em nhận ra nhu cầu phải sử dụng mảng 2 chiều trong lập trình . GV : Khai báo cách nào tiện lợi hơn (tương tự mảng 1 chiều) ? HS : Thường thì học sinh vẫn chọn cách 1 . GV : Tùy theo trường hợp cụ thể nhưng thường thì cách 1 hay được dùng hơn . GV : Khi khai báo mảng 2 chiều cần chú ý điều 2. Kiểu mảng 2 chiều : - Mảng hai chiều là một bảng các phần tử cùng kiểu . Với mảng hai chiều ta quan tâm đến : - Tên kiểu mảng hai chiều . - Số lượng phần tử của mỗi chiều trong mảng . - Kiểu dữ liệu của phần tử . - Cách khai báo biến mảng hai chiều . - Cách truy cập vào từng phần tử của mảng . a> Khai báo mảng hai chiều - Trong ngôn ngữ Pascal, mảnh hai chiều được khai báo như sau : Cách 1 : Khai báo trực tiếp Var : : Array[kiểu chỉ số dòng, kiểu chỉ số cột] of < kiểu phần tử> ; Cách 2 : Khai báo gián tiếp thông qua khai báo kiểu mảng Type = Array[kiểu chỉ số dòng, kiểu chỉ số cột] of ; Var : ; gì ? HS : Tìm câu trả lời, GV gợi ý để các em chỉ ra được chỉ số của mảng, số dòng, số cột và kiểu của mỗi phần tử trong mảng . GV : Gọi một số học sinh lên khai báo một số biến mảng một chiều theo yêu cầu của giáo viên . Minh họa bằng hình ảnh mảng 2 chiều và chỉ số các phần tử mảng hai chiều cũng như cách viết truy cập phần tử mảng . GV cho học sinh quan sát chương trình và giải thích các lệnh trong chương trình, chú ý đi sâu vào các lệnh lặp để các em nhận ra thường thì ta sử dụng vòng lặp for - do để duyệt qua các phần tử mảng . GV nên soạn sẵn chương trình và cho các em quan sát chương trình, và chạy thử chương trình trên máy để các em tiện theo dõi . Program Timkiem; Uses crt; var A : Array[1..100,1..100] of Integer; i,j,n,m : Byte ; k,d : integer ; Ví dụ : Khai báo biến mảng thông qua kiểu mảng : Type ArrayInteger = Array[1..10,1..15] of Integer ; ArrayReal=Array[1..50,1..100] of Real ; Var A : ArrayInteger ; B : ArrayReal ; Khai báo mảng trực tiếp : Var A : Array[1..10,1..15] og Integer ; B : Aarray[1..50,1..100] og Real ; Cách truy cập vào phần tử của mảng hai chiều : [chỉ số dòng, chỉ số cột] Ví dụ : A[1,3], B[23,66],…… b> Một số ví dụ : Ví dụ 1 : Chương trình sau đưa ra màn hình bảng cửu chương . Program cuuchuong; Uses crt ; var A : Array[1..9,1..9] of Integer ; i, j : Byte ; Begin Clrscr ; Write(' Nhap so dong, so cot cua mang : ') ; Readln(m,n); For i := 1 to m do For j := 1 to n do Begin Write(' A[',i,',',j,'] = '); Readln(A[i,j]); End ; Writeln(' Mang vua nhap vao la : '); Writeln; For i := 1 to m do Begin For j := 1 to n do Write(a[i,j]:4) ; Writeln; Writeln; End; Write(' Nhap gia tri k : '); Readln(k) ; d := 0 ; For i := 1 to m do For j := 1 to n do If a[i,j] < k then Begin write('So nho hon ',k,' la '); write(a[i,j]:8); d := d+1 ; End ; If d = 0 then Write('Khong co ptu nao nho hon ',k); readln; End . Begin Clrscr ; Writeln('Bang cuu chuong 1 -> 9 : '); Writeln ; For i := 1 to 9 do For j := 1 to 9 do A[i,j] := i*j ; For i := 1 to 9 do Begin For j := 1 to 9 do Write(a[i,j]:4); Writeln ; Writeln ; End ; Readln ; End . Ví dụ 2 : Chương trình sau nhập vào một mảng 2 chiều và số nguyên k, sau đó in ra các phần tử có giá trị nhỏ hơn k của mảng . V. CỦNG CỐ:  Nhắc lại một số khái niệm mới .  Nhắc lại cấu trúc câu lệnh bằng cách chia bảng thành 4 phần đồng thời gọi 4 học sinh lên bảng viết lại các cách khai báo, truy xuất, và hiển thị để nhập dữ liệu .  Ra bài tập về nhà .