Thứ Sáu, 20 tháng 11, 2015

MỘT SỐ BÀI TẬP ĐƠN GIẢN VỀ MẢNG

DỮ LIỆU KIỂU MẢNG (ARRAY)


I. KHAI BÁO MẢNG
Cú pháp:
            TYPE <Kiểu mảng> = ARRAY [chỉ số] OF <Kiểu dữ liệu>;
            VAR   <Biến mảng>:<Kiểu mảng>;
hoặc khai báo trực tiếp:
            VAR               <Biến mảng> : ARRAY [chỉ số] OF <Kiểu dữ liệu>;
Ví dụ:
            TYPE  Mangnguyen = Array[1..100] of Integer;
                                                Matrix = Array[1..10,1..10] of Integer;
                                                MangKytu = Array[Byte] of Char;
            VAR               A: Mangnguyen;
                                                M: Matrix;
                                                C: MangKytu;
hoặc:
            VAR               A: Array[1..100] of Integer;
                                                C: Array[Byte] of Char;

II. XUẤT NHẬP TRÊN DỮ LIỆU KIỂU MẢNG
            - Để truy cập đến phần tử thứ k trong mảng một chiều A, ta sử dụng cú pháp: A[k].
            - Để truy cập đến phần tử (i,j) trong mảng hai chiều M, ta sử dụng cú pháp: M[i,j].
            - Có thể sử dụng các thủ tục READ(LN)/WRITE(LN) đối với các phần tử của biến kiểu mảng.

BÀI TẬP MẪU

Bài tập 5.1:    Viết chương trình tìm giá trị lớn nhất của một mảng chứa các số nguyên gồm N phần tử.
Ý tưởng:
            - Cho số lớn nhất là số đầu tiên: Max:=a[1].
            - Duyệt qua các phần tử a[i], với i chạy từ 2 tới N: Nếu a[i]>Max thì thay Max:=a[i];

Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var    A:Mang;
                   N,i,Max:Integer;
Begin
          {Nhập mảng}
          Write(‘Nhap N=’); Readln(N);
          For i:=1 To N Do
                   Begin
                             Write(‘A[‘,i,’]=’); Readln(A[i]);
                   End;
          {Tìm phần tử lớn nhất}
          Max:=A[1];
          For i:=2 To N Do
                   If Max<A[i] Then Max:=A[i];
          {In kết quả ra màn hình}
          Writeln(‘Phan tu lon nhat cua mang: ’, Max);
          Readln;
End.

Bài tập 5.2:    Viết chương trình tính tổng bình phương của các số âm trong một mảng gồm N phần tử.
Ý tưởng:
            Duyệt qua tất cả các phần tử A[i] trong mảng: Nếu A[i]<0 thì cộng dồn (A[i])2 vào biến S.

Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var    A:Mang;
                   N,i,S:Integer;
Begin
          {Nhập mảng}
          Write(‘Nhap N=’); Readln(N);
          For i:=1 To N Do
                   Begin
                             Write(‘A[‘,i,’]=’); Readln(A[i]);
                   End;
          {Tính tổng}
          S:=0;
          For i:=1 To N Do
                   If A[i]<0 Then S:=S+A[i]*A[i];
          {In kết quả ra màn hình}
          Writeln(‘S= ’, S);
          Readln;
End.

Bài tập 5.3: Viết chương trình nhập vào một mảng gồm N số nguyên. Sắp xếp lại mảng theo thứ tự tăng dần và in kết quả ra màn hình.
Ý tưởng:
            Cho biến i chạy từ 1 đến N-1, đồng thời cho biến j chạy từ i+1 đến N: Nếu A[i]>A[j] thì đổi chổ A[i], A[j].

Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var    A:Mang;
                   N,i,j,Tam:Integer;
Begin
          {Nhập mảng}
          Write(‘Nhap N=’); Readln(N);
          For i:=1 To N Do
                   Begin
                             Write(‘A[‘,i,’]=’); Readln(A[i]);
                   End;
          {Sắp xếp}
          For i:=1 To N-1 Do
                   For j:=i+1 To N Do
                             If A[i]>A[j] Then
                                      Begin
                                                Tam:=A[i]; A[i]:=A[j]; A[j]:=Tam;
                                      End;
          {In kết quả ra màn hình}
          Writeln(‘Ket qua sau khi sap xep:’);
          For i:=1 To N Do Write(A[i]:5);
          Readln;
End.

Bài tập 5.4: Viết chương trình nhập vào một mảng A gồm N số nguyên và nhập thêm vào một số nguyên X. Hãy kiểm tra xem phần tử X có trong mảng A hay không?
Ý tưởng:
            Dùng thuật toán tìm kiếm tuần tự. So sánh x với từng phần tử của mảng A. Thuật toán dừng lại khi x=A[i] hoặc i>N.
            Nếu x=A[i] thì vị trí cần tìm là i, ngược lại thì kết quả tìm là 0 (không tìm thấy).

Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var    A:Mang;
                   N,i,x:Integer;

Function TimKiem(x, N: Integer; A:Mang):Integer;
Var i:Integer;
          Begin
                   I:=1;
                   While (I <= N) and (X<>A[I]) do I:=I+1;
                   If I <= N Then Timkiem:=I  Else Timkiem:=0;
          End;

Begin
          {Nhập mảng}
          Write(‘Nhap N=’); Readln(N);
          For i:=1 To N Do
                   Begin
                             Write(‘A[‘,i,’]=’); Readln(A[i]);
                   End;
          Write(‘Nhap X=’); Readln(x);
          {Kết quả tìm kiếm}
          If TimKiem(X,N,A)<>0 Then     
                   Writeln(‘Vi tri cua X trong mang la:’, TimKiem(X,N,A))
          Else Writeln(‘X khong co trong mang.’);
          Readln;
End.

Bài tập 5.5: Giả sử mảng A đã được sắp xếp theo thứ tự tăng dần. Viết hàm để kiểm tra xem phần tử X có trong mảng A hay không?
Ý tưởng:
            So sánh x với phần tử ở giữa mảng A[giua]. Nếu x=A[giua] thì dừng (vị trí cần tìm là chỉ số của phần tử giữa của mảng). Ngược lại, nếu  x>A[giua] thì tìm ở đoạn sau của mảng [giua+1,cuoi], ngược lại thì tìm ở đoạn đầu của mảng [dau,giua-1].
Sau đây là hàm cài đặt cho thuật toán này:
Function TimKiemNhiPhan(X, N: Integer; A: Mang):Integer;
Var    dau,cuoi,giua:Integer;
                   Found:Boolean;
Begin
          dau:=1; {điểm mút trái của khoảng tìm kiếm}
          cuoi:=N; {điểm mút phải của khoảng tìm kiếm}
          Found:=False; {chưa tìm thấy}
          While (dau <=cuoi) and (Not Found) Do
                   Begin
                             giua:=(dau + cuoi) Div 2;
                             If  X = A[giua] Then Found:=True {đã tìm thấy}
                             Else
                                      If X > A[giua] Then dau:=giua+1
                                      Else cuoi:=giua-1;
                   End;
          If Found Then TimKiemNhiPhan:= giua Else TimKiemNhiPhan:=0;
End;

Bài tập 5.6: Viết chương trình tìm ma trận chuyển vị của ma trận A.
Ý tưởng:
            Dùng mảng 2 chiều để lưu trữ ma trận. Gọi B là ma trận chuyển vị của ma trận A, ta có: Bij = Aji.

Uses Crt;
Type Mang = ARRAY[1..10,1..10] Of Integer;
Var    A,B:Mang;
                   m,n,i,j:Integer;
Begin
          {Nhập ma trận}
          Write(‘Nhap số dòng m=’); Readln(m);
          Write(‘Nhap số cột n=’); Readln(n);
          For i:=1 To m Do
                   For j:=1 To n Do
                             Begin
                                      Write(‘A[‘,i,j,’]=’); Readln(A[i,j]);
                             End;
          {Tìm ma trận chuyển vị}
          For i:=1 To m Do
                   For j:=1 To n Do    B[i,j]:=A[j,i];
          {In ma trận chuyển vị ra màn hình}
          For i:=1 To m Do
                   Begin
                             For j:=1 To n Do    Write(B[i,j]:5);
                             Writeln;
                   End;
          Readln;
End.

Bài tập 5.7: Cho một mảng 2 chiều A cấp mxn gồm các số nguyên và một số nguyên x. Viết chương trình thực hiện các công việc sau:
            a/ Đếm số lần xuất hiện của x trong A và vị trí của chúng.
            b/ Tính tổng các phần tử lớn nhất của mỗi dòng.

Uses Crt;
Type Mang = ARRAY[1..10,1..10] Of Integer;
Var    A:Mang;
                   m,n,i,j,x,dem,S,max:Integer;
Begin
          {Nhập ma trận}
          Write(‘Nhap số dòng m=’); Readln(m);
          Write(‘Nhap số cột n=’); Readln(n);
          For i:=1 To m Do
                   For j:=1 To n Do
                             Begin
                                      Write(‘A[‘,i,j,’]=’); Readln(A[i,j]);
                             End;
          {Nhập x}
          Write(‘Nhap x=’); Readln(x);
          {Đếm số lãn xuất hiện của x và vị trí của x}
          dem:=0;
          Writeln(‘Vi tri cua x trong mang A: ‘);
          For i:=1 To m Do
                   For j:=1 To n Do   
                             If x=A[i,j] Then
                                      Begin
                                                Write(i,j,’ ; ‘);
                                                dem:=dem+1;
                                      End;
          Writeln(‘So lan xuat hien cua x trong mang A la: ‘,dem);
          {Tính tổng các phần tử lớn nhất của mỗi dòng}
          S:=0;
          For i:=1 To m Do {duyệt qua từng dòng}
                   Begin
                             {Tìm phần tử lớn nhất của dòng thứ i}
                             Max:=A[i,1];
                             For j:=2 To n Do    {duyệt từng phần tử của dòng thứ i}
                                      If max<A[i,j] Then max:=A[i,j];
                             {Cộng max vào biến S}
                             S:=S+max;
                   End;
          Writeln(‘Tong cac phan tu lon nhat cua moi dong la: ‘,S);
          Readln;
End.

Bài tập 5.8: Giải phương trình bằng phương pháp chia nhị phân.
Ý tưởng:
            Giả sử cần tìm nghiệm của phương trình f(x)=0 trên đoạn [a,b] với y=f(x) đồng biến và đơn trị trên đoạn [a,b]. Ta giải như sau:
            Gọi m là trung điểm của đoạn [a,b]. Nếu f(m)*f(a)<0 thì giới hạn đoạn tìm nghiệm thành [a,m]. Tương tự đối với đoạn [m,b]. Quá trình này lặp lại cho đến khi f(m)<e, lức này ta có 1 nghiệm gần đúng là m.
            Giả sử f(x) là một đa thức: f(x) = a0 + a1x + a2x2 + ... + anxn. Lúc này, ta có thể dùng mảng một chiều để lưu trữ các hệ số ai của đa thức.

Uses Crt;
Type HESO=Array[0..20] Of Real;
Var    a:HESO;
                   n:Byte;
                   Min,Max,epsilon:Real;

Procedure NhapDaThuc;
Var i:Byte;
Begin
  Write('Bac cua da thuc: n= '); Readln(n);
  Writeln('Nhap cac he so cua da thuc:');
  For i:=0 To n Do
   Begin
     Write('a[',i,']='); Readln(a[i]);
   End;
  Writeln('Nhap doan tim nghiem:[a,b]');
  Write('a= '); Readln(Min);
  Write('b= '); Readln(Max);
  Write('Nhap sai so cua phuong trinh: '); Readln(epsilon);
End;

{Tính giá trị của đa thức}
Function f(x:Real):Real;
Var    S,tam:Real;
                   i:Byte;
Begin
          S:=a[0]; tam:=1;
          For i:=1 To n Do
                   Begin
                             tam:=tam*x;
                             S:=S+a[i]*tam;
                   End;
          f:=S;
End;

Procedure TimNghiem(Min,Max:real);
Var m:Real;
Begin
  If f(Min)*f(Max)>0 Then Writeln('Phuong trinh vo nghiem.')
  Else If abs(f(Min))<epsilon Then Writeln('Nghiem la x=',min:0:2)
       Else If abs(f(Max))<epsilon Then Writeln('Nghiem la x=',max:0:2)
            Else
              Begin
                m:=(Min+Max)/2;
                If abs(f(m))<=epsilon Then Writeln('Nghiem la x=',m:0:2)
                Else If f(Min)*f(m)<0 Then TimNghiem(Min,m)
                        Else TimNghiem(m,Max);
              End;
End;

Begin
 NhapDaThuc;
 TimNghiem(Min,Max);
 Readln;
End.

 Bài tập 5.9: Viết chương trình nhập vào số tự nhiên N (N lẻ), sau đó điền các số từ 1 đến n2 vào trong một bảng vuông sao cho tổng các hàng ngang, hàng dọc và 2 đường chéo đều bằng nhau (bảng này được gọi là Ma phương).
            Ví dụ: Với N=3 và N=5 ta có





Bắc

2
7
6


3
16
9
22
15

9
5
1


20
8
21
14
2

4
3
8

Tây
7
25
13
1
19
Đông





24
12
5
18
6






11
4
17
10
23






Nam

Phuơng pháp:
            Xuất phát từ ô bên phải của ô nằm giữa. Đi theo hướng đông bắc để điền các số 1, 2, ...
            Khi điền số, cần chú ý một số nguyên tắc sau:
                        - Nếu vượt ra phía ngoài bên phải của bảng thì quay trở lại cột đầu tiên.
                        - Nếu vượt ra phía ngoài bên trên của bảng thì quay trở lại dòng cuối cùng.
                        - Nếu số đã điền k chia hết cho N thì số tiếp theo sẽ được viết trên cùng một hàng với k nhưng cách 1 ô về phía bên phải.

Uses Crt;
Var A:Array[1..20,1..20] Of Word;
      n,i,j,k:Word;
Begin
  Write('Nhap N= '); Readln(n);
  Clrscr;
 {Định vị ô xuất phát}
  i:=n DIV 2 + 1;
  j:=n DIV 2 + 2;

 {Điền các số k từ 1 đến n*n}
  For k:=1 To n*n Do
   Begin
     A[i,j]:=k;
     If k MOD n=0 Then j:=j+2
     Else Begin
                                      {Đi theo hướng đông bắc}
                              j:=j+1; i:=i-1;
            End;
     If j>n Then j:=j MOD n;
     If i=0 Then i:=n;
   End;

 {In kết quả ra màn hình}
  For i:=1 To n Do
   Begin
     For j:=1 To n Do write(a[i,j]:4);
     Writeln;
   End;
  Readln;
End.

Bài tập 5.10: Viết chương trình nhập vào 2 mảng số nguyên A, B đại diện cho 2 tập hợp (không thể có 2 phần tử trùng nhau trong một tập hợp). Trong quá trình nhập, phải kiểm tra: nếu phần tử vừa nhập vào đã có trong mảng thì không bổ sung vào mảng. In ra màn hình các phần tử là giao của 2 tập hợp A, B.
Ý tưởng:
            Duyệt qua tất cả các phần tử aiÎA. Nếu aiÎB thì viết ai ra màn hình.

Uses Crt;
Type Mang=ARRAY[1..50] Of Integer;

Var A,B:Mang;
    n,m:Byte;

Function KiemTra(x:Integer; n:Byte; A:Mang):Boolean;
Var i:Byte; Found:Boolean;
Begin
  Found:=False;
  i:=1;
  While (i<=n) AND (not Found) Do
    If x=A[i] Then Found:=True Else i:=i+1;
  KiemTra:=Found;
End;

Procedure NhapMang(Var n:Byte; Var A:Mang);
Var ch:Char;
    x:Integer;
Begin
  n:=0;
  Repeat
    Write('x='); Readln(x);
    If not KiemTra(x,n,A) Then
     Begin
       n:=n+1; A[n]:=x;
     End;
    Writeln('An ESC de ket thuc nhap!');
    ch:=Readkey;
  Until ch=#27;
End;

Procedure GiaoAB(n:Byte; A:Mang;m:Byte; B:Mang);
Var i:Byte;
Begin
  For i:=1 To n Do
   If KiemTra(A[i],m,B) Then Write(A[i]:4);
End;

Begin
  Clrscr;
  Writeln('Nhap mang A: ');
  NhapMang(n,A);
  Writeln('Nhap mang B: ');
  NhapMang(m,B);
  Writeln('Giao cua 2 mang A&B la: ');
  GiaoAB(n,A,m,B);
  Readln;
End.

Bài tập 5.11: Cho một mảng số nguyên gồm n phần tử. Tìm dãy con gồm m phần tử  (m£n) sao cho dãy con này có tổng lớn nhất. (Dãy con là dãy các phần tử liên tiếp nhau trong mảng).

Uses Crt;
Type Mang=ARRAY[1..50] Of Integer;

Var A:Mang;
    n,m,i,j,k:Byte;
    S,Max:Integer;
Begin
  Write('So phan tu cua mang: n= '); Readln(n);
  For i:=1 To n Do
   Begin
     Write('a[',i,']='); Readln(a[i]);
   End;
  Write('Nhap so phan tu cua day con: m= '); Readln(m);

  k:=1; {Vị trí phần tử đầu tiên của dãy con}

 {Giả sử m phần tử đầu tiên của mảng A là dãy con có tổng lớn nhất}
  Max:=0;
  For i:=1 To m Do Max:=Max+A[i];

 {Tìm các dãy con khác}
  For i:=2 To n-m+1 Do
   Begin
    {Tính tổng của dãy con thứ i}
     S:=0;
     For j:=i To i+m-1 Do S:=S+A[j];
     If S>Max Then {Nếu dãy con tìm được có tổng lớn hơn dãy con trước}
       Begin
         Max:=S; {Thay tổng mới}
         k:=i;       {Thay vị trí đầu tiên của dãy con mới}
       End;
   End;

  Writeln('Day con co tong lon nhat la:');
  For i:=k To k+m-1 Do Write(A[i]:5);
  Readln;
End.

Bài tập 5.12: Viết chương trình in ra màn hình tam giác Pascal. Ví dụ, với n=4 sẽ in ra hình sau:
1
1          1
1          2          1
1          3          3          1
1          4          6          4          1
Ý tưởng:
Tam giác Pascal được tạo ra theo qui luật sau:
            + Mỗi dòng đều bắt đầu và kết thúc bởi số 1.
            + Phần tử thứ j ở dòng k nhận được bằng cách cộng 2 phần tử thứ j-1 và j ở dòng thứ k-1.

Uses Crt;
Var Dong:Array[0..20] Of Byte;
    n,i,j:Byte;
Begin
  Write('n= '); Readln(n);
  Clrscr;
  Dong[0]:=1;
  Writeln(Dong[0]:4);

  {Khoi tao gia tri cua dong}
  For i:=1 To n Do Dong[i]:=0;

  {Voi moi dong i}
  For i:=1 To n Do
   Begin
     For j:=i DownTo 1 Do
      Begin
        Dong[j]:=Dong[j-1]+Dong[j];
        Write(Dong[j]:4);
      End;
     Writeln(Dong[i]:4);
   End;
  Readln;
End.

BÀI TẬP TỰ GIẢI

Bài tập 5.13: Viết chương trình nhập vào một dãy số thực và số thực x. Thông báo lên màn hình số lượng các phần tử trong dãy bằng x và vị trí của chúng.

Bài tập 5.14: Nhập vào một mảng các số nguyên.
            a/ Xếp lại mảng đó theo thứ tự giảm dần.
            b/ Nhập vào một số nguyên từ bàn phím. Chèn số đó vào mảng sao cho mảng vẫn có thứ tự giảm dần. (không được xếp lại mảng)
Gợi ý:
            - Tìm vị trí cần chèn: i.
            - Đẩy các phần tử từ vị trí i tới n sang phải 1 vị trí.
            - Gán: A[i]=x;

Bài tập 5.15: Cho 2 mảng số nguyên: Mảng A có m phần tử, mảng B có n phần tử.
            a/ Sắp xếp lại các mảng đó theo thứ tự giảm dần.
            b/ Trộn 2 mảng đó lại thành mảng C sao cho mảng C vẫn có thứ tự giảm dần (Không được xếp lại mảng C).
Gợi ý:
            - Dùng 2 chỉ số i,j để duyệt qua các phần tử của 2 mảng A, B và k là chỉ số cho mảng C.
            - Trong khi (i<=m) và (j<=n) thì:
              {Tức là khi đồng thời cả 2 dãy A, B đều chưa duyệt hết}
                        + Nếu A[i]>B[j] thì: C[k]:=A[i]; i:=i+1;
                        + Ngược lại: C[k]:=B[j]; j:=j+1;
            - Nếu dãy nào hết trước thì đem phần còn lại của dãy kia bổ sung vào cuối dãy C.

Bài tập 5.16: Viết chương trình tính tổng và tích 2 ma trận vuông A, B cấp n.
Gợi ý:
            Công thức tính tổng 2 ma trận: Cij = Aij + Bij
            Công thức tính tích 2 ma trận: Cij =
Bài tập 5.17: Viết chương trình nhập vào 2 dãy số nguyên (a)n và (b)m, m£n. Kiểm tra xem dãy {b} có phải là dãy con của dãy {a} không?

Bài tập 5.18: Viết chương trình nhập vào một dãy số nguyên a1, a2, ..., an. Tìm trong dãy {a} một dãy con tăng dần dài nhất (có số phần tử lớn nhất) và in ra màn hình dãy con đó.

Bài tập 5.19: Cho mảng 2 chiều A cấp mxn. Viết chương trình sắp xếp lại mảng A theo yêu cầu sau:
            a/ Các phần tử trên mỗi dòng được sắp xếp theo thứ tự giảm dần.
            b/ Các dòng được sắp xếp lại theo thứ tự tăng dần của tổng các phần tử trên mỗi dòng.

Bài tập 5.20: Viết chương trình để kiểm tra một dãy các số nguyên được nhập vào từ bàn phím đã được sắp theo thứ tự tăng dần hay chưa theo 2 cách: Đệ qui và không đệ qui.
Gợi ý:
            - Nếu dãy có 1 phần tử thì dãy tăng dần.
            - Ngược lại:
                        + Nếu A[n-1]>A[n] thì dãy không tăng dần.
                        + Ngược lại: Gọi đệ qui với dãy có n-1 phần tử (bỏ bớt đi phần tử cuối cùng).

Bài tập 5.21: Viết chương trình nhập vào 2 mảng số nguyên A, B đại diện cho 2 tập hợp (không thể có 2 phần tử trùng nhau trong một tập hợp). Trong quá trình nhập, phải kiểm tra: nếu phần tử vừa nhập vào đã có trong mảng thì không bổ sung vào mảng.
            a/ In ra màn hình hợp của 2 tập hợp A, B.
            b/ In ra màn hình hiệu của 2 tập hợp A, B.
Gợi ý:
            a/         - In ra màn hình tất cả các phần tử của  tập hợp A.
                        - Duyệt qua tất cả các phần tử b­i­ÎB. Nếu biÏA thì in bi ra màn hình.
            b/ Duyệt qua tất cả các phần tử a­i­ÎA. Nếu aiÏB thì in ai ra màn hình.

Bài tập 5.22: Viết chương trình tính tổng của 2 đa thức h(x) = f(x) + g(x). Trong đó, mỗi đa thức có dạng: a0 + a1x + a2x2 + ... + anxn.
Gợi ý:
            Dùng các mảng A, B, C để lưu trữ các hệ số ai của các đa thức f(x), g(x) và h(x).

Bài tập 5.23: Viết chương trình để tìm các phương án đặt 8 quân hậu trên bàn cờ vua (ma trận 8x8) sao cho các quân hậu không ăn được nhau.
Gợi ý:
            Dùng giải thuật quay lui.

Bài tập 5.24: Viết chương trình tính định thức của ma trận vuông cấp n.
Gợi ý:
            Dùng cách tính định thức theo phương pháp GAUSE.

Người đăng: vào lúc

Không có nhận xét nào:

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)