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ố

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.
Bạn thấy bài viết này như thế nào?: 
Average: 2.9 (58 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Nguy cơ rò rỉ thông tin từ thiết bị viễn thông nhập khẩu Trung Quốc là  Huawei và ZTE

Tập đoàn viễn thông Huawei và ZTE đe dọa an ninh nước Mỹ

Không phải đến bây giờ, khi Ủy ban Tình báo Hạ viện Mỹ vừa công bố hai tập đoàn viễn thông Trung Quốc là Huawei và ZTE đe dọa an ninh nước này, các khuyến cáo về sử dụng các thiết bị tương tự tại Việt Nam mới được đưa ra.

[KDS] Keeping Drupal Simple và Static Prototyping

[KDS] Keeping Drupal Simple và Static Prototyping

The technical debt involved with preprocessing views templates or creating custom panel layouts is hard to justify for projects that have small budgets, tight timelines, or hyper-specific design requirements.

Microsoft đã tung ra một số chiến dịch quảng cáo nhằm hạ đối thủ Google

Microsoft đã tung ra một số chiến dịch quảng cáo nhằm hạ đối thủ Google

Trong vài tháng qua, Microsoft đã tung ra một số chiến dịch quảng cáo “chọc ngoáy” đối thủ Google, nhằm lôi kéo người dùng từ các dịch vụ của “gã khổng lồ tìm kiếm.”

Công ty diệt chuột T&C

 

Diet con trung