Tìm dãy con lớn nhất các phần tử tăng dần của dãy số gồm n số

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.

Giải thuật:

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

LÝ THUYẾT:

- 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à chr 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.

Cài đặt

Program Day_con1;

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.

Nhận xét:

Bài toán trên có thể sử dụng giải thuật vét cạn dãy con để giải. Sau đây là cài đặt:

Program Day_con1b;

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.