Số duy nhất

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

VÀ

LẬP TRÌNH