Một số thuật toán có nhiều ứng dụng
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (111.1 KB, 9 trang )
Một thuật toán có nhiều ứng dụng
Xuân Phong
Ta xét bài toán sau:
Bài toán 1: (Số sát sau) cho số tự nhiên a có n chữsố. Hãy hoán vị các chữ số trong a để
được số sát sau số a.
Dữ liệu vào ghi trong tệp văn bản SOSATSAU.INP: dòng đầu tiênlà giá trị n, từ dòng thứ
hai trở đi là các chữ số của a.
Dữ liệu ra là số sát sau của số a và được ghi trong tệpSOSATSAU.OUT. Nếu vô nghiệm
thì ghi chữ số 0. Giới hạn của n là 1000.
Thí dụ:
SOSATSAU.INP
6
526431
SOSATSAU.OUT
531246
Bài giải:
Trước hết ta đọc dữ liệu từ tệp SOSATSAU.INP vào biến n và mảngký tự a[1..n].
procedure doc;
var i : integer;
c: char;
begin
assign(f.fn); reset(f);
readln(f,n); i:=0;
while not eof(f) do
begin
read(f,c);
if(c>='0') and (c<='9') then
begin
inc(i); a[i]:=c;
end;
end;
close(f);
end;
Các hằng và biến được khai báo như sau:
const mn=1000;
fn = 'sosatsau.inp';
gn = 'sosatsau.out';
var a: array[0..mn] of char;
n: interger;
f,g: text;
Chú ý rằng số a có thể có đến 1000 chữ số do đó người ta cóthể viết trên nhiều dòng cho
nen thủ tục đọc phải nhận biết đượccác chữ số thông qua dong lệnh:
if (c>='0') and (c<='9') then...
Thuật toán tìm số sát sau: Để tìm số sát sau của a,ta sửa tại chỗ mảng a theo các bước
sau:
1. Tìm điểm gãy: Duyệt ngược mảng a để tìm vị tríi đầu tiên thoả mãn a[i] < a[i+1].
2. Xét điều kiện kết thúc: Nếu không tìm được chỉsố i như trên, tức là các chữ số của số
đã cho xếp theo thứ tự giảmdần do đó a chính là số lớn nhất, sau nó không còn số nào có
thểnhận được bằng một phép hoán vị được nữa. Bài toán vô nghịêm:dưng thuật toán.
3. Tìm điểm vượt: Ta xét trường tồn tại i trong khoảng1..n để a[i]a[i].
4. Hoán vị: Hoán vị a[i] và a[j].
5. Lật: Lật ngược đoạn a[i+1..n] sẽ thu được số cầntìm.
Với thí dụ đã cho, n=6, a[1..6]=526431 ta thực hiện như sau:
1. Tìm điểm gãy: Duyệt ngược mảng a ta tìm đượci=2; a[2]=2 < a[3]=6.
2. Xét điều kiện kết thúc: Do tìm được chỉ số inên nghiệm của bài toán có thể tìm được từ
bước 3 trở đi.
3. Tìm điểm vượt: Ta duyệt ngược mảng a lầnthứ hai tìm được j=5, a[5]=3>a[2]=2.
4. Hoán vị: Hoán vị a[2] và a[5] ta thu được 536421.
5. Lật: Lật ngược đoạn a[2..6] sẽ thu được a=531246.
Ta viết hàm Next kiểu Boolean cho ra giá trị True nếu có số sát sau,ngược lại hàm cho ra
giá trị False. Để việc duyệt không vượt rangoài giới hạn mảng ta dùng phần tử a[0] làm
lính canh. Ta gán giátrị cho a[0] nhỏ hơn ký tự '0':
a[0]:=pred('0');
Hàm Pred(c) cho ta giá trị sát trước giá trị c. Chương trìnhdưới đây khá gọn và không đòi
hỏi giải thích thêm.
user crt;
const mn=1000;
fn='sosatsau.inp';
gn='sosatsau.out';
var a: array[0..mn] of char;
n: integer; f,g: text;
procedure doc;
var i : integer;
c: char;
begin
assign(f.fn); reset(f);
readln(f,n); i:=0;
while not eof(f) do
begin
read(f,c);
if(c>='0') and (c<='9') then
begin
inc(i); a[i]:=c;
end;
end;
close(f);
end;
function nex: Boolean;
var i,j: integer;
tg: char;
begin
next: false; i:=n-1;
{Duyet nguoc lan thu nhat tim diem gay}
while a[i]>=a[i-1] do
dec(i);
if i=0 then exit;
{Duyet nguoc lan hai tim diem vuot}
j:=n;
while a[j]<=a[i] do dec(j);
{Hoan vi a[i] va a[j]}
tg:=a[i]; a[i]:=a[j];
a[j]:=tg; inc(i);
{Lat doan a[i..n]}
j:=n;
while i< begin>
tg:=a[i]; a[i]:=a[j];
a[j]:=tg; inc(i);
dec(j); end;
next:=true;
end;
procedure Ghi;
{Ghi ket qua vao tep}
var i: integer;
begin
for i:=1 to n do
write(g,a[i]);
writeln(g);
end;
procedure BaiLam;
begin
doc; a[0]:=pred('0');
assign(g,gn); rewrite(g);
