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



Có 9 chiếc đồng hồ điện tử treo trên một bảng theo sơ đồ 3 ´ 3. Các đồng hồ được mã số từ 1 đến 9 theo trật tự từ trái qua phải, từ hàng trên xuống hàng dưới. Mỗi đồng hồ có 4 điểm chỉ giờ ứng với các giờ 12, 3, 6 và 9. Giờ hiện trỏ của mỗi đồng hồ ứng với điểm sáng à. Để điều khiển các đồng hồ người ta sử dụng 9 phím với các chức năng được mô tả như trong hình vẽ. Khi nhấn vào một phím thì có 4 đồng hồ đồng loạt nhảy điểm sáng đi 90o theo chiều kim đồng hồ để cộng thêm 3 giờ tính từ giờ hiện trỏ. Thí dụ, khi nhấn phím 1 thì 4 đồng hồ 1, 2, 4 và 5 sẽ được chỉnh giờ theo luật trên. Biết giờ hiện tại của các đồng hồ. Hãy xác định một dãy ngắn nhất các phím cần nhấn để các đồng hồ đồng loạt trỏ 12 giờ.



¨



¨



¨



Sơ đồ bố trí
9 đồng hồ
à

¨

¨

¨

à

¨



¨



à



¨





ƒ

 9h

6h

ƒ 9h





¨



à



¨




ˆ

à

¨

¨

¨

¨

à








¨



¨



¨








9h

12h

3h








à



¨



¨








¨

¨

¨

¨

¨

¨


9 phím
điều khiển

¨



à



à



12h

ˆ 6h

6h



1
2
3















4
5
6

9 đồng hồ, à giờ đang trỏ



7
8
9


Dữ liệu vào: tệp văn bản DONGHO.INP gồm 12 dòng
3 dòng đầu tiên gồm 9 số trỏ giờ tại thời điểm đầu bố trí theo ma trận 3´3.
Dòng thứ i trong số 9 dòng tiếp theo, i = 1, 2, 3, 4 ghi 4 số tự nhiên thể hiện mã số của 4  đồng hồ sẽ nhảy điểm sáng 90o khi ta nhấn phím i. 
Các số trên cùng dòng cách nhau qua dấu cách.
Dữ liệu ra: Tệp văn bản DONGHO.OUT gồm hai thông tin:
   - Bài toán có nghiệm (ghi số 1)  hoặc vô nghiệm (ghi số 0).
   - Dãy phím ngắn nhất cần nhấn cho trường hợp có nghiệm.

DONGHO.INP
DONGHO.OUT
9 6 9
9 12 3
12 6 6
1 2 4 5
2 3 5 6
4 5 7 8
5 6 8 9
1 2 3 5
1 4 5 7
3 5 6 9
5 7 8 9
2 5 6 8
1
1 2 4 4


Ý nghĩa: Nhấn lần lượt các phím 1, 2, 4, 4
cả 9 đồng hồ đều đồng loạt trỏ 12 giờ.

Tag: gia sư tin học, gia sư tin học tại nhà

Thuật toán

Ta nhận thấy rằng do các đồng hồ hoạt động độc lập với nhau nên dãy phím cần nhấn là giao hoán, nghĩa là có thể liệt kê dãy phím đó theo trật tự tùy ý. Thí dụ, nhấn các phím 1, 2, 3 sẽ mang lại kết quả như khi nhấn dãy phím 2, 1, 3 hoặc theo bất kì hoán vị nào của 3 phím đó. Ngoài ra, nếu một phím được nhấn đến một bội lần của 4 thì điểm sáng trỏ giờ sẽ quay lại đúng vị trí ban đầu, do đó ta không dại gì mà nhấn một phím qúa 3 lần. Từ hai nhận xét trên ta thấy rằng có thể dùng kỹ thuật vét cạn, cụ thể là xét các tổ hợp dãy phím p[1..9], p[i] = 0..3 biểu thị số lần bấm phím i. Với mỗi tổ hợp p ta tính xem các đồng hồ được cập nhật ra sao. Nếu cả 9 đồng hồ đều nhảy về thời điểm 12 giờ thì ta chọn phương án có số lần bấm phím ít nhất trong số các tổ hợp ứng viên.













1
2
3

1
2
3

1
2
3


4
5
6

4
5
6

4
5
6


7
8
9

7
8
9

7
8
9
















1



2



3
















1
2
3

1
2
3

1
2
3


4
5
6

4
5
6

4
5
6


7
8
9

7
8
9

7
8
9
















4



5



6
















1
2
3

1
2
3

1
2
3


4
5
6

4
5
6

4
5
6


7
8
9

7
8
9

7
8
9
















7



8



9
















Chức năng của các phím điều khiển
Dưới đây là một vài chi tiết sử dụng trong chương trình.  Ta khởi tạo sẵn mảng hai chiều mô tả chức năng của các phím điều khiển, phim[i,j] cho biết khi nhấn phím i thì đồng hồ j sẽ được chỉnh.
var
phim: array[1..9,1..4] of integer;
Sau khi đọc dữ liệu ứng với  thí dụ cụ thể thì mảng phim sẽ được gán trị như sau:
  phim  =  ((1,2,4,5),
       (2,3,5,6),
       (4,5,7,8),
       (5,6,8,9),
       (1,2,3,5),
       (1,4,5,7),
       (3,5,6,9),
       (5,7,8,9),
       (2,5,6,8));      
Bạn cũng nên mô tả sẵn một kiểu mảng 9 phần tử để biểu thị các phím và các đồng hồ.
type mi1 = array[1..9] of
                      integer;
var
 dongHo: mi1;
 f: text;
 imin, imax: longint;
Bạn có thể sử dụng 9 vòng for lồng nhau ứng với 9 phím, mỗi vòng biến thiên từ 0 đến 3 ứng với số lần nhấn phím.  
Biến ts dùng để tính tổng số lần nhấn phím. Dễ thấy, mỗi phím được nhấn tối đa 3 lần, vậy 9 phím sẽ được nhấn tối đa 9.3 = 27 lần. Ta lấy 28 làm gía trị khởi đầu cho việc tính tsmin - tổng số lần nhấn phím ít nhất. Ta cũng nên chuyển các số trên mặt đồng hồ là (12,3,6,9) sang các số hệ 4 là (0,1,2,3) để cho tiện tính toán. Hàm Sum(p) tính tổng 9 phần tử của mảng p - đó chính là tổng số lần nhấn phím của phương án p. Hàm KiemTra(q) thực hiện việc kiểm tra xem 9 đồng hồ có cùng trỏ đến 12h hay không, q[i]  là số lần đồng hồ i được cập nhật khi thực hiện phương án p.
Bạn cũng có thể sử dụng hệ 4 để xử lí như sau: Các phương án nhấn 9 phím biến thiên từ (0,0,0,0,0,0,0,0,0) đến (3,3,3,3,3,3,3,3,3) ứng với imin = 0 và  imax = 49-1 = 218-1 = (1 shl 18) - 1 = 262143. Ta cho i biến thiên từ imin đến imax. Với mỗi i ta xây dựng phương án nhấn phím bằng cách gọi thủ tục Split(i,p) chuyển số i sang dạng biểu diễn hệ 4 để ghi vào mảng p, trong đó p[j] sẽ là số lần nhấn phím j. Biết p ta dễ dàng cập nhật các đồng hồ.
Chương trình dưới đây cài đặt 2 phương án vét cạn,  Run1 – chín vòng for lồng nhau và Run2 - tính toán theo hệ 4.
(* Pascal *)
(* Dong ho *)
const bl = #32; fn = 'DONGHO.INP'; gn = 'DONGHO.OUT';
type mi1 = array[1..9] of integer;
var
 dongHo,kq: mi1;
 f,g: text;
 imin, imax: longint;
 s, tsmin: integer;
var
phim: array[1..9,1..4] of integer;
procedure Split(x: longint; var a: mi1);
var i: integer;
begin
  for i := 1 to 9 do
  begin
    a[i] := x mod 4;
    x := x div 4;
  end;
end;
procedure Doc;
var i,j: integer;
begin
 assign(f,fn); reset(f);
 for i:=1 to 9 do read(f,dongHo[i]);
 for i:=1 to 9 do
   for j:=1 to 4 do read(f,phim[i,j]);
 close(f);
end;
procedure Ghi;
var i,j: integer;
begin
   assign(g,gn); rewrite(g);
   if tsmin = 28 then writeln(g,0) { vo nghiem }
   else
   begin { co nghem }
     writeln(g,1);
     for i := 1 to 9 do
       for j := 1 to c[i] do write(g,i,bl);
     writeln(g);
   end;
   close(g);
end;
procedure Init;
var i: integer;
begin
 for i:=1 to 9 do dongHo[i] := (dongHo[i] div 3) mod 4;
 imin := 0;
 imax := 1;
 imax := (imax shl 18 - 1);
end;
function KiemTra(var q: mi1): Boolean;
var i: integer;
begin
    KiemTra := false;
    for i:=1 to 9 do
     if (dongHo[i]+q[i]) mod 4 <> 0 then exit;
    KiemTra := true;
end;
function Sum(var q: mi1): integer;
 var i,s: integer;
begin
  s := 0;
  for i:=1 to 9 do s := s+q[i];
  Sum := s;
end;
procedure XuLiFor;
var j,k,ts: integer;
    q,p: mi1; { p[i] – so lan nhan phim i }
    i,ikq: longint;
begin
 tsmin := 28; { = 3*9+1 }
 for p[1] := 0 to 3 do
  for p[2] := 0 to 3 do
   for p[3] := 0 to 3 do
    for p[4] := 0 to 3 do
     for p[5] := 0 to 3 do
      for p[6] := 0 to 3 do
       for p[7] := 0 to 3 do
        for p[8] := 0 to 3 do
         for p[9] := 0 to 3 do
           begin
             fillchar(q,sizeof(q),0);
             for j := 1 to 9 do
              begin
               for k := 1 to 4 do
               inc(q[phim[j,k]],p[j]);
              end;
             if KiemTra(q) then
              begin
               ts := Sum(p);
               if ts < tsmin then
               begin
                tsmin := ts;
                kq := p;
               end;
              end;
            end;
end;
procedure XuLi;
var j,k,ts: integer;
    q,p: mi1;
    i,ikq: longint;
begin
 tsmin := 28; { = 3*9+1 }
 for i:=imin to imax do
   begin
     Split(i,p); { bam phim j p[j] lan }
     fillchar(q,sizeof(q),0);
     for j := 1 to 9 do
      begin
        for k := 1 to 4 do
          inc(q[phim[j,k]],p[j]);
      end;
      if KiemTra(q) then
      begin
        ts := Sum(p);
        if ts < tsmin then
        begin
          tsmin := ts;
          ikq := i;
        end;
      end;
   end;
   Split(ikq,kq);
end;
procedure Run1;
begin
 Doc; Init;
 XuLiFor; Ghi;
end;
procedure Run2;
begin
 Doc; Init;
 XuLi; Ghi;
end;
BEGIN
 Run1;
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