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



Tệp văn bản UNIQUE.INP chứa dãy số, mỗi số chiếm một dòng dài không quá 20 chữ số. Trong dãy này có duy nhất một số xuất hiện đúng một lần, các số còn lại đều xuất hiện đúng k lần. Hãy tìm số duy nhất đó. Số k không cho trước, nhưng biết rằng đó là một số chẵn khác 0. Kết quả hiển thị trên màn hình.

Tag: gia sư tin học, gia sư tin học tại nhà, dạy lập trình pascal

Thuật toán

Ta dựa vào một kiến thức có từ hàng ngàn năm trước, đó là biểu diễn số theo vị trí. Ta lần lượt đọc từng dòng vào một biến string sau đó ghi vào một mảng a số lần xuất hiện của từng chữ số tại từng vị trí, a[c,i] cho biết số lần xuất hiện của chữ số c tại cột i tính từ trái qua phải.  
Với thí dụ đã cho, trên cột 1 ta tính được a[‘1’,1] = 5, a[‘2’,1] = 4, a[‘3’,1] = 0,... , a[‘8’,1] = 4...
Như vậy mảng a có kích thước 10 hàng đủ chứa 10 chữ số ‘0’..’9’ và 20 cột đủ chứa các chữ số dài nhất. Sau khi đọc xong dữ liệu,  ta thấy mọi phần tử của mảng a hoặc là chia hết cho k do đó là số chẵn, hoặc là số lẻ có dạng m.k + 1, m = 0, 1, 2,... Nếu a[c,i] là số lẻ thì c sẽ là chữ số xuất hiện tại cột i của số duy nhất cần tìm.

Chương trình Pascal

UNIQUE.INP
MÀN HÌNH
1357
2008
80
1357
2008
80
2008
1357
10203040
80
2008
80
1357

10203040

Giải thích: Số duy nhất cần tìm là 10203040. Các số còn lại đều xuất hiện 4 lần.
(* Pascal *)
procedure XuLi;
const mn = 20;
   ChuSo = ['0'..'9'];
      fn = 'unique.inp';
var  a: array['0'..'9',1..mn] of integer;
     f: text;
     i: integer;
     s: string;
    cs: char;
begin
  fillchar(a,sizeof(a),0);
  assign(f,fn); reset(f);
   while not seekeof(f) do
   begin
     readln(f,s);
     for i:=1 to length(s) do
       if s[i] in ChuSo then inc(a[s[i],i]);
   end;
  close(f);
  s := ''; { Ket qua }
  for i := 1 to mn do
    for cs := '0' to '9' do
      if Odd(a[cs,i]) then s := s+cs;
  writeln(s);
end;
BEGIN
  XuLi;
  readln;
END.


Độ phức tạp

Nếu có n số dài tối đa m chữ số thì ta cần xét mỗi chữ số 1 lần, nghĩa là tổng cộng cần  n.m thao tác. Duyệt mảng a cần 10.m thao tác là số rất nhỏ so với n.m.

Các biến thể của bài UNIQUE

1. Nếu đầu bài cho biết số k thì không cần đòi hỏi k là số chẵn.
2. Biết duy nhất một số xuất hiện đúng m lần, các số còn lại đều xuất hiện k lần như nhau, k ¹ m và k và  m nguyên tố cùng nhau. Bạn thử suy nghĩ xem có cần biết cụ thể các giá trị của m và k không? Bạn thử tìm một số điều kiện của k và m?
3.  Thay các số bằng các dãy kí tự A..Z dài tối đa m.


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