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


Đoạn đơn điệu dài nhất




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

DONDIEU.INP
DONDIEU.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 DONDIEU.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 DONDIEU.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.

Thuật toán


Photo of Edsger W. Dijkstra
Edsger Wybe Dijkstra (1930-2002) Sinh năm 1930 tại Rotterdam, Holland. 1948-1956 học Toán và Vật lý lý thuyết tại Đại học Leyden. 1952-1962 nghiên cứu tại Trung tâm Toán học Amsterdam. 1962-1973 Giáo sư Toán tại Đại học Bách khoa Eindhoven, Holland và Đại học Texas Austin. Dijkstra là một trong những người đi tiên phong trong lĩnh vực lập trình, người khởi xướng và đặt nền móng cho nguyên lý lập trình cấu trúc.
Edsger Wybe Dijkstra
(photo ©2002 Hamilton Richards)


Nhận xét:
Đoạn có 1 phần tử là đoạn đơn điệu (tăng, giảm),
Đoạn gồm một dãy liên tiếp các phần tử bằng nhau là đoạn đơn điệu (tăng, giảm).
Ta dùng hai biến đếm các phần tử tăng hoặc bằng nhau liên tiếp, dt và đếm các phần tử giảm hoặc bằng nhau liên tiếp, dg. Nếu ai= ai-1ta tăng đồng thời dt và dg 1 đơn vị. Nếu ai > ai-1 ta tăng dt thêm 1 đơn vị và đặt lại dg = 1. Nếu ai < ai-1 ta tăng dg thêm 1 đơn vị và chỉnh lại dt = 1. Sau mỗi bước ta cập nhật đoạn đơn điệu dài nhất tìm được. Chương trình Pascal đọc và xử lí trực tiếp file input, chương trình C# đọc toàn bộ dữ liệu vào mảng rồi xử lí trên mảng.
Độ phức tạp: cỡ N.
Các biến tổng thể:
n: số lượng phần tử,
dt: đếm số phần tử trong dãy tăng,
dg: đếm số phần tử trong dãy giảm.
iMax: chỉ số đầu của đoạn đơn điệu dài nhất,
MaxLen: chiều dài (số phần tử) của đoạn đơn điệu dài nhất.
(*  Pascal  *)
program DonDieu;
uses crt;
const
 bl = #32;  fn = 'DONDIEU.INP';  gn = 'DONDIEU.OUT';
var f,g: text;
  n: integer;
  dt,dg: integer;
  iMax, MaxLen: integer;
function Max(a,b,c: integer): integer;
begin
  if (a < b) then a := b; { a = Max(a,b) }
  if (a > c) then Max := a
    else Max := c;
end;
procedure XuLi;
 var i,m,x,y: integer;
 begin
   assign(f,fn); reset(f);
   readln(f,n); read(f,x);
   dt := 1; dg := 1;
   MaxLen := 1; iMax := 1;
   for i := 2 to n do
    begin
     read(f,y);
     if (y = x) then
       begin  dt := dt + 1;  dg := dg + 1; end
       else if (y > x) then
        begin  dt := dt + 1;  dg := 1;  end
       else { y < x }
        begin  dg := dg + 1;  dt := 1;  end;
     m := Max(MaxLen, dt, dg);
     if (m > MaxLen) then
       begin  MaxLen := m; iMax := i - MaxLen + 1;  end;
     x := y;
    end;
   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