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
Thursday, December 19, 2013



Trong một hội nghị khoa học có n nhà khoa học (KH)  tổ chức thư giãn dưới hình thức sau. Họ đặt một máy tính trong căn phòng hẹp, ngoài máy ra chỉ có thể chứa thêm 1 người, màn hình máy tính hiện số 0. Sau đó mỗi nhà khoa học buộc phải thực hiện n thao tác loại 1 và n thao tác loại 2 đan xen nhau, trong đó thao tác đầu tiên phải là loại 1.
 Tag: gia sư tin học, gia sư tin học tại nhà
Thao tác loại 1: Đọc
Thao tác loại 2: Ghi
s         Vào phòng;
s         Đọc và ghi nhớ số trên màn hình;
s         Ra khỏi phòng.
s           Vào phòng;
s           Lấy số nhớ trong đầu cộng thêm 1 và hiển thị kết quả trên màn hình;
s           Ra khỏi phòng.

 Khi hiển thị số mới trên màn hình thì số cũ trên màn hình tự động bị xóa và người thực hiện thao tác loại 2 cũng quên luôn số đã nhớ. 
Cho trước các giá trị n và m. Hãy bố trí một lịch thực hiện để các nhà khoa học hoàn thành trọn vẹn cuộc chơi theo đúng yêu cầu và số cuối cùng hiển thị trên màn hình là m.
Dữ liệu vào: Tệp văn bản KH.INP chứa 2 số n và m trên một dòng cách nhau qua dấu cách.
Dữ liệu ra: Tệp văn bản KH.OUT chứa một lịch thực hiện gồm một dãy tuần tự các dòng lệnh thuộc một trong hai dạng sau:
Dạng thứ nhất gồm hai số tự nhiên ghi cách nhau qua dấu cách, i t cho biết nhà khoa học i thực hiện thao tác t; i Î {1,2,…,n}; t Î{1,2}.
Dạng thứ hai gồm 4 số tự nhiên ghi cách nhau qua dấu cách, i t1t2 k cho biết nhà khoa học i thực hiện k lần liên tiếp các thao tác t1 và t2 đan xen nhau; i Î {1,2,…,n}; t Î{1,2};  k > 0.
Nếu không có cách nào bố trí lịch thì ghi duy nhất một số 0.
Thí dụ,

KH.INP
KH.OUT
Ý nghĩa
3 4


1 1
3 1 2 3
1 2
2 1
1 1 2 2
2 2
2 1 2 2


Có 3 nhà khoa học tham gia trò chơi thư giãn với nhiệm vụ sinh ra kết quả trên màn hình (MH) là số 4. Lịch thực hiện sẽ như sau:
Người số 1: Đọc. MH = 0. Đầu(1) = 0.
Người số 3: (Đọc; Ghi) 3 lần. MH = 3.
Người số 1:  Ghi. MH = Đầu(1)+1 = 0+1 = 1.
Người số 2: Đọc. Đầu(2) = 1, MH = 1.
Người số 1: (Đọc; Ghi) 2 lần. MH = 3.
Người số 2 Ghi. MH = Đầu(2)+1 = 1+1 = 2.
Người số 2 (Đọc;Ghi) 2 lần. MH = 2+2 = 4.
Chú thích: Đầu(i) - số nhớ trong đầu nhà khoa học thứ i.

 Thuật toán

Ta sẽ chỉ ra rằng với mọi n ³ 2 và mọi m trong khoảng 2..n2 luôn luôn có một lịch thỏa yêu cầu của đầu bài (ta gọi là lịch hợp lệ) để màn hình (MH) đạt giá trị m.
Sau khi mở tệp KH.INP và đọc hai giá trị n, m ta tiến hành xếp lịch và ghi dần kết quả vào tệp KH.OUT mở sẵn. Trước hết ta nhận xét rằng nếu một người thực hiện liên tiếp k lần một cặp thao tác (Đọc - Ghi, viết tắt là ĐG), tức là sau 2k dòng lệnh
i  1
i  2
...
i  1
i  2
thì giá trị của MH được tăng thêm k đơn vị. Dãy 2k lệnh trên có thể viết gộp lại thành một lệnh 4 thành phần là    i  1  2  k.
Ta tính k = m div nr = m mod  n, ta có m = k.n+r , 0 £ r < n, với ý nghĩa là để đạt được giá trị m trên MH thì phải có k người thực hiện đầy đủ và liên tiếp n cặp thao tác ĐG, ngoài ra phải có ít nhất một người thực hiện thêm r cặp thao tác ĐG.  Do yêu cầu mỗi người buộc phải thực hiên n thao tác Đ và n thao tác G, một lẽ tự nhiên, ta phải sử dụng 2 người ghi nhận giá trị hiện có trên MH để khi cần sẽ trả lại giá trị đó (dĩ nhiên là phải cộng thêm 1) nhằm đảm bảo cho các thao tác cần thiết được thực hiện liên tục.  Xét 3 trường hợp sau đây.
Trường hợp 1: r = 0, tức là m = k.n. Ta cần k người thực hiện liên tiếp n cặp thao tác ĐG. Tuy nhiên, do những người khác cũng phải thực hiện đầy đủ n cặp thao tác ĐG cho mỗi người, nên ta chia các thao tác thành hai loại là các thao tác vô ích là những thao tác đến một thời điểm nào đó sẽ có một thao tác khác đặt lại giá trị cho MH. Các thao tác còn lại được gọi là thao tác có ích. Như vậy trường hợp này cần có k người thực hiện tổng cộng m = k.n cặp thao tác có ích và mọi thao tác còn lại là vô ích. Lịch khi đó sẽ như sau.
1 1  - Người số 1 Đọc và nhớ số 0 trên màn hình. Đầu(1) = 0.
i 1 2 n ; i = k+1..n - Những người còn lại (mang mã số k+1..n) ĐG n lần vô ích.
1 2 -  Người số 1 ghi số 1 lên màn hình (có ích), MH = Đầu(1)+1 = 0 + 1 = 1.
1 1 2 n-1  - Người số 1 ĐG  nốt n-1 lần có ích, MH = n.
i 1 2 n ; i =  2..k  - Những người số 2..k ĐG n lần có ích, MH = n+(k-1).n = k.n = m.
Trường hợp 2: r ¹ 0 và k > 0. Ta có m = k.n+r, 0 < r < n, k > 0. Trường hợp này cần n-1 người thực hiện các thao tác vô ích, 1 người thực hiện r cặp thao tác ĐG có ích và cũng chính người đó phải thực hiện (n-r) cặp thao tác vô ích. Ta sử dụng 2 người , số 1 và số 2 như sau. 
1 1 - Người số 1 Đọc và nhớ  số 0. Đầu(1) = 0.
i 1 2 n ; i =  k+2..n - Những người mã số từ k+2 đến n ĐG n lần  vô ích.
1 2 - Người số 1 Ghi 1 lên MH. MH = Đầu(1)+1 = 0 + 1 = 1.
2 1 - Người số 2 Đọc và nhớ số 1. Đầu(2) = 1.
1 1 2 n-r - Người số 1 ĐG n-r lần vô ích.
Tiếp đến là những thao tác có ích:
2 2 - Người số 2 Ghi số 2 lên MH, MH = Đầu(2)+1 = 1 + 1 = 2.
1 1 2 r-1 - Người số 1 ĐG nốt r-1 lần có ích, MH = 2+(r-1).
2 1 2 n-1 - Người số 2 ĐG nốt n-1 lần có ích, MH = 2+(r-1)+(n-1) = n+r.
i 1 2 n ; i = 3..k+1 - Những người số 3..k+1  ĐG n lần có ích, MH = n+r+(k-1).n = k.n+r.
Trường hợp 3: r ¹ 0 và k = 0, do đó m = r ³ 2. Trường hợp này cần n-1 người thực hiện các thao tác vô ích, 1 người thực hiện r cặp thao tác ĐG có ích và cũng chính người đó phải thực hiện (n-r) căp thao tác vô ích. Ta sử dụng 2 người , số 1 và số 2 như sau. 
1 1 - Người số 1 Đọc và nhớ số 0 trên MH. Đầu(1) = 0.
i 1 2 n ; i = 3..n - Những người từ số 3 đến n ĐG n lần vô ích.
2 1 2 n-1 - Người số 2  ĐG n-1 lần vô ích.
1 2 - Người số 1 Ghi số 1 lên MH. MH = Đầu(1)+1 = 0+1 = 1.
2 1 - Người số 2  Đọc số 1 trên MH. Đầu(2) = 1.
1 1 2 n-r+1 - Người số 1 ĐG  n-r+1 lần vô ích.
2 2 - Người số 2 Ghi số 2 lên MH. MH = Đầu(2)+1 = 1+1 = 2.
1 1 2 r-2 - Người số 1 ĐG  r-2 lần có ích, MH = 2 + (r-2) = r.  
Phần dưới đây trình bày cấu trúc dữ liệu và các thủ tục đọc và  xếp lịch. Hai thủ tục phụ trợ Lenh2 và Lenh4 dùng để ghi một lệnh 2 tham biến dạng i t và lệnh 4 tham biến dạng i t1  t2  k vào output file g KH.OUT. Trong các chú thích dưới đây d[i] là số trong đầu nhà KH thứ i, t[i] là số thao tác ĐG nhà KH i đã thực hiện, MH – màn hình, kí hiệu MH = x cho biết ta không quan tâm đến giá trị của MH vì sớm muộn giá trị này sẽ bị xóa.
uses crt;
const
fn = 'kh.inp'; gn = 'kh.out';
bl = #32; nl = #13#10; mn = 100;
{ bl – dấu cách; nl – xuống dòng }
type
  mi1 = array[0..mn+1] of integer;
var
f,g: text;
n, m, mh: integer;
d,t: mi1;
{ mh – Màn hình }
  d[i] - so nho trong dau,
  t[i] - con dem lenh cua nguoi i }
procedure Doc;
begin
 assign(f,fn); reset(f);
 read(f,n,m); close(f);
end;
procedure Lenh2(i,tt: integer);
begin writeln(g,i,bl,tt); end;
procedure Lenh4(i,tt1,tt2,k: integer);
begin if k > 0 then writeln(g,i,bl,tt1,bl,tt2,bl,k); end;
procedure XepLich;
var k,r,i: integer;
begin
  assign(g,gn); rewrite(g);
  if (n < 2) or (m < 2) or (m > n*n) then
  begin writeln(g,0); close(g); exit; end;
  k := m div n; { k nguoi co ich }
  r := m mod n; { va r thao tac co ich }
  if (r = 0) then
  begin
    Lenh2(1,1); {MH=0,d[1]=0,t[1]=1}
    for i := k+1 to n do Lenh4(i,1,2,n);
    {MH=x,t[i]=2n,i=k+1..n}
    Lenh2(1,2); {MH=1}
    Lenh4(1,1,2,n-1); {MH=n,t[1]=2n}
    for i := 2 to k do Lenh4(i,1,2,n);
    { MH =n+(k-1)n=kn=m,t[i]=2n,i=2..k}
    close(g); exit;
  end;
  { r > 0 }
  if k > 0 then
   begin { r,k > 0 }
    Lenh2(1,1); {MH=0,d[1]=0,t[1]=1}
    { Bo nhung nguoi vo ich }
    for i:=k+2 to n do Lenh4(i,1,2,n);
    {MH=x,t[i]=2n,i=k+2..n}
    Lenh2(1,2); {1 Ghi;MH=1,t[1]=2}
    Lenh2(2,1); {2 Doc;MH=1;d[2]=1,t[2]=1}
    { Cac thao tac vo ich cua 1 }
    Lenh4(1,1,2,n-r); {MH=x,t[1]=2+2(n-r)=2(n-r+1)}
    { Tu day la cac thao tac co ich }
    Lenh2(2,2); {MH=2,t[2]=2}
    Lenh4(1,1,2,r-1);
    {MH=2+r-1,t[1]=2(n-r+1)+2(r-1)=2n}
    Lenh4(2,1,2,n-1);{MH=2+r-1+n-1=n+r,t[2]=2n}
    for i := 3 to k+1 do Lenh4(i,1,2,n);
    {MH=n+r+(k-1)n=kn+r=m,t[i]=2n,i=3..k+1}
    close(g); exit;
   end;
  { k = 0, r > 0 }
  Lenh2(1,1); {1 Doc,d[1]=0,t[1]=1}
  { Bo nhung nguoi vo ich }
  for i:=3 to n do Lenh4(i,1,2,n);{MH=x,t[i]=2n,i=3..n}
  { n-1 thao tac vo ich cua 2 }
  Lenh4(2,1,2,n-1);{MH=x,t[2]=2(n-1)}
  Lenh2(1,2); {1 Ghi,MH=1,t[1]=2}
  Lenh2(2,1); {2 Doc,MH=1,d[2]=1,t[2]=2n-2+1=2n-1}
  { Cac thao tac vo ich cua 1 }
  Lenh4(1,1,2,n-r+1);{MH=x,t[1]=2+2(n-r+1)=2(n-r+2)}
  Lenh2(2,2); {MH=2,t[2]=2n}
  Lenh4(1,1,2,r-2);{MH=2+r-2=r=m,t[1]=2(n-r+2)+2(r-2)=2n}
  close(g);
end;
Bạn có thể viết thêm thủ tục test để kiểm tra xem lịch đã xếp và ghi trong tệp KH.OUT có thỏa các yêu cầu của đầu bài hay không. Thủ tục sử dụng các mảng sau đây. Mảng d[1..n], d[i] là số nhớ trong đầu người số i. Mảng t[1..n], t[i] là số lần người thứ i thực hiện các thao tác Đọc (1), Ghi (2). Do thao tác Đọc phải thực hiện trước và hai thao tác Đọc - Ghi phải đan xen nên thời điểm sát trước thao tác Đọc của người thứ i ta phải có t[i] là số chẵn và thời điểm sát trước thao tác Ghi phải có t[i] là số lẻ. Mỗi lần đọc 1 dòng lệnh thủ tục phải xét xem dòng lệnh đó chứa 2 hoặc 4 số. Thủ tục phải thực hiện các kiểm tra sau đây.
Kiểm tra lệnh dạng i  v: 1 £  i £ n, v = 1 hoặc 2. Nếu v = 1 thì t[i] phải là số chẵn, nếu v = 2 thì t[i] phải lẻ.
Kiểm tra lệnh dạng i  v1  v2  k: tương tự như trên.
Thực hiện lệnh  i  v: Nếu v = 1 (thao tác đọc) thì gán d[i] := MH; ngược lại, nếu v = 2 (ghi) thì gán MH := d[i] + 1. Trong cả hai trường hợp đều tăng con đếm lệnh t[i] thêm 1 đơn vị.
Sau khi đọc xong tệp KH.OUT phải duyệt lại các con đếm để đảm bảo rằng d[i] = 2.n với mọi i = 1..n. Cuối cùng kiểm tra xem MH = m?

procedure DocLenh(var i,t1,t2,k,v: integer);
begin
  read(g,i,t1); v := 2;
  if seekeoln(g) then exit;
  readln(g,t2,k); v := 4;
end;
procedure XemLenh(i,t1,t2,k,KieuLenh: integer);
begin
  if KieuLenh = 2 then writeln(i,bl,t1)
   else writeln(i,bl,t1,bl,t2,bl,k);
end;
function Lenh(i,c: integer): Boolean;
begin
  Lenh := false;
  if (i < 1) or (i > n) then exit;
  case c of
   1: begin
        if odd(t[i]) then exit;
        inc(t[i]); d[i] := mh;
      end;
   2: begin
        if not(odd(t[i])) then exit;
        inc(t[i]); mh := d[i]+1;
      end;
  else exit;
  end;
  Lenh := true;
end;
function KiemTraLenh(i,t1,t2,k,v: integer): Boolean;
 var j: integer;
begin
  if v = 2 then KiemTraLenh := Lenh(i,t1)
  else
  begin
    KiemTraLenh := false;
    for j := 1 to k do
      begin
        if not Lenh(i,t1) then exit;
        if not Lenh(i,t2) then exit;
      end;
    KiemTraLenh := true;
  end;
end;
procedure Test;
 var i,t1,t2,k,v,n2: integer;
begin
  mh := 0;
  fillchar(d,sizeof(d),0);
  fillchar(t,sizeof(t),0);
  assign(g,gn); reset(g);
  while not Seekeof(g) do
  begin
     DocLenh(i,t1,t2,k,v);
     XemLenh(i,t1,t2,k,v);
     if not KiemTraLenh(i,t1,t2,k,v) then
      begin
        writeln('Sai '); close(g);
        exit;
      end;
  end;
  n2 := n+n;
  for i:=1 to n do
   if (t[i] <> n2) then
     begin
       writeln('Sai '); close(g);
       exit;
     end;
  if (mh <> m) then
     begin
       writeln('Sai '); close(g);
       exit;
     end;
  writeln('Dung');
  close(g);
end;


Độ phức tạp

Thuật toán phát sinh và ghi vào file kết quả tối đa 2.n2dòng lệnh.


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