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

 
Rò rỉ thông số kĩ thuật của máy ảnh Sony Cyber-shot RX100 MkII

Rò rỉ thông số kĩ thuật của máy ảnh Sony Cyber-shot RX100 MkII

Sau khi tung ra Cyber-shot RX100 cách đây không lâu, có vẻ như Sony muốn tiếp tục gây ấn tượng với người dùng với kế hoạch phát hành Cyber-shot RX100 MkII.

Advantages of Component-Based Web Design Systems

Ưu điểm của hệ thống Atomic Design thiết kế web Based Web Design

In the evolving world of web design and development, component-based design systems represent a revolutionary leap

Drupal features

Một số tính năng của Drupal

Drupal is a fully featured content management system that can be infinitely enhanced through the installation of contributed modules or by customised development.

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

 

Diet con trung