Diễn đàn tin học Văn Lang - Vạn Ninh
Chào mừng bạn đến với Diễn đàn Tin học Văn Lang - Vạn Ninh của chúng tôi !
Hãy đăng nhập hoặc đăng kí tài khoản để trải nghiệm nhiều điều thú vị tại đây !
Thân ái !

Diễn đàn tin học Văn Lang - Vạn Ninh

Nơi trao đổi thông tin, tăng cường hợp tác, giải đáp những vướng mắc khi học lập trình Pascal
 
Trang ChínhCalendarTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập

Share | 
 

 Dữ liệu kiểu mảng

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Admin
Admin
avatar

Posts : 113
Danh tiếng : 5
Join date : 10/11/2014
Age : 16

Bài gửiTiêu đề: Dữ liệu kiểu mảng   15/1/2015, 22:46

I / Định nghĩa :  
Mảng là tập hợp các phần tử cùng kiểu . Kiểu của các phần tử như mọi kiểu của biến (trừ kiểu File ) .

II/ Cách khai báo mảng 1 chiều : Có hai cách khai báo :
Cách 1 :
TYPE  Tên_Kiểu_Mảng  =   ARRAY[chỉ_số_đầu  .  . chỉ_số_cuối]  of  Kiểu_Phần_tử ;
VAR Tên_biến_Mảng   :    Tên_Kiểu_Mảng ;
Cách 2 :
VAR Tên_biến_Mảng   :    ARRAY[chỉ_số_đầu  .  . chỉ_số_cuối]  of  Kiểu_Phần_tử ;

Lưu ý :
Khi truyền dữ liệu kiểu mảng vào trong chương trình con bắt buộc phải dùng cách 1

III /  Cách khai báo mảng 2 chiều :     Tương tự cũng có 2 cách khai báo :
Cách 1 :
TYPE  Tên_Kiểu_Mảng  =   ARRAY[m1 .  . m2,n1 . . n2]  of  Kiểu_Phần_tử ;
VAR Tên_biến_Mảng   :    Tên_Kiểu_Mảng ;
Cách 2 :
VAR Tên_biến_Mảng   :    ARRAY[m1 .  . m2,n1 . . n2]  of  Kiểu_Phần_tử ;

Lưu ý : m1  là chỉ số dòng đầu và m2 chỉ số dòng cuối
n1  là chỉ số cột đầu và n2 chỉ số cột cuối

IV /  Cách truy nhập Mảng :
Kí hiệu mảng 1 chiều có N phần tử là  A(N). Kí hiệu phần tử thứ i ( 1 <= i  <= N ) của mảng là  A[i] . Trong chương trình , A[i] có vai trò như một biến mang giá trị của ô nhớ tương ứng với phần tử thứ i của mảng . Vậy muốn truy nhập (lấy ra hoặc đặt lại ) giá trị của  phần tử thứ i của mảng 1 chiều A(N) ta chỉ cần truy nhập qua A[i] . Rõ ràng rất thuận tiện .
Kí hiệu mảng 2 chiều có M dòng ,N cột  A(M,N) . Số phần tử là MxN Kí hiệu phần tử ở dòng i ( 1 <= i  <= M ) , cột j  ( 1 <= j  <= N ) của mảng là  A[i,j] . Chỉ số i gọi là chỉ số dòng , chỉ số j gọi là chỉ số cột . Chú ý chỉ số dòng viết trước.
Trong chương trình , A[i,j] có vai trò như một biến ,mang giá trị của ô nhớ tương ứng với phần tử ở dòngi , cột j  của mảng . Vậy muốn truy nhập (lấy ra hoặc đặt lại ) giá trị của  phần tử này chỉ cần truy nhập qua A[i,j] .

V / Chuyển đổi mảng 2 chiều vào mảng 1 chiều :

Để chuyển giá trị của các phần tử của mảng 2 chiều A(M,N ) vào mảng 1 chiều B(M*N) ta dùng công thức sau :

B[k] := A[i,j]   với  k := (i - 1) * N  + j    ( 1<=i<=M  ; 1<=j <= N )

VI / Kích thước của mảng :

+ Cách 1  : Mảng A có kích thước là  :  Sizeof(A)  Byte
+ Cách 2  : Kích thước Mảng = Kích thước 1 phần tử * Số lượng phần tử .

VII /  Vấn đề  mảng  và tự điển :

Trong một số bài tập , việc tổ chức  mảng như thế nào để có thể làm việc với bộ dữ liệu lớn là một yêu cầu cần thiết . Thí dụ : Cho một bảng chữ nhật 2x4 gồm 2 dòng , 4 cột chứa 8 ô vuông , mỗi ô chứa 1 số nguyên khác nhau 1 , 2 ,3 ,4 ,5 ,6 ,7 8 .

Hình 1
1 2 3 4
8 7 6 5


Hình 2
4 1 2 3
5 8 7 6

Hình 3
4 8 1 3
5 7 2 6

Rõ ràng có 8! = 40.320  bảng như vậy . Bài toán đặt ra là :
Nếu xếp các ô cạnh nhau theo chiều mũi tên như trên hình vẽ sẽ được 1 số nguyên kiểu LongInt :  12345678  ( Hình 1 ) hoặc 41236785 ( Hình 2 )  hoặc 48136275 ( Hình 3 ).Giá trị của số này gọi là giá trị của bảng .
Hãy sắp xếp 40.320 bảng này theo thứ tự tăng nghĩa là sắp xếp 40.320 số kiểu LongInt .Không thể dùng mảng  có kiểu  Array[1.. 40320] of  LongInt  để lưu trữ các bảng này .
Vậy hướng giải quyết như thế nào ? Ta sẽ xây dựng 1 “Tự điển “ sắp xếp tăng các số này (nhưng không cần lưu trữ)  .Mỗi số gọi là 1 từ trong tự điển .
Mỗi từ tạo thành như cách thức trên có những đặc trưng gì ? Nếu lần lượt tạo các chữ số  từ trái qua phải , chữ số ở vị trí thứ  i ( 0<= i <= 8 ) có k*(8-i)! số được tạo ra trước nó ; k là số các chữ số nhỏ hơn chữ số ở vị trí i mà chưa được dùng làm các chữ số trước i  . Vậy từ ở vị trí thứ  i  là 1 cặp số  ( i,k)  ,trong tự điển nó đứng ở vị trí thứ   :

                                                         8
VT =      ki * (8-i)!  +  1   ( 1<=i<=Cool
         i=1
Thí dụ  Bảng nêu ở hình 1 có VT = 1 vì ki =0 trong cả 8 số hạng .
Bảng nêu ở hình 2 có VT  = 3*7! + 3! + 2! + 1! + 1 = 5049 ...
Vậy chỉ cần các mảng sau  :  
+ Mảng M có 8 phần tử kiểu Word chứa 8 giá trị  (8-i)!  ( 1<= i <= 8 )
+ Mảng P để đánh dấu các chữ số nào đã được dùng đứng trước chữ số thứ i , suy ra  k là số các chữ số nhỏ hơn i , đã được dùng đứng trước chữ số thứ i
+ Mảng A có kiểu Array[1..8] of Byte để chứa 1 bảng .
Mỗi khi nhận được 1 bảng , ta có thể tìm được vị trí của nó trong tự điển , và ngược lại .

Uses   Crt;
Const   M       : Array[0..7] of Word =(1,1,2,6,24,120,720,5040);
Type   KX     = Array[1..8] of Byte;
Var     A       : KX;  i , j : Word;
Function Vitri(X  : KX)   : Word;
  Var  T   : LongInt;
       i,j : Byte;
       D   : KX;
      Begin
           T := 0;
           FillChar(D,Sizeof(D),0);
           For i:=1 to 8 do
                Begin
                     For j:= X[i]-1 downto 1 do
                            If D[j]=0 then T := T + M[8-i];
                     D[X[i]] := 1;
                End;
           Vitri := T + 1;
      End;
Procedure  Timso(T : Word;Var X : KX);
      Var i,j,k : Byte;       D     : KX;
      Begin
          FillChar(D,Sizeof(D),0);
          Dec(T);
          For i:=1 to 8 do
              Begin
                   K := T div M[8-i] + 1 ;   T := T mod M[8-i];
                   j := 0;
                   While (k>0) do
                         Begin
                              While D[j+1]=1 do Inc(j);
                              Inc(j);Dec(k);
                         End;
                    X[i] := j; D[j] := 1;
              End;
      End;
BEGIN
      Clrscr;
        For i:=1 to 8 do
            Begin
                  Write('A[',i,'] = ');
                  Readln(A[i]);
            End;
        j := vitri(A);
      Writeln(j);
Timso(j,A);
           For i:=1 to 8 do Write(A[i]);
       Readln
END.

VIII / Một số thao tác trên mảng :

1 ) Duyệt mảng :

      Mảng được duyệt nhờ sử dụng 1 biến điều khiển nhận giá trị từ chỉ số nhỏ nhất tới chỉ số lón nhất hoặc ngược lại . Một số loại bài tập duyệt mảng .
a )  Đếm số phần tử thoả mãn 1 tính chất nào đó ( thường dùng 1 biến đếm ) .
b )  Kiểm tra các phần tử của mảng xem đã được dùng vào một giai đoạn nào đó của bài toán chưa , phần tử nào đã được xem xét thì được đánh dấu bằng cách gán cho nó 1 giá trị đặc biệt .( Hoặc có thể dùng kèm theo 1 mảng phụ để đánh dấu ) .
c )  Thay đổi lại giá trị của 1 số phần tử có tính chất chung .
d )  Tìm một dãy con các phần tử liên tiếp nhau thoả mãn 1 tính chất nào đó  .
e )   Xoá bỏ một số phần tử ( Thường dùng kèm theo 1 mảng đánh dấu ) .
g )   Duyệt mảng đồng thời dồn mảng sau khi xoá bỏ 1 số phần tử , hoặc chèn thêm vào 1 số phần tử .
            h) Xử lý trên mảng vòng ( Hai phương pháp chính - Các bài tập 5,21,23.. sẽ đề cập  )
2 ) Sắp xếp tăng , giảm :

Thường dùng một số phương pháp chính sau đây :
+ BubbleSort
+ ShellSort
+ QuickSort
+  HeapSort
+  Đổi chỗ trực tiếp
a ) Bubble Sort    {  Phương pháp nổi bọt }
Uses   Crt;
Const  N = 10000;
Type   M1  = Array[1..N] of Integer;
Var    A   : M1;
      i,j,x : Integer;
Begin
      Clrscr;
      Randomize;
      For i:=1 to N do A[i] := Random(10);
      For i:=1 to N do Write(A[i]:4);
      For i:=2 to N do
          For j:=N downto i do
              If A[j-1] > A[j] then
                  Begin
                       x := A[j-1];
                       A[j-1] := A[j];
                       A[j]   := x;
                  End;
      Writeln;
      For i:=1 to N do Write(A[i]:4);
      Readln;
End.

b ) Shell Sort    {Chèn trực tiếp với độ dài giảm dần , có biến đóng vai trò lính canh }
Uses   Crt;
Const   N = 10000;
Type   M1   = Array[1..N] of Integer;
      M2   = Array[1..4] of Integer;
Var     A   : M1;
      H   : M2;
      i,j,m,k,s,x : Integer;
Begin
      Clrscr;
      Randomize;
      For i:=1 to N do A[i] := Random(10);
      For i:=1 to N do Write(A[i]:4);
      H[1] := 1;         H[2] := 3;           H[3] := 5;           H[4] := 9;
      For m := 1 to 4 do
          Begin
               K := H[m];
               S := -k;
               For i:=K+1 to N do
                   Begin
                        x := A[i];
                        j := i-k;
                        If s=0 then s := -k;
                        Inc(s);
                        A[s] := x;
                        While x<A[j] do
                             Begin
                                  A[j+k] := A[j];
                                  Dec(j,k);
                             End;
                        A[j+k] := x;
                   End;
          End;
      For i:=1 to N do Write(A[i]:4);
      Readln;
End.

c ) QuickSort
{$S-}
Uses  Crt;  {Sắp xếp bằng phân hoạch }
Const Max= 15000;  { Nếu dùng đệ qui , không sử dụng 2 mảng DP,CP , thì Max ->32000}
Type   Chiso = 1..Max;
      Mang   = Array[Chiso] of Integer;
Var   A     : Mang;
Procedure Taomang; { Tạo ngẫu nhiên Mảng A(N) }
Procedure QuickSort;
     Var   s,D,C,i,j : Word;
          coc,x       : Integer;
          dP,cP : Array[Chiso] of Chiso;
     Begin
          s:=1;
          dP[s]:=1;
          cP[s]:=Max;
          Repeat
                D:=dP[s]; { Chỉ số đầu của phân hoạch thứ  s }
                C:=cP[s]; { Chi số cuối của phân hoạch thứ  s }
                Dec(s);
                Repeat
                      i:=D;  
                      j:=C;
                      x:= A[(D+C) div 2];
                      Repeat
                             While A[i] < x do inc(i);
                             While x < A[j] do dec(j);
                             If i<=j then
                                Begin
                                     coc:=A[i];   A[i]:=A[j];   A[j]:=coc;
                                     Inc(i);  
                                     Dec(j);
                                End;
                      Until i>j;
                      If i<C then
                      Begin
                           Inc(s);
                           dP[s]:=i;
                           cP[s]:=C;
                      End;
                      C:=j;
                Until D>=C;
           Until s=0;
      End;
Procedure Hien(X : Mang);    { Hiện Mảng }
BEGIN
    Repeat
          Clrscr;
          Taomang;
          QuickSort;
          Hien(A);
          Write('ESC to Quit.Press any key to Continue...');
    Until ReadKey=#27;
END.
d) MergeSort   {  Đổi chỗ trực tiếp . Phương pháp này it dùng trên mảng vì tốn bộ nhớ}
e ) HeapSort     { Phương pháp vun đống + Đệ qui sẽ học sau  }


3 )Tạo mảng vòng :

Cách 1 :  Biến i ( biến điều khiển ) duyệt mảng  nhận các giá trị tăng dần ,đến  khi i = N+1 thì gán i= 1 . Hoặc ngược lại biến i ( biến điều khiển ) duyệt mảng  nhận các giá trị giảm dần ,đến  khi i = 0 thì gán i = N .
Cách 2 :  Nhân đôi mảng

                   i chạy từ 1 đến N để tạo các điểm
                   bắt đầu khác nhau của J


 A(N)  :       1   2  .......i  ........... .................N     1   2   3   ...........(i+N-1) ........................2xN

                                       J đi từ i tới i+N-1 là duyệt xong mảng A(N)
                           

4 ) Biến định vị :

Trong khi duyệt mảng , người ta thường hay dùng 2 loại biến : Biến điều khiển vòng lặp để duyệt mảng và biến định vị để đánh dấu mốc những vị trí cần thiết ,nhằm mục đích tạo ranh giới phần đã duyệt và phần còn phải duyệt tiếp. Mỗi lần biến điều khiển “dò dẫm” duyệt mảng ,thấy điều kiện nào đó theo yêu cầu của đề bài được đáp ứng trên một dãy con nào đó của mảng thì biến điều khiển gửi ngay “thông điệp” cho biến định vị tới “quản lý” 2 vị trí chốt đầu và cuối dãy con này . Biến định vị lập tức nhận nhiệm vụ “lính canh” này và phấp phỏng chờ đợi “thông điệp mới của biến định vị “ để nhận chốt mới .

Thí dụ    :       Bài toán tìm dãy con dài nhất gồm các phần tử liên tiếp lớn hơn x :
( Xem lời giải chi tiết ở trang 122 )
+ Chương trình sẽ dùng 1 biến i làm nhiệm vụ duyệt mảng , 4 biến định vị : đ,c,Lđ,Lc
Biến đ : chốt điểm đầu của dãy con mới xây dựng
Biến c : chốt điểm cuối của dãy con mới xây dựng
Biến Lđ : chốt điểm đầu của dãy con dài nhất trước dãy con mới xây dựng
Biến Lc : chốt điểm cuối của dãy con dài nhất trước dãy con mới xây dựng
+ Khởi trị : Đ := 1;C := 1; LĐ := 1; LC:=1;
+ Biến i duyệt mảng bắt đầu từ 1 ,
* Nếu A[i] > x thì C chốt tới giá trị i này, i tiếp tục hành trình “thăm dò “ của mình  , * Nếu A[i]<= x thì phải so sánh  C-Đ với LC-LĐ .
-Nếu C-Đ > LC-LĐ thì dãy con mới xây dựng dài hơn nên LC nhận giá trị mới là C , LĐ nhận giá trị mới là Đ . Đồng thời Đ và C lên giữ chốt mới là i, để bắt đầu xây dựng một dãy con khác
-Nếu C-Đ < = LC-LĐ thì chỉ xảy ra Đ và C lên giữ chốt mới là i, để bắt đầu xây dựng một dãy con khác
Về Đầu Trang Go down
Xem lý lịch thành viên http://forumpascalvanlang.forumvi.com
 
Dữ liệu kiểu mảng
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Văn Lang - Vạn Ninh :: Lí thuyết :: Mảng và xâu-
Chuyển đến