4. Chơi Ô ăn quan.
Trò chơi “Ô ăn quan” là trò chơi dân gian thú vị gắn với tuổi thơ của nhiều người. Trò
chơi thật đơn giản nhưng chứa nhiều yếu tố bất ngờ: bạn bốc một ô sỏi của mình rồi rải đều
trên các ô (mỗi ô 1 viên) theo một chiều nào đó, khi hết sỏi nếu gặp ô tiếp theo có sỏi thì lại
bốc sỏi của ô này và rải tiếp, nếu cách một ô mới gặp ô có sỏi thì được “ăn” số sỏi ở ô có sỏi
này…
Một số bài toán tin học cũng học cách rải sỏi của trò chơi này để phân bố các giá trị
của các biến đếm vào các ô nhớ.
Ví dụ 1. Tạo các số Hexa
Hãy tạo tất cả các số nguyên tăng dần từ 1 đến 10000 trong hệ đếm Hexa (là hệ đếm
có cơ số 16).
Phân tích
Mỗi số x<1000 trong hệ đếm Hecxa có thể biểu diễn dưới dạng: x=x1.163 + x2.162 +
x3.16 + x4 (mà 0 xi<16, i=1, 2, 3, 4). Để hình thành các số x1, x2, x3, x4 chúng ta tạm tạo ra 4 ô
là A1, A2, A3 và A4 theo thứ tự xếp từ trái qua phải. Sau đó chúng ta lấy 10000 viên sỏi rải vào
các ô này theo nguyên tắc: Mỗi lần rải 1 viên cho đầy ô A4 (nghĩa là đủ 16 viên, viên thứ nhất
ứng với số 0, viên cuối ứng với số 15). Khi A4 đầy, thì “ăn” hết quân của A4, và rải một quân
vào A3, tiếp theo lại quay về rải cho đầy A4, rồi lại “ăn” hết quân của A4 và rải thêm một
quân vào A3, quá trình này lặp đến khi A3 đầy (đủ 16 quân) thì “ăn” hết quân ở A3, đồng thời
rải một quân vào A2, lại quay về rải quân bắt đầu từ ở A4… quá trình tiếp tục làm đầy dần
A2…, cứ thế lặp cho đến khi hết 10000 viên sỏi. Tập hợp các số lượng sỏi ở các ô A1, A2, A3 và
A4 sau mỗi lần rải 1 viên sỏi là các số x1, x2, x3, x4 trong biểu diễn một số nguyên x dưới dạng
Hexa. Khi x tăng dần từ 1 đến 10000 ta biểu diễn được các số nguyên từ 1 đến 10000 trong
hệ Hexa. Chỉ lưu { một điều là xi=10 biểu diễn bằng ‘A’, xi=11 biểu diễn bằng ‘B’, … , xi=15
biểu diễn bằng ‘F’,
Văn bản chương trình
Program Tao_so_Hexa;
const fo = 'hexa.out';
L = 4;
M = 15;
KT : array[0..15] of char =
('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F');
var a : array[1..L] of integer;
i : integer;
g : text;
OK : boolean;
Procedure hien;
var i : integer; value : longint;
begin
for i:=1 to L do write(g,KT[a[i]]);
value := 0;
for i:= 1 to L do value := a[i] + value*(M+1);
writeln(g,' = ',value);
if value = 10000 then Ok := true;
end;
Procedure tao(L : byte);
var i,j : integer;
begin
inc(a[L]);
if a[L]>M then begin
a[L] := 0;
if L>1 then tao(L-1)
else exit;
end;
end;
BEGIN
for i:=1 to L do a[i]:= 0;
assign(g,fo); rewrite(g);
OK := false;
repeat
tao(L);
hien;
until OK;
close(g);
END.