CÁC BÀI TẬP VỀ MẢNG 1 CHIỀU VÀ 2 CHIỀU

BÀI TẬP 2

Tìm phần tử nhỏ nhất, lớn nhất của một mảng (cần chỉ ra cả vị trí của phần tử).

HƯỚNG DẪN

Giả sử phần tử min cần tìm là phần tử k. Ban đầu ta cho k=1. Sau đó cho i chạy từ 2 đến n, nếu a[k] > a[i] thì rõ ràng a[i] bé hơn, ta gán k bằng i. Sau khi duyệt toàn bộ dãy thì k sẽ là chỉ số của phần tử min. (Cách tìm min này đơn giản vì từ vị trí ta cũng suy ra được giá trị).

pro­ce­dure tim­min;

var i, k : in­te­ger;

be­gin

            k := 1;

            for i := 2 to n do

                        if a[k] > a[i] then k := i;

            writeln('Phan tu nho nhat la a[',k,']=',a[k]);

end;

Tìm max cũng tương tự, chỉ thay dấu so sánh.

pro­ce­dure tim­max;

var i, k : in­te­ger;

be­gin

            k := 1;

            for i := 2 to n do

                        if a[k] < a[i] then k := i;

            writeln('Phan tu lon nhat la a[',k,']=',a[k]);

end;

Chú ý:

1. Nếu áp dụng với mảng 2 chiều thì cũng tương tự, chỉ khác là để duyệt qua mọi phần tử của mảng 2 chiều thì ta phải dùng 2 vòng for. Và vị trí một phần tử cũng gồm cả dòng và cột.

Ví dụ 1. Tìm phần tử nhỏ nhất và lớn nhất của mảng 2 chiều và đổi chỗ chúng cho nhau:

pro­ce­dure ex­change;

var i,j,i1,j1,i2,j2,tg : in­te­ger;

be­gin

            i1 := 1; j1 := 1; {i1,j1 là vị trí phần tử min}

            i2 := 1; j2 := 1; {i2,j2 là vị trí phần tử max}

            for i := 1 to m do

                        for j := 1 to n do be­gin

                                    if a[i1,j1] > a[i,j] then be­gin {so sánh tìm min}

                                                i1 := i; j1 := j;     {ghi nhận vị trí min mới}

                                    end;

                                    if a[i2,j2] < a[i,j] then be­gin {so sánh tìm max}

                                                i2 := i; j2 := j; {ghi nhận vị trí max mới}

                                    end;

                        end;

            tg := a[i1,j1]; a[i1,j1] := a[i2,j2]; a[i2,j2] := tg; {đổi chỗ}

end;

2. Nếu cần tìm phần tử lớn nhất / nhỏ nhất hoặc sắp xếp 1 dòng (1 cột) của mảng 2 chiều thì ta cũng coi dòng (cột) đó như 1 mảng 1 chiều. Chẳng hạn tất cả các phần tử trên dòng k đều có dạng chỉ số là a[k,i] với i chạy từ 1 đến n (n là số cột).

Ví dụ 2. Tìm phần tử lớn nhất của dòng k và đổi chỗ nó về phần tử đầu dòng.

pro­ce­dure tim­max(k : in­te­ger);

var i, vt, tg : in­te­ger;

be­gin

            vt := 1; {vt là vị trí của phần tử min dòng k}

            for i := 1 to n do

                        if a[k,i] > a[k,vt] then vt := i; {các phần tử dòng k có dạng a[k,i]}

            tg := a[k,1]; a[k,1] := a[k,vt]; a[k,vt] := tg;

end;

Ví dụ 3. Sắp xếp giảm dần cột thứ k.

pro­ce­dure sapx­ep(k: in­te­ger);

var i,j,tg : in­te­ger;

be­gin

            for i := 1 to m-1 do {mỗi cột có m phần tử, vì bảng có m dòng}

                        for j := i+1 to m do

                                    if a[i,k] > a[j,k] then be­gin {các phần tử cột k có dạng a[i,k]}

                                                tg := a[i,k]; a[i,k] := a[j,k]; a[j,k] := tg;

                                    end;

end;