Bài 11: Kiểu mảng | Tin học | Chương 4: Kiểu dữ liệu có cấu trúc - Lớp 11 - Giáo Dục Việt Nam

Chúng ta chỉ xét hai kiểu mảng thông dụng với nhiều ngôn ngữ lập trình là kiểu mảng một chiều và kiểu mảng hai chiều.

1. Kiểu mảng một chiều

Mảng một chiều là dãy hữu hạn các phần tử cùn kiểu. Mảng được đặt tên và mỗi phần tử của nó có một chỉ số. Để mô tả mảng một chiều cần xác định kiểu của các phần tử và cách đánh số các phần tử của nó.

Để người lập trình có thể xây dựng và sử dụng kiểu mảng một chiều, các ngôn ngữ lập trình có quy tắc, cách thức cho phép xác định:

• Tên kiểu mảng một chiều;
• Số lượng phần tử;
• Kiểu dữ liệu của phần tử;
• Cách khai báo biến mảng;
• Cách tham chiếu đến phần tử.

Ví dụ, xét bài toán nhập vào nhiệt độ (trung bình) của mỗi ngày trong tuần, tính và đưa ra màn hình nhiệt độ trung bình của tuần và số lượng ngày trong tuần có nhiệt độ cao hơn nhiệt độ trung bình của tuần.

Ta có thể dùng bảy biến thực để lưu trữ nhiệt độ của các ngày trong tuần. Chương trình giải bài toán có thể được viết bằng Pascal như sau:

program Nhietdo_Tuan;
var t1, t2, t3, t4, t5, t6, t7, tb: real;
dem: integer;
begin
writeln('Nhap vao nhiet do cua 7 ngay: ');
readln (t1, t2, t3, t4, t5, t6, t7);
tb: (t1+t2+t3+t4+t5+t6+t7)/7;
dem:= 0;
if tl>tb then dem:= dem+1;
if t2>tb then dem:= dem+1;
if t3>tb then dem:= dem+1;
if t4>tb then dem: dem+1;
if t5>tb then dem:= dem+1;
if t6>tb then dem:= dem+1;
if t7>tb then dem:= dem+1;
writeln('Nhiet do trung binh tuan: ', tb: 4:2);
writeln('So ngay nhiet do cao hon trung binh: ',dem);
readln
end.

Khi cần giải bài toán trên với N ngày (N khá lớn) thì cách làm tương tự không những đòi hỏi một khối lượng khai báo khá lớn, mà đoạn chương trình tính toán cũng khá dài.

Để giải quyết vấn đề đó, ta sử dụng kiểu dữ liệu mảng một chiều để mô tả dữ liệu. Chương trình giải bài toán tổng quát với N ngày trong Pascal có thể như sau:

program Nhietdo_Nngay;
const Max = 366;
{gia thiet N lon nhat la 366}
type Kmangl= array [1.. Max] of real;
var Nhietdo: Kmangl;
dem, i, N: integer;
Tong, Trung binh: real;
begin
write('Nhap so ngay: '); readln(N); Tong:= 0;
for i: 1 to N do
begin
write('Nhap nhiet do ngay ',i, ': ');
readln (Nhietdo [i]);
Tong: Tong + Nhietdo [i];
end;
dem:= 0;
Trung_binh:= Tong/N;
for i: 1 to N do
if Nhietdo[i]>Trung binh then dem:= dem+1;
writeln('Nhiet do trung binh',N,' ngay: ',Trung binh:8:3);
writeln('So ngay nhiet do cao hon trung binh: ',dem); readln
end.

Trong chương trình này đã khai báo biến mảng một chiều (thông qua khai báo kiểu mảng) như sau:

Type Kmang1 = array [1.. Max] of real;

Var Nhietdo: Kmang1;

a) Khai báo

Tổng quát, khai báo biến mảng một chiều có dạng:

• Cách 1. Khai báo trực tiếp biến mảng một chiều:
  var <tên biến mảng >:array (kiểu chỉ số] of <kiểu phần tử;
• Cách 2. Khai báo gián tiếp biến mảng qua kiểu mảng một chiều:
  type <tên kiểu mảng>= array [kiểu chỉ số] of <kiểu phần tử; var <tên biến mảng >: <tên kiểu mảng;

trong đó:

• Kiểu chỉ số thường là một đoạn số nguyên liên tục có dạng nl.m2 với nl, n2 là các hằng hoặc biểu thức nguyên xác định chỉ số đầu và chỉ số cuối (n1 <n2);
• Kiểu phần tử là kiểu của các phần tử mảng.

Ví dụ. Các khai báo kiểu mảng một chiều sau đây là hợp lệ:

type
ArrayReal = array [-100..200] of real;
ArrayBoolean = array [-n+1..n+1] of boolean; ArrayInt = array [-100..0] of integer;

trong đó n là hằng nguyên.

Tham chiếu tới phần tử của mảng một chiều được xác định bởi tên mảng cùng với chỉ số, được viết trong cặp ngoặc [ và ].

Ví dụ, tham chiếu tới nhiệt độ của ngày thứ 20, trong chương trình trên, được
viết là Nhietdo[20].

b) Một số ví dụ

Ta xét chương trình có sử dụng mảng một chiều cài đặt một số thuật toán giải những bài toán tìm kiếm và sắp xếp.

Ví dụ 1. Tìm phần tử lớn nhất của dãy số nguyên
Input: Số nguyên dương N (N ≤ 250) và dãy N số nguyên dương A, A2,..., Ay, mỗi số đều không vượt quá 500.
Output: Chỉ số và giá trị của phần tử lớn nhất trong dãy số đã cho (nếu có nhiều phần tử lớn nhất chỉ cần đưa ra một trong số chúng).

Chương trình dưới đây thực hiện việc duyệt tuần tự các phần tử để tìm ra số lớn nhất của dãy số nguyên.

program TimMax;
uses crt;
const
Nmax = 250;
type
ArrInt = array [1.. Nmax] of integer;
var
N, i, Max, csmax: integer;
A: ArrInt;
begin
clrscr;
write('Nhap so luong phan tu cua day so, N = ');
readln (N);
for i: 1 to N do
begin
write ('Phan tu thu ', i,' = ');
readln(A[i]);
end;
Max: A[1]; csmax: 1;
for i: 2 to N do
if A[i]> Max then
begin
Max: A[i];
csmax:= i;
end;
writeln('Gia tri cua phan tu Max: ', Max);
writeln('Chi so cua phan tu Max: ', csmax);
readln
end.

Ví dụ 2. Sắp xếp dãy số nguyên bằng thuật toán tráo đổi
Input: Số nguyên dương N (N ≤ 250) và dãy A gồm N số nguyên dương A, A2,..., An, mỗi số đều không vượt quá 500.
Output: Dãy số A đã được sắp xếp thành dãy không giảm.

Để giải bài toán này, ta sẽ sử dụng thuật toán tráo đổi như mô tả trong sách giáo khoa Tin học 10.

(* Chuong trinh giai bai toan sap xep day so *)
program sapxep;
uses crt;
const Nmax = 250;
type
ArrInt = array [1.. Nmax] of integer;
var
N, i, j,t: integer;
A: ArrInt;
begin
clrscr;
write('Nhap so luong phan tu cua day so, N = ');
readln(N);
for i:=1 to N do (* Nhap cac phan tu *)
begin
write('Phan tu thu ', i, ' = ');
readln (A[i]);
end;
for j:=N downto 2 do
for i: 1 to j-1 do
if A[i]> A[i+1] then
begin (*Trao doi A[i] va A[i+1]*)
t:= A[i];
A[1] A[i+1];
A[i+1]:= t;
end;
writeln('Day so duoc sap xep la: ');
for i: 1 to N do write (A[i]: 4);
readln
end.

Ví dụ 3. Tìm kiếm nhị phân
Input: Dãy A là dãy tăng gồm N (N ≤ 250) số nguyên dương A, A,,.., An và số nguyên k.
Output: Chỉ số i mà A = k hoặc thông báo "Khong tim thay" nếu không có số hạng nào của dãy A có giá trị bằng k.
Để giải bài toán này, chúng ta sẽ sử dụng thuật toán tìm kiếm nhị phân được trình bày trong sách giáo khoa Tin học 10.

(* Chuong trinh cai dat thuat toan tim kiem nhi phan*) program TK_nhiphan;
uses crt;
const
Nmax 250;
type
ArrInt array [1.. Nmax] of integer;
var
N, i, k: integer;
Dau, Cuoi, Giua: integer;
A: ArrInt;
Tim Thay: boolean;
begin
clrscr;
write('Nhap so luong phan tu cua day so, N = ');
readln (N);
writeln('Nhap cac phan tu cua day so tang: ');
for i: 1 to N do
begin
write('Phan tu thu ', i, ' = ');
readln (A[i]);
end;
write('Nhap gia tri k = ');
readln(k);
Dau:= 1; Cuoi:=N; Tim thay:= false;
while (Dau <= Cuoi) and not (Tim Thay) do
begin
Giua:= (Dau+Cuoi) div 2;
if A[Giua] = k then
Tim_thay: true
else
if A[Giua]>k then Cuoi:= Giua-1
else Dau:= Giua+1;
end;
if Tim thay then writeln('Chi so tim duoc la: ', Giua)
else writeln('Khong tim thay');
readln
end.

2. Kiểu mảng hai chiều

Xét bài toán tính và đưa ra màn hình bảng nhân.

Ta thấy bảng nhân có dạng bảng gồm các giá trị cùng kiểu. Ta có thể biểu diễn bảng nhân bằng kiểu dữ liệu mảng hai chiều.

Mảng hai chiều là bảng các phần tử cùng kiểu.

Nhận xét rằng mỗi hàng của mảng hai chiều có cấu trúc như một mảng một chiều cùng kích thước. Nếu coi mỗi hàng của mảng hai chiều là một phần tử thì ta có thể nói mảng hai chiều là mảng một chiều mà mỗi phần tử là mảng một chiều.

Như vậy, ta cũng có thể mô tả dữ liệu của bảng nhân là kiểu mảng một chiều gồm 9 phần tử, mỗi phần tử lại là mảng một chiều có 10 phần tử, mỗi phần tử là một số nguyên.

Tương tự như với kiểu mảng một chiều, với kiểu mảng hai chiều, các ngôn ngữ lập trình cũng có các quy tắc, cách thức cho phép xác định:

• Tên kiểu mảng hai chiều;
• Số lượng phần tử của mỗi chiều;
• Kiểu dữ liệu của phần tử;
• Cách khai báo biến;
• Cách tham chiếu đến phần tử.

Ví dụ, biến mảng hai chiều B lưu trữ bảng nhân có thể được khai báo trong
Pascal như sau:
var B: array [1..9] of array [1..10] of integer;
hoặc có thể khai báo ngắn gọn:
var B: array [1..9, 1..10] of integer;

a) Khai báo

Tổng quát, khai báo biến mảng hai chiều trong Pascal như sau:

– Cách 1. Khai báo trực tiếp biến mảng hai chiều:

var <tên biến mảng:array[kiểu chỉ số hàng, kiểu chỉ số cột 1 of <kiểu phần tử;

– Cách 2. Khai báo gián tiếp biến mảng qua kiểu mảng hai chiều:

type <tên kiểu mảng>=array[kiểu chỉ số hàng, kiểu chỉ số cột]
var <tên biến mảng>: <tên kiểu mảng; of <kiểu phần tử;

Ví dụ. Các khai báo sau đây là hợp lệ:
type
ArrayReal array [-100..200,100..200] of real; ArrayBoolean = array [-n+1..n+1, n..2*n] of boolean;
ArrayInt: array [1..10, 1..15] of integer;
var
ArrayLong: array [0..3* (n+1), 0..n] of longint;

trong đó n là hằng nguyên.

Tham chiếu tới phần tử của mảng hai chiều được xác định bởi tên mảng cùng với hai chỉ số được phân cách bởi dấu phẩy và viết trong cặp ngoặc [ và ].\

Ví dụ. Tham chiếu tới phần tử ở hàng thứ 5, cột thứ 9 của biến mảng Arraylnt khai báo trong ví dụ trên được viết: ArrayInt [5, 9].

b) Một số ví dụ

Ví dụ 1. Chương trình sau tính và đưa ra màn hình bảng nhân.

program Bang_nhan;
uses crt;
var
B: array [1..9,1..10] of integer;
{B: bien mang hai chieu luu bang nhan}
i, j: integer;
begin
clrscr;
for i: 1 to 9 do
for j 1 to 10 do
B[i, j]: i*j;
for i: 1 to 9 do
begin
for j=1 to 10 do write (B[i, j]:4);
writeln;
end;
readln
end.

Ví dụ 2. Chương trình sau nhập vào từ bàn phím các phần tử của mảng hai chiều B gồm 5 hàng, 7 cột với các phần tử là các số nguyên và một số nguyên k. Sau đó, đưa ra màn hình các phần tử của mảng có giá trị nhỏ hơn k.

program MangHaiChieu;
uses crt;
var b: array [1..5, 1..7] of integer;
d, i, j, k: integer;
begin
clrscr;
writeln('Nhap cac phan tu cua mang theo dong: '); for i:= 1 to 5 do
begin
for j 1 to 7 do read (b[i, j]);
writeln;
end;
write ('Nhap vao gia tri k = '); 
readln (k);
d:= 0;
writeln('DS cac phan tu mang nho hon ', k, ':');
for i:= 1 to 5 do
for := 1 to 7 do
if b[i, j] <k then begin
end.
write (b[i, j], '');
d:= d+1;
end;
if d = 0 then writeln(’Khong co phan tu nao nho hon',k);
readln
end.

Chú ý:

• Các biến mảng thường gồm số lượng lớn các phần tử nên cần lưu ý phạm vi sử dụng chúng để khai báo kích thước và kiểu dữ liệu sao cho tiết kiệm bộ nhớ.
• Ngoài hai kiểu mảng một chiều và hai chiều, còn có kiểu mảng nhiều chiều.

Bài tập và thực hành 3

1. Mục đích, yêu cầu

Nâng cao kĩ năng sử dụng một số câu lệnh và một số kiểu dữ liệu thông qua việc tìm hiểu, chạy thử các chương trình có sẵn,

Biết giải một số bài toán tính toán, tìm kiếm đơn giản trên máy tính.

2. Nội dung

Bài 1. Tạo mảng A gồm n (n < 100) số nguyên, mỗi số có giá trị tuyệt đối không vượt quá 300. Tính tổng các phần tử của mảng là bội số của một số nguyên dương k cho trước.

a) Hãy tìm hiểu và chạy thử chương trình sau đây:

program Suml;
uses crt;
const
  nmax = 100;
type
  MyArray = array [1..nmax] of integer;
var
  A: MyArray;
  s, n, i, k: integer;
begin
  clrscr;
  randomize;
  write('Nhap n = ');
  readln(n);

  { Tạo ngẫu nhiên mảng gồm n số nguyên }
  for i := 1 to n do
    A[i] := random(301) - random(301);

  writeln('Mang vua tao:');
  for i := 1 to n do
    write(A[i]:5);
  writeln;

  write('Nhap k = ');
  readln(k);

  s := 0;
  for i := 1 to n do
    if A[i] mod k = 0 then
      s := s + A[i];

  writeln('Tong can tinh la: ', s);
  readln;
end.

Chú ý: Hàm chuẩn random(n) cho giá trị là số nguyên ngẫu nhiên trong đoạn từ 0 đến n − 1, còn thủ tục randomize khởi tạo cơ chế sinh số ngẫu nhiên.

b) Hãy đưa các câu lệnh sau đây vào những vị trí cần thiết nhằm sửa đổi chương trình trong câu a) để có được chương trình đưa ra số các số dương và số các số âm trong mảng.

posi, neg: integer;
posi:= 0; neg:= 0;
if A[i]>0 then posi:= posi+1
else if A[i] <0 then neg:= neg+1;
writeln (posi: 4, neg: 4);

Bài 2. Viết chương trình tìm phần tử có giá trị lớn nhất của mảng và đưa ra màn hình chỉ số và giá trị của phần tử tìm được. Nếu có nhiều phần tử có cùng giá trị lớn nhất thì đưa ra phần tử có chỉ số nhỏ nhất.

a) Hãy tìm hiểu chương trình sau đây:

program MaxElement;
const
  Nmax = 100;
type
  MyArray = array[1..Nmax] of integer;
var
  A: MyArray;
  n, i, j: integer;
begin
  write('Nhap so luong phan tu cua day so, N = ');
  readln(n);

 

  { Nhập các phần tử của mảng }
  for i := 1 to n do
  begin
    write('Phan tu thu ', i, ' = ');
    readln(A[i]);
  end;

  { Tìm chỉ số của phần tử lớn nhất }
  j := 1;
  for i := 2 to n do
    if A[i] > A[j] then
      j := i;

  { In ra chỉ số và giá trị của phần tử lớn nhất }
  writeln('Chi so: ', j, ' Gia tri: ', A[j]:4);
  readln;
end.

b) Chỉnh sửa chương trình trên để đưa ra chỉ số của các phần tử có cùng giá trị lớn nhất.

Bài tập và thực hành 4

1. Mục đích, yêu cầu

• Biết nhận xét, phân tích, đề xuất thuật toán giải bài toán sao 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.

2. Nội dung

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.

(* Chương trình giải bài toán sắp xếp dãy số *)
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);

  {Tạo ngẫu nhiên mảng gồm n số nguyên}
  for i := 1 to n do
    A[i] := random(300) - random(300);

  writeln('Mang vua tao:');
  for i := 1 to n do
    write(A[i]:5);
  writeln;

  {Sắp xếp dãy số theo thứ tự tăng dần}
  for j := n downto 2 do
    for i := 1 to j-1 do
      if A[i] > A[i+1] then
      begin
        (* Trao đổi A[i] và A[i+1] *)
        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.

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.

Bài 2
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.
Thoạt đầu có thể viết chương trình sau để giải bài toán này:

program SubSuml;
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);

  {Tạo ngẫu nhiên mảng gồm n số nguyên}
  for i := 1 to n do
    A[i] := random(300) - random(300);  {Sửa đoạn này để tạo số ngẫu nhiên trong khoảng -299 đến 299}

  for i := 1 to n do
    write(A[i]:5);
  writeln;

  {Bắt đầu tạo mảng B}
  for i := 1 to n do
  begin
    B[i] := 0;
    for j := 1 to i do
      B[i] := B[i] + A[j];
  end;
  {Kết thúc tạo mảng B}

  for i := 1 to n do
    write(B[i]:6);
  readln;
end.

Để ý rằng ta có các hệ thức sau:
B[1]= A[1]
B[i]= B[i-1]+A[i], l<i≤n.

Do đó, ta thay đoạn chương trình từ chú thích {Bat dau tao B} đến {Ket thuc tao B} bởi hai lệnh sau:
B[1]:= A[1];
for i: 2 to n do B[i]:= B[i-1]+A[i];

Với hai lệnh này, máy chỉ phải thực hiện n − 1 phép cộng, trong khi với đoạn chương trình trên máy phải thực hiện

phép cộng.

Nhờ việc phân tích như trên ta có thể giảm bớt đáng kể số phép toán cần thực hiện.

Tuy tốc độ tính toán của máy tính nhanh nhưng có giới hạn. 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.