Thuật toán về dãy con trong Pascal

41
Lập trình Pascal

– Dãy con là dãy các phần tử liên tục thuộc một dãy có trước (dãy mẹ) thỏa mãn một tính chất nào đó.

– Để quản lí một dãy con cần  một chỉ số (nơi bắt đầu dãy con) và độ dài của dãy.

– Một cách quản lí khác là chỉ số đầu và chỉ số cuối.

– Để xây dựng một dãy con cần:

   – Xây dựng giá trị ban đầu.

   – Duyệt qua các phần tử của dãy, Nếu:

   – Thỏa điều kiện, tăng độ dài thêm 1 ngược lại:

          – Nếu dãy con đang xét cần lưu thì: Lưu lại độ dài, chỉ số đầu dãy, Xác định lại độ dài, chỉ số đầu của dãy mới.

          – Nếu dãy con đang xét không cần lưu thì: Xác định lại độ dài, chỉ số đầu của dãy mới.

– Để duyệt qua tất cả các dãy con của một dãy gồm n số ta dùng thuật toán vét cạn sau:

For i:= 1 to n
      For j:= 1 to n-i+1 // Xét dãy con bắt đầu từ vị trí thứ i có độ dài j.

Ví dụ 1: Cho dãy số gồm n số. Tìm dãy con lớn nhất các phần tử tăng (giảm) dần.

Sử dụng kỹ thuật xây dựng dãy con:

Program dayCon;
Var M: array[1..100] of integer;
    i,n, dau,ldau, dai,Max: integer;
Begin
     Write('Nhap so n: '); Readln(n);
     For i:=1 to n do 
       Begin Write('[',i,']='); Readln(M[i]); End;
     {Khoi tao gia tri dau}
     i:=0;
     Max:=1;
     dau:=1;
     dai:=1;
     ldau:=1;
     While i<=n do
     Begin
     i:=i+1;
     if M[i+1]>=M[i] then dai:=dai+1 else
     if dai> Max then Begin Max:=dai; ldau:=dau; dai:=0 End
     else Begin dau:=i+1; dai:=1 End;
     End;
     Write('Xau con dai:',max,' bat dau tu: ',ldau);
     Readln
End.

Giải thuật vét cạn:

Program dayCon;
Type KM= array[1..100] of integer;
     Var M:KM;
    i,j,n, dau,ldau, dai,Max: integer;
Function KT(A:KM;m,l:byte):boolean;
Var ok:Boolean;
    i:byte;
Begin
    ok:=True;
    For i:=m to m+l-1 do if A[i]>A[i+1] then ok:=ok and false;
    KT:=ok;
End;
Begin
     Write('Nhap so nc: '); Readln(n); Max:=0;
     For i:=1 to n do Begin Write('[',i,']='); Readln(M[i]); End;
     For i:= 1 to n-1 do
      For  j:=1 to n-i+1 do
           if KT(M,i,j) then
           if j+1> Max then Begin ldau:=i; Max:=j+1 End;
     Write('Xau con dai:',max,' bat dau tu: ',ldau);
     Readln
End.

Ví dụ 2: Cho dãy số gồm n số. Tìm dãy con lớn nhất các phần tử có cùng dấu, (đan dấu).

Program dayCon;
Var M: array[1..100] of integer;
    i,n, dau,ldau, dai,Max: integer;
Begin
     Write('Nhap so nc: '); Readln(n);
     For i:=1 to n do Begin Write('[',i,']='); Readln(M[i]); End;
     i:=0;
     Max:=1;
     dau:=1;
     dai:=1;
     ldau:=1;
     While i<=n do
     Begin
     i:=i+1;
     if M[i+1]*M[i]>0 then dai:=dai+1 else
     if dai> Max then Begin Max:=dai; ldau:=dau; dai:=0 End
     else Begin dau:=i+1; dai:=1 End;
     End;
     Write('Xau con dai:',max,' bat dau tu: ',ldau);
     Readln
End.

Ví dụ 3: Cho dãy số gồm n số nguyên. Tìm dãy con có tổng lớn nhất

Giải thuật:

– Sử dụng kỹ thuật vét cạn các dãy con, dùng hàm tính tổng dãy con để kiểm tra.

Program tongDayCon;
Type KM= array[1..100] of integer;
     Var M:KM;
    i,j,n,ldau, dai,Max: integer;
Function TONG(A:KM;m,l:byte):Integer;
Var Tam,i:integer;
Begin
    Tam:=0;
    For i:=m to m+l do Tam:=Tam + A[i];
    TONG:=Tam;
End;
Begin
     Write('Nhap so nc: '); Readln(n);
     For i:=1 to n do Begin Write('[',i,']='); Readln(M[i]); End;
     Max:=M[1];dai:=1;ldau:=1;
     For i:= 1 to n do
      For  j:=0 to n-i+1 do
           if TONG(M,i,j)> Max then
           Begin ldau:=i; Max:=Tong(M,i,j) ; dai:=j+1 End;
     Write('Xau con co tong:',max,' bat dau tu: ',ldau, ' dai: ',dai);
     Readln
End.