Tin học 11 Bài 11: Kiểu mảng

  1. Tác giả: LTTK CTV
    Đánh giá: ✪ ✪ ✪ ✪ ✪

    Tóm tắt lý thuyết
    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ùng 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;
      • Cách tham chiếu đến phần tử.
    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 n1..n2 với n1, 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 \(\leq\) n2);
    • Kiểu phần tử là kiểu của phần tử mảng.
    Ví dụ 1. 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 = [-100..0] of integer;​

    Trong đó, n là hằng nguyên.

    b. Tham chiếu tới phần tử của mảng một chiều
    • 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à ].
    • Cú pháp: tên_mảng[chỉ số]
    Ví dụ 2: 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].

    [​IMG]

    Hình 1. Minh họa mảng một chiều

    2. Kiể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 ta 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.
    • Để người lập trình có thể xây dựng và sử dụng kiểu mảng hai 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 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ử.
    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 như sau:
    var < tên biến mảng > : 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 biến mảng qua kiểu mảng hai chiều:
    type < tên kiểu mảng > = array[ kiểu chỉ số dòng, kiểu chỉ số cột ] of < kiểu phần tử >;​

    var < tên biến mảng >: < tên kiểu mảng >;​

    Ví dụ 4. 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;

    var

    ArrayInt: array[1..10,1..15] of integer;

    ArrayLong:array[0..3*(n+1),0..n] of longint;​

    Trong đó, n là hằng nguyên.

    b. Tham chiếu tới phần tử của mảng hai chiều
    • 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 cách nhau bởi dấu phẩy và viết trong cặp ngoặc [ và ].
    • Cú pháp: tên_mảng[chỉ số dòng, chỉ số cột]
    Ví dụ 4. Tham chiếu tới phần tử ở dòng thứ 5, cột thứ 9 của biến mảng ArrayInt khai báo được viết: ArrayInt [5, 9].

    [​IMG]

    Hình 2. Minh hoạ mảng hai chiều

    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 để 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 minh họa
    Dạng 1. Một số bài tập vận dụng về mảng một chiều
    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.

    Bài tập 1. Tìm phần tử lớn nhất của dãy số nguyên
    • Xác định bài toán:
      • Input: Số nguyên dương N (N\(\leq\)250) và dãy N số nguyên dương a1, a2 ,..., aN, 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).
    • Mô tả thuật toán:
      • Bước 1. Nhập N và dãy a1,..., aN;
      • Bước 2. Max \(\leftarrow\) a1, i \(\leftarrow\) 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 \(\leftarrow\) ai;
        • Bước 4.2. i \(\leftarrow\) i + 1 rồi quay lại bước 3;
    • Chương trình cài đặt:
    PHP:
    1. program TimMax;
    2. uses crt;
    3. const
    4.    Nmax = 250;
    5. type
    6.    ArrInt = array[1..Nmax] of integer;
    7. var
    8.    N,i, Max, csmax: integer;
    9.    A: ArrInt;
    10. begin
    11.    clrscr;
    12.    write('Nhap so luong phan tu cua day so, N = ');
    13.    readln(N);
    14.    for i:=1 to N do
    15.          begin
    16.                write('Phan tu thu ',i,' = ');
    17.                readln(A[i]);
    18.          end;
    19.   Max:= A[1]; csmax:=1;
    20.      for i:=2 to N do
    21.                if A[i]> Max then
    22.          begin
    23.                            Max:= A[i];
    24.                      csmax:= i;
    25.          end;
    26. writeln('Gia tri cua phan tu Max: ', Max);
    27. writeln('Chi so cua phan tu Max: ', csmax);
    28. readln
    Bài tập 2. Sắp xếp dãy số nguyên bằng thuật toán tráo đổi
    • Xác định bài toán:
      • Input: Số nguyên dương N (N\(\leq\)250) và dãy A gồm N số nguyên dương a1, 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.
    • Chương trình cài đặt:
    PHP:
    1. program sapxep;
    2. uses CRT;
    3. const Nmax = 250;
    4. type
    5.     ArrInt = array[1..Nmax] of integer;
    6. var
    7.     N,i,j,t: integer;
    8.     A: ArrInt;
    9. begin
    10.     clrscr;
    11.     write('Nhap so luong phan tu cua day so, N = ');readln(N);
    12.     for i:=1 to N do
    13.           begin
    14.              write('Phan tu thu ',i,' = ');
    15.              readln(A[i]);
    16.           end;
    17.     for j:=N downto 2 do
    18.                begin
    19.                for i:=1 to j-1 do
    20.                if A[i]> A[i+1] then
    21.                      begin  (*Trao doi A[i] va A[i+1]*)
    22.                            t:= A[i];
    23.                            A[i]:= A[i+1];
    24.                            A[i+1]:= t
    25.                            end;
    26.                 end;
    27.    writeln('Day so duoc sap xep la: ');
    28.    for i:=1 to N do write(A[i]: 4);
    29.    readln
    Bài tập 3. Tìm kiếm nhị phân
    • Xác định bài toán:
      • Input: Dãy A là dãy tăng gồm N (N \(\leq\) 250) số nguyên dương a1, a2,..., aN và số nguyên k.
      • Output: Chỉ số i mà ai = 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.
    • Chương trình cài đặt:
    PHP:
    1. program TK_nhiphan;
    2. uses crt;
    3. const
    4.    Nmax = 250;
    5. type
    6.    ArrInt = array[1..Nmax] of integer;
    7. var
    8.    N, i, k: integer;
    9.    Dau, Cuoi, Giua: integer;
    10.    A: Arrint;
    11.    Tim_Thay: boolean;
    12. begin
    13.    clrscr;
    14.    write('Nhap so luong phan tu cua day so, N = ');
    15.    readln(N);
    16.    writeln('Nhap cac phan tu cua day so tang: ');
    17.    for i:=1 to N do
    18.          begin
    19.              write('Phan tu thu ',i,' = ');
    20.              readln(A[i]);
    21.          end;
    22.    write('Nhap gia tri k = ');
    23.    readln(k);
    24.    Dau:= 1; Cuoi:=N; Tim_thay:= false;
    25.    while (Dau <= Cuoi) and not (Tim_Thay) do
    26.          begin
    27.          Giua:= (Dau+Cuoi) div 2;
    28.          if A[Giua] = k then
    29.              Tim_thay:= true
    30.                      else
    31.                      if A[Giua]>k then Cuoi:= Giua-1
    32.                            else Dau:= Giua+1;
    33.                end;
    34.    if Tim_thay then writeln('Chi so tim duoc la: ', Giua)
    35.                else  writeln('Khong tim thay');
    36.    readln

    Dạng 2. Một số bài tập vận dụng về mảng hai chiều
    Bài tập 4. Chương trình sau tính và đưa ra màn hình bảng cửu chương.
    PHP:
    1. program BangCuuChuong;
    2. uses crt;
    3. var
    4.         B: array[1..9,1..10] of integer;
    5. {B: bien mang hai chieu luu bang cuu chuong}
    6.         i, j: integer;
    7. begin
    8.    clrscr;
    9.    for i:=1 to 9 do
    10.          for j:= 1 to 10 do
    11.                B[i,j]:= i*j;
    12.    for i:=1 to 9 do
    13.          begin
    14.                for j:=1 to 10 do write(B[i,j]:4);
    15.                writeln;
    16.          end;
    17.     readln
    Bài tập 5. 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 dòng, 7 cột với các phần tử là các số nguyên và 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.
    PHP:
    1. program MangHaiChieu;
    2. uses crt;
    3. var b: array[1..5, 1..7] of integer;
    4.      d, i, j, k: integer;
    5. begin
    6.    clrscr;
    7.    writeln('Nhap cac phan tu cua mang theo dong: ');
    8.    for i:= 1 to 5 do
    9.      begin
    10.        for j:= 1 to 7 do
    11.           begin
    12.                read(b[i,j]);
    13.                      write(' ');
    14.           end;
    15.        writeln;
    16.      end;
    17.    write('Nhap vao gia tri k = '); readln(k);
    18.    d:= 0;
    19.    writeln('DS cac phan tu mang nho hon ',k,':');
    20.    for i:= 1 to 5 do
    21.       for j:= 1 to 7 do
    22.          if b[i, j] < k then begin
    23.                                                          write(b[i, j], ' ');
    24.                                                          d:= d+1;
    25.                                      end;
    26.    if d = 0 then writeln(’Khong co phan tu nao nho hon ’,k);
    27. readln