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



Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước được gọi là đoạn. Cho dãy gồm N số tự nhiên. Tìm đoạn ngắn nhất có tổng các phần tử bằng giá trị K cho trước.

TDOAN.INP
TDOAN.OUT

21 17
0  2  3  2 10
1  5  5  6 12
20 30 14 8 0
11 0 6 0 0
5

16 3


Dữ liệu vào: tệp văn bản TDOAN.INP
Dòng thứ nhất: hai số tự nhiên N và K,
                1 £ N £ 2000.
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 TDOAN.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). Nếu vô nghiệm thì ghi 0 0.
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

Ta giải bằng kĩ thuật cửa sổ trượt như sau. Xét đoạn a[i..j] với tồng S = a[i] + a[i+1] + … + a[j], i £j. Đoạn này được gọi là cửa sổ. Ta cho cửa sổ này trượt dần qua phải và xét ba tình huống sau đây.
1) (S = K): ta ghi nhận điểm đầu i và độ dài đoạn là j-i+1. Nếu độ dài này nhỏ hơn độ dài LMin thì ta cập nhật lại các giá trị iMin và Lmin (thủ tục Update). Rồi tiếp tục xét cửa sổ mới là a[i+1..j] .
2) (S < K): Ta dịch đầu phải của cửa sổ từ j sang j+1, giữ nguyên đầu trái  (thủ tục Right).
3) (S > K): Ta co đầu trái của cửa sổ từ i thành i+1 (thủ tục Left).
Ta đặt phần tử a[n+1] = 0 làm lính canh.
(****************************************
      TONG DOAN - Doan ngan nhat
      co tong K
****************************************)
program TDoan;
uses crt;
const
 mn = 2001;  bl = #32;
 fn = 'TDOAN.INP'; gn = 'TDOAN.OUT';
type mw1 = array[0..mn] of word;
var f,g: text;
  n,k: word;
  a: mw1;
  iMin, LMin: word;
  iLeft,iRight: word;
  sum: word;
procedure Doc;
 var i: word;
begin
  assign(f,fn); reset(f); readln(f,n, k);
  for i := 1 to n do read(f,a[i]);
  close(f);
end;
procedure Left;
begin
  sum := sum - a[iLeft]; iLeft := iLeft + 1;
  if (iLeft > iRight) then
    begin iRight := iLeft; sum := a[iLeft]; end;
end;
procedure Right;
begin  iRight := iRight + 1;  sum := sum + a[iRight]; end;
procedure Update;
begin
  if (LMin > iRight - iLeft + 1) then
    begin iMin := iLeft; LMin := iRight - iLeft + 1; end;
  Left;
end;
procedure XuLi;
 begin
   iLeft := 1; iRight := iLeft;
   LMin := n + 1; sum := a[1];
   repeat
     if (sum = k) then Update
       else if (sum < k) then Right
         else { sum > k } Left;
   until (iRight > n);
   if (LMin = n+1) then LMin := 0;
 end;
procedure Ghi;
begin
  assign(g,gn); rewrite(g); writeln(g,iMin,bl,LMin); close(g);
end;
BEGIN
 Doc; XuLi; ghi;
END.

Nguồn:

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


tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts