Ngày xuân kể về Thuật toán
Nguyễn Xuân Huy
Năm Quý Mùi xin giới thiệu với các bạn một vài thuật toán nhẹ nhàng nhưng có phần bổ
ích dùng trong vài phút vui Xuân. Hầu hết các thuật toán trong bài đều do các bạn học
sinh đề xuất.
Mừng Xuân Quý Mùi Bạn Xuân muốn làm một nền thiếp chúc Tết Quý Mùi gồm 2
n
dòng
văn bản mỗi dòng có đúng n ký tự Q và M sao cho hai dòng kề nhau khác nhau tại đúng
một vị trí, dòng đầu tiên và dòng cuối cùng cũng khác nhau tại đúng một vị trí. Thí dụ, với
n=3 thì nền tấm thiếp của bạn đó sẽ như sau:
QQQ
QQM
QMM
QMQ
MMQ
MMM
MQM
MQQ
Cho trước chiều dài n trong khoảng 1.. 20. Hãy tạo một nền thiếp theo yêu cầu của bạn
Xuân. Kết quả ghi trong tệp văn bản QUYMUI.OUT.
Bài giải
Với n=1 ta có 2 dòng
Q
M
Giả sử ta đã thu được các dòng cho trường hợp n-1. Để thu được kết quả cho n ta thực hiện
2 bước sau đây:
Bước 1: Thêm Q vào các dòng của thiếp n-1
Bước 2: Lật các dòng của thiếp n-1 và thêm M vào mỗi dòng đó.
Thí dụ, với n=2 ta đã có 4 dòng
QQ

QM
MM
MQ
Để tính n=3 ta có
Bước 1:
QQQ
QQM
QMM
QMQ
Bước 2:
MMQ
MMM
MQM
MQQ
Vì hai dòng bất kỳ của thiếp n-1 khác nhau tại đúng 1 vị trí cho nên khi thêm cùng một ký
tự vào đầu dòng của chúng ta vẫn bảo lưu tính chất đó. Dòng cuối của dãy thu được trong
bước 1 và dòng đầu của dãy thu được trong bước 2 đều do 1 dòng duy nhất sinh ra do đó
chung chỉ khác nhau ở ký tự thêm vào đầu dòng (là Q và M). Tương tự, dòng đầu tiên của
bước 1 và dòng cuối cùng của bước 2 cũng được lập luận như trên.
Thuật toán trên đòi hỏi n.2
n
byte lưu trữ cho nên khá tốn kém. Ta thử nghĩ cách khác xem
sao?
Ta sẽ không phát sinh ra các dòng vội mà thử tính xem dòng thứ k trong thiếp n sẽ có dạng
gì.
Muốn vậy trước hết ta giải bài toán ngược sau đây: Biết giá trị của một dòng trong tệp kết
quả, hãy cho biết vị trí của dòng đó trong tệp. Thí dụ, với n=3, dòng 'MQM'
đứng thứ mấy trong tệp với giả thiết là chỉ số được tính từ 0 trở đi? Gọi Index(s) là hàm
cho ta vị trí dòng s (với n cho trước), ta có, theo thí dụ trên Index('MQM')=6. Hàm Index
khá dễ viết. Theo phương thức tạo dòng nói trên ta có ngay hàm sau với n cho trước. Biểu

thức m-id-1 nhằm tính cho trường hợp phải lật các dòng của thiếp n-1 (để thêm ký tự M).
function Index: longint;
var id,m: longint;
i: byte;
begin
id:=0;
m:=1;
for i:=n downto 1 do
begin
m:=2*m;
if s[i]='M' then id:=m-id-1;
end;
Index:=id;
end;
Dựa vào hàm Index ta có thể viết hàm Line(id) tạo ra dòng có số hiệu id cho trước. Tuy
nhiên ta sẽ không theo đuổi hai phương án này mà coi chúng như bước chuyển đổi để đi
tới khái niệm bổ ích sau đây.
Mã Gray
Mã Gray của một số tự nhiên n được tính theo công thức xử lý bit như sau:
Gray(n) = n XOR (n shr 1)
Mã Gray có tính chất vàng sau đây:
Mã Gray của hai số tự nhiên liên tiếp sai khác nhau tại đúng 1 vị trí. Thí dụ, Cho
n=13=1101
2
. Ta có n+1=14=1110 và do đó
Gray(13)=1101
2
XOR 0110
2
=1011

2
= 11 và
Gray(14)=1110
2
XOR 0111
2
=1001
2
= 9
Chúng khác nhau tại bit 1 tính từ đầu phải sang (bạn lưu ý rằng các bit được mã số từ 0 và
tính từ đầu phải). Biết bí mật của mã Gray chúng ta giải bài toán trên quá dễ dàng. Với mỗi
n cho trước, ta tìm mã g=Gray(i) lần lượt với i từ 0 đến 2
n-1
. Sau đó ta duyệt số g thu được,
gặp bit 0 ta viết Q, gặp bit 1 ta viết M là xong. Chương trình QUYMUI.PAS dưới đây giải
bài toán trên trong chớp mắt.
(* QUYMUI.PAS *)
uses crt;
const
fn = 'QUYMUI.OUT';
QM:array[0..1] of char = ('Q','M');
BL=#32; { dau cach }
var
n: word;
f:text;
function GetBit(x:longint;i:byte):byte;
begin
GetBit:= (x shr i) and 1;
end;
procedure ghi(x: longint);

var i: byte;
begin
x:= x xor (x shr 1);
for i := n-1 downto 0 do
write(f,QM[GetBit(x,i)]);
writeln(f);
end;
procedure QuyMui(len: byte);
var i, mu: longint;
begin
n:= len;
mu := 1;
assign(f,fn); rewrite(f);
for i:=0 to (mu shl n)-1 do
ghi(i);
close(f);
end;
BEGIN
QuyMui(5);
END.
Người ta trừ ra sao?
Cho hai số tự nhiên x và y có chiều dài bằng nhau. Giả sử x không nhỏ hơn y. Khi đó hiệu
z=x-y được minh hoạ với x=7123 và y=1749 như sau:
1. Lấy bù chín của y ta được t=9999-y=9999-1749=8250.
2. Tính tổng z=x+t+1=7123+8250+1=15374
3. Bỏ số 1 ở đầu trái ta được kết quả z=5374.
Tại sao vậy?
Thật dễ hiểu, ta có x-y=x+10000-10000-y=x+(9999+1)-y-10000=x+(9999-y)+1-10000
Phép trừ 10000 thực hiện ở bước 3 trong thuật toán trên chỉ đơn giản là bỏ số 1 ở đầu trái.
Ta có thể tổng quát hoá bài toán như sau: Tính z=x-y trong hệ đếm b tuỳ ý.

Trong hệ đếm 10 thì ta bù chín, trong hệ đếm b ta bù (b-1) do đó chỉ cần thay thuật ngữ
″bù chín″ trong thuật toán trên bằng thuật ngữ ″bù (b-1)″ là ta thu được thuật toán trừ tổng
quát.
Gọi k là độ dài của các số tự nhiên với kiểu
Type NatNum = array[1.. k] of integer;
Giả sử ta đã biết giá trị của hệ đếm b.
Ta có thuật toán Tru sau:
Procedure Tru(var x,y,z: NatNum);
var i, nho: integer;
begin
nho := 1;
for i:=k downto 1 do
begin
z[i] := x[i]+(b-1-y[i])+nho;
if z[i] < b then nho:=0 else
begin
z[i]:=z[i]-b;
nho:=1;
end;
end;
Số Kaprekar
Kaprekar là nhà toán học Ân-độ nổi tiếng. Ông đề xuất ra loại số mang tên ông như sau: Số
Kaprekar loại (b,k) là số tự nhiên x thoá các tính chất sau:
(i) x được biểu diễn trong hệ đếm b có đúng k chữ số khác nhau.
(ii)T(x) = x″-x′,
trong đó x′ và x″ là số nhận được từ bằng cách viết các chữ số của x theo trật tự tăng và
giảm dần.
Thí dụ, số 6174 là số Kaprekar loại (10,4). Thật vậy, ta có
x′ = 1467; x″ = 7641 do đó T(x)=T(6174)=x″-x′=7641-1467=6174.
Bạn cũng dễ dàng kiểm tra để thấy rằng 132 là số Kaprekar loại (4,3). Tuy nhiên, bạn nhớ

làm phép trừ 321-123 trong hệ đếm 4.
Không phải với mọi cặp (b,k) đều tồn tại số Kaprekar tương ứng. Chẳng hạn, không tồn tại
số Kaprekar loại (5,4) và loại (6,4).
Bài toán Kaprekar
Với mỗi cặp b và k cho trước hãy tìm số Kaprekar nhỏ nhất. Nếu vô nghiệm ta ghi kết quả
0.
Bài giải
Ta lần lượt duyệt các tổ hợp chặp k của b phần tử
0.. (b-1) và chỉ quan tâm đến các tổ hợp sắp tăng như 123, 124, 567,.. Giả sử x là một tổ
hợp như vậy, ta gọi y là tổ hợp đảo của x. Đặt z=y-x (trong hệ đếm b), ta thấy, nếu z chỉ
gồm các chữ số của x thì chính z sẽ là nghiệm của bài toán, vì T(z)=x″-x′=y-x=z.
Trong chương trình KAPREKAR.PAS dưới đây hàm Next cho ta tổ hợp chặp k tiếp theo
các giá trị 0.. (b-1). Tổ hợp đầu tiên được khởi trị là 0.. (k-1). Hàm T tính tại chỗ và kiểm
tra luôn xem các giá trị x[i] có mặt trong a[1.. k] hay không. Mảng d dùng để đánh dấu các
chữ số có trong tổ hợp a.
Nói thêm về hàm Next. Để lấy tổ hợp tiếp theo thoạt tiên ta dỡ các giá trị liên tiếp (cách
nhau 1 đơn vị) từ (b-1) trở đi cho tới khi gặp khoảng hẫng (cách nhau trên 1 đơn vị). Sau
đó tăng vị trí hẫng thêm 1 đơn vị và xếp thêm liên tiếp cho đủ k phần tử. Nếu không gặp
khoảng hẫng ta dừng thuật toán (Next=false). Thí dụ, với b=10; k=4; giả sử a=(1,2,8,9). Ta
áp dụng hàm Next sẽ thu được a[2] là phần tử hẫng, do đó a được biến đổi thành
a=(1,3,4,5)..
(* KAPREKAR.PAS *)
uses crt;
const mn = 20; bl = #32 { dau cach };
type
mb1 = array[0.. MN] of byte;
var b,k,b1: byte;
a,x,d: mb1;
procedure xem(var x: mb1; n: integer);
var i:byte;

begin
write(bl);
for i:=1 to n do write(x[i]);
end;
procedure init;
var i: byte;
begin
for i:=1 to k do a[i]:=i-1;
a[0]:=b+1;
end;
function next: Boolean;
var i,v: byte;
begin
next:=false;
i:=k; v:=b1;
while a[i]=v do
begin
dec(v); dec(i);
end;
if i=0 then exit;
v:=a[i]+1;
repeat
a[i]:=v;
inc(i); inc(v);
until i > k;
next:=true;
end;
function T: Boolean;
var i,nho:byte;