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: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Giá bán của ZTE Grand S bị rò rỉ trước thềm triển lãm CES 2013

Giá bán của ZTE Grand S bị rò rỉ trước thềm triển lãm CES 2013

Bên cạnh Nubia Z5, ZTE dự kiến sẽ công bố thêm thành viên Grand S có màn hình 5 inch với độ phân giải 1080p tại triển lãm CES 2013 diễn ra vào đầu năm sau.

Nguyễn Bành Đức trúng tuyển 15 đại học ở Mỹ

Nguyễn Bành Đức, 18 tuổi 7.5 IELTS, SAT là 1.460/1.600 trúng tuyển 15 đại học ở Mỹ

Nguyễn Bành Đức, 18 tuổi, được 15 đại học ở Mỹ cấp học bổng trị giá từ 650 triệu đồng đến gần 5 tỷ đồng cho khóa trọn gói 4 năm.

Kiếm tiền từ cộng đồng mạng - nhiều tiềm năng

Kiếm tiền từ cộng đồng mạng - nhiều tiềm năng

Theo nghiên cứu của Yahoo - Kantar Media, 55% số người dùng Internet truy cập vào các mạng xã hội năm 2011, so với 41% năm 2010. Đầu tư vào các website có cộng đồng đã trở nên hấp dẫn!