Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Cho dãy gồm N số nguyên. Tìm đoạn không giảm có chiều dài lớn nhất.

MDOAN.INP
MDOAN.OUT

12
1 5 5 1 3
3 3 5 7 9
1 2

4 7


Dữ liệu vào: tệp văn bản MDOAN.INP
Dòng thứ nhất: số tự nhiên N,          1 £ N £ 20000.
Từ dòng thứ hai trở đi: các phần tử của dãy.
Dữ liệu ra: tệp văn bản MDOAN.OUT
Chứa một dòng duy nhất gồm hai số tự nhiên  d – chỉ số đầu đoạn và L – số phần tử trong đoạn (chiều dài đoạn).
Trong các tệp, dữ liệu trên cùng dòng cách nhau qua dấu cách.
Thí dụ trên cho ta đoạn không giảm dài nhất bao gồm 7 phần tử  bắt đầu từ phần tử thứ tư trong dãy (các phần tử được gạch dưới):
1 5 5 1 3 3 3 57 9 1 2

Thuật toán

Đây là bài dễ, ta đọc dần các phần tử từ input file và  so sánh hai phần tử liên tiếp nhau là x (phần tử đọc trước tại bước i) và y (phần tử đọc sau tại bước i+1). Nếu y < x thì coi như kết thúc một đọan không giảm, ta cập nhật để ghi nhận lại đoạn không giảm dài nhất. Các biến tổng thể trong chương trình được dùng như sau:
MaxLen – chiều dài của đoạn không giảm dài nhất hiện tìm được,
imax -  chỉ số đầu tiên của đoạn không giảm dài nhất hiện tìm được,
ileft – chỉ số đầu tiên của đoạn không giảm đang xét.
Độ phức tạp: cỡ N.
(*  Pascal  *)
(****************************************
      MDOAN - Doan tang dai nhat
****************************************)
program MDoan;
uses crt;
const
 bl = #32; fn = 'MDOAN.INP'; gn = 'MDOAN.OUT';
var f,g: text;
  n: integer;
  a: mw1;
  iLeft, imax: integer;
  MaxLen: integer;
procedure Update(i: integer);
begin
  if (MaxLen < i - iLeft) then
   begin
     MaxLen := i - iLeft;
     imax := iLeft; ileft := i;
   end;
  iLeft := i;
end;
procedure XuLi;
 var i, x, y: integer;
 begin
  assign(f,fn);  reset(f);  readln(f,n);
  read(f,x); 
   iLeft := 1;  MaxLen := 0;
   for i := 2 to n do
    begin
     read(f,y);
     if (y < x) then Update(i);
     x := y;
    end;
   Update(n+1);
  close(f);
 end;
procedure Ghi;
begin
  assign(g,gn); rewrite(g);
  writeln(g,imax,bl,MaxLen);
  close(g);
end;
BEGIN
  XuLi; ghi;
END.


Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts