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 Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

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

 
Bài 5:Học sinh lập trình Scratch - Làm quen với biến

Bài 5:Học sinh lập trình Scratch - Làm quen với biến

Bạn đã làm được hai trò chơi: “Mèo nhí diễu hành” và “Dơi bắt chuột, chuột ăn chuối”. Bạn nên hướng dẫn cho bé tự làm từ đầu thật thạo hai trò chơi đó trước khi chuyển qua bước tiếp theo

Hướng dẫn học ngôn ngữ Swift của Apple trong 24h thôi

Hướng dẫn học ngôn ngữ Swift của Apple trong 24h thôi

Khi Apple công bố ngôn ngữ lập trình hoàn toàn mới có tên là Swift của họ, cộng đồng lập trình đều rất vui mừng. 

iPad 3 chính là iPad 2S?

iPad 3 chính là iPad 2S?

Hãng sản xuất phụ kiện Trung Quốc Chinee vừa đăng tải hình ảnh của chiếc vỏ bảo vệ (case) được thiết kế cho thiết bị có tên iPad 2S

BLOG POSTS

 

Wordpress Freelancer

 

Wordpress Freelancer