Bài toán: Tìm số

In

Thứ năm, 21 Tháng 7 2011 22:07

tinhoche11_02

Bài toán: Tìm số                                          Mã file: SEARCH

Trong quá trình viết phần mềm quản lý, người lập trình thường gặp phải vấn đề với những mã số quản lý của các đối tượng trong phần mềm (ví dụ như mã số của nhân viên, của phòng…). Ở đây ta xem xét một bài toán đặt ra là: trong quá trình viết phần mềm quản lý nhân sự cho một công ty, mỗi nhân viên được phần mềm gắn cho một mã số (mã số không được trùng nhau giữa 2 nhân viên bất kỳ) được đánh số lần lượt là 1, 2, 3, 4… Tuy nhiên, có trường hợp là có một số nhân viên sau một thời gian sẽ nghỉ và phải tuyển nhân viên mới vào. Nhân viên mới cũng được phần mềm gắn cho một mã số.

 

Yêu cầu: với n mã số hiện có. Hãy tìm ra mã số bé nhất có thể gắn cho nhân viên mới.

Dữ liệu vào từ file ‘SEARCH.INP’:

Dòng đầu là số nguyên dương n (1≤n≤50000).

N dòng tiếp theo mỗi dòng chứa một mã số ai (1≤ai≤2.000.000.000).

Kết quả ghi vào file ‘SEARCH.OUT’ ghi mã số tìm được.

Ví dụ:

SEARCH.INP

SEARCH.OUT

5

2

3

1

5

7

4

Lời giải tham khảo:

Lời giải 1:

const fi='SEARCH.INP';
      fo='SEARCH.OUT';
var n,maMin:longint;
    A:array[1..1000000]of longint;
    f:text;
procedure docfile;
var i:longint;
begin
assign(f,fi); reset(f);
read(f,n);
for i:=1 to n do  readln(f, A[i]);
close(f);
end;
procedure hoandoi(var a,b:longint);
var tg:longint;
begin
tg:=a;
a:=b;
b:=tg;
end;
procedure Qsort(d,c:longint);
var i,j,Y:longint;
begin
i:=d; j:=c;
Y:=a[(i+j) div 2];
repeat
   while a[i]<Y do inc(i);
   while a[j]>Y do dec(j);
   if i<=j then
    begin
     hoandoi(a[i],a[j]);
     inc(i); dec(j);
    end;
until i>j;
if i<c then Qsort(i,c);
if d<j then Qsort(d,j);
end;
procedure xuly;
var i,j:longint;
begin
  Qsort(1,n);
  if a[1]>1 then maMin:=1
  else begin for i:=1 to n do
      begin
      j:=0;
      if a[i+1]-a[i] >1 then begin maMin:=a[i]+1;break; end
      else j:=j+1;end;
  if j<>0 then maMin:=a[n]+1;end;
end;
procedure ghifile;
begin
assign(f,fo);
rewrite(f);
writeln(f,maMin);
close(f);
end;
BEGIN
DOCFILE;
xuly;
GHIFILE;
END.

Lời giải 2:

const fi='SEARCH.INP';
      fo='SEARCH.OUT';
var dd:array[1..1000000]of byte;
    n,kq:longint;
    f:text;

procedure docfile;
var i,x:longint;
begin
    assign(f,fi);reset(f);
    readln(f,n);
    for i:=1 to n do
        begin
            read(f,x);
            if x<=n then
                dd[x]:=1;
        end;
    close(f);
end;

procedure xuly;
var x:longint;
begin
    for x:=1 to n+1 do
        if dd[x]=0 then
            begin
                kq:=x;
                break;
            end;
end;

procedure ghifile;
begin
    assign(f,fo);rewrite(f);
    writeln(f,kq);
    close(f);
end;

begin
    docfile;
    xuly;
    ghifile;
end.

(Chương trình tập huấn kỹ năng lập trình và công tác bồi dưỡng HSG dành cho GV THCS - hè 2011)