Số Kapreka mang tên nhà toán học Ấn Độ và được mô tả như sau. Đó là
số tự nhiên x viết trong hệ đếm B có đúng K chữ số khác nhau đôi một và x = x’’
-
x’, trong đó x’’ và x’ lần lượt là các số thu được bằng cách sắp lại các chữ số
của số x theo trật tự giảm và tăng dần.
Với mỗi cặp giá trị B và K hãy tìm một số Kapreka.
|
KAPREKA.INP
|
KAPREKA.OUT
|
|
10 4
|
6174
|
Dữ liệu vào: tệp văn bản KAPREKA.INP
Dòng đầu tiên: hai số B và K cách nhau qua dấu cách,
2 £ B £ 10, K < B.
2 £ B £ 10, K < B.
Dữ liệu ra: tệp văn bản KAPREKA.OUT
Số x viết trong hệ đếm B.
Bộ dữ liệu trên cho biết: Trong hệ đếm thập phân (B = 10), x =
6174 là số Kapreka có 4 chữ số (khác
nhau đôi một), x'' - x' = 7641 -
1467 = 6174 = x.
Thuật toán
|
Kaprekar
D. R. (1905-1986) nhà toán học Ấn Độ say mê lý thuyết
số từ nhỏ. Sau khi tốt nghiệp Đại học Tổng hợp Bombay năm 1929 ông làm giáo viên phổ thông
tại Devlali, Ấn Độ. Ông viết nhiều bài
khảo cứu nổi tiếng về lý thuyết số, ma phương và các tính chất kỳ lạ của thế
giới số.
|
Ta dựa vào thuật toán tổ hợp Next của bài trước, sinh lần
lượt các số K chữ số trong hệ b. Lưu ý rằng hệ đếm b sử dụng b chữ số 1..(b-1).
Với mỗi số x được sinh ra theo thuật toán Next ta tính hiệu y = x’’-
x’, trong đó x’’ là số thu được bằng cách sắp lại các chữ số của x theo trật tự
giảm dần và x’ – tăng dần. Nếu y chỉ chứa các chữ số của x thì y chính là một
số Kapreka. Do các tổ hợp x được sinh ra đã chứa các chữ số đôi một khác nhau
và được sắp tăng, nên ta luôn có x'' = x.
Để tìm hiệu của hai số trong hệ b ta nên biểu diễn ngược các số dưới dạng mảng K
phần tử nhận các giá trị trong khoảng 0..b-1. Thí dụ số x = 1234 trong hệ 10 sẽ
được biểu diễn là x[1..4] = (4,3,2,1).
Giả sử x = (x1, x2,…,xK)
và y = (y1, y2,…,yK). Ta tính hiệu z = x –
y = (z1, z2,…,zK)
theo qui tắc sau:
Tính z = x + y* +
1, trong đó y* là dạng bù (b-1) của y.
Sau đó ta bỏ đi
số nhớ cuối cùng.
Dạng bù (b -1) y* = (y1*, y2*,…,yK*)
của số y được tính như sau: yi* = (b -1) – yi, i = 1..K.
Thí dụ, tính 9217 – 468 trong hệ 10. Ta có x[1..4] = (7,1,2,9), y[1..4] = (8,6,4,0), do
đó y*[1..4] = (1,3,5,9). Vậy x - y = x + y*
+ 1 = (7,1,2,9) + (1,3,5,9) + (1,0,0,0) = (9,4,7,8). Kết quả là, 9217 – 468 =
8749.
Qui tắc trên được
giải thích như sau. Xét các số trong hệ đếm b. Kí hiệu z = b-1, khi đó số (z, z,…,z) gồm K chữ số z chính là bK
- 1 và y* = (bK-1)-y. Khi đó,
x - y = x - y + (bK - 1) + 1 - bK
= x + ((bK-1)-y) + 1 - bK
= x + y* + 1 – bK. Việc bỏ số nhớ cuối cùng tương đương với phép trừ
bK vào kết quả.
Dưới đây là thủ
tục tính hiệu z = x – y cho các số viết ngược có tối đa K chữ số trong hệ b.
procedure Hieu;
var i,c,t: integer;
begin
c := 1; { so nho }
for i := 1 to K do
begin
t := x[i] +
((b-1)-y[i]) + c;
z[i] := t mod b;
c := t div b;
end;
end;
Để ý rằng phép cộng hai
số một chữ số trong hệ đếm b > 1 bất kì cho số nhớ tối đa là 1. Ngoài ra do
các phép toán div và mod thực hiện lâu hơn các phép cộng và trừ nên
ta có thể viết lại thủ tục trên như sau.
procedure Hieu;
var i,c,t: integer;
begin
c := 1;
for i := 1 to K do
begin
t := x[i] +
(b-1-y[i]) + c;
if (t >=
b) then
begin
z[i] := t – b; c := 1; end
else begin z[i] :=
t; c := 0; end;
end;
end;
Với số x có K chữ số sắp tăng tức là dạng viết ngược của x’’ ta có
thể thực hiện phép trừ y = x’’ – x’ bằng các thao tác trên chính x theo hai
chiều duyệt xuôi và ngược. Khi thực hiện phép lấy hiệu ta cũng đồng thời kiểm
tra xem mỗi chữ số của y có xuất hiện đúng một lần trong x hay không. Nếu đúng,
ta cho kết quả là true, ngược lại, ta cho kết quả false.
Để thực hiện việc này ta dùng mảng d[1..K] đánh dấu sự xuất hiện của các chữ số
trong x và y.
(*------------------------------
y = x'' - x' (he dem B)
-------------------------------*)
function Hieu: Boolean;
var i,c,t: integer;
begin
fillchar(d,sizeof(d),0);
{ mang danh dau }
Hieu := false;
{ Ghi nhan cac xuat hien cua x[i] }
for i := 1 to k do d[x[i]] := 1;
c := 1; { c: so nho }
for i := 1 to k do
begin
t := x[i] + (b - 1 -
x[k-i+1]) + c;
if (t >= b) then
begin y[i] := t - b;
c := 1; end
else begin y[i] := t;
c := 0; end;
if (d[y[i]] = 0) then
exit;
if (d[y[i]] = 1) then
d[y[i]] := 0;
end;
Hieu := true;
end;
Dưới đây cung
cấp 15 thí dụ để bạn đọc test chương trình. Kết quả 0 cho biết không tồn tại số
Kapreka cho trường hợp đó.
|
NN
|
B
|
K
|
Đáp số
|
NN
|
B
|
K
|
Đáp số
|
NN
|
B
|
K
|
Đáp số
|
|
|
1
|
4
|
3
|
132
|
6
|
8
|
2
|
25
|
11
|
9
|
7
|
0
|
|
|
2
|
5
|
4
|
0
|
7
|
8
|
3
|
374
|
12
|
9
|
8
|
0
|
|
|
3
|
6
|
3
|
253
|
8
|
8
|
7
|
6417532
|
13
|
10
|
3
|
495
|
|
|
4
|
6
|
4
|
0
|
9
|
9
|
5
|
62853
|
14
|
10
|
4
|
6174
|
|
|
5
|
6
|
5
|
41532
|
10
|
9
|
6
|
0
|
15
|
10
|
9
|
864197532
|
|
|
15
thí dụ về các số Kapreka
|
||||||||||||
(* Pascal *)
(***************************************
So Kapreka
***************************************)
program SoKapreka;
uses crt;
const mn = 11; fn = 'KAPREKA.INP'; gn = 'KAPREKA.OUT';
type mb1 = array[0..mn] of
byte;
var x,y,d: mb1;
b,k,b1,v: integer;
{-------------------------------------------
b - he dem
k - so chu so
b1 - chu so lon nhat
trong he b, b1 = b-1
v - bien kiem soat cho
ham Next
---------------------------------------------}
f,g: text;
procedure Doc;
begin assign(f,fn);
reset(f); readln(f,b,k); close(f);
b1 := b-1; { Chu so cao nhat trong he dem b }
end;
function Next: Boolean;
var i: integer;
begin
Next := false;
if (v = 0) then exit;
x[v] := x[v] + 1;
for i := v + 1 to k do
x[i] := x[i-1] + 1;
if (x[k] = b1) then v :=
v - 1 else v := k;
Next := true;
end;
(*------------------------------
y = x'' - x'
-------------------------------*)
function Hieu: Boolean;
var i,c,t: integer;
begin
fillchar(d,sizeof(d),0);
Hieu := false;
{ Ghi nhan cac xuat hien cua x[i] }
for i := 1 to k do d[x[i]] := 1;
c := 1; { c: so nho }
for i := 1 to k do
begin
t := x[i] + (b1 -
x[k-i+1]) + c;
if (t > b1) then
begin t := t - b; c
:= 1; end
else c := 0;
if (d[t] = 0) then
exit; { t ko xuat hien trong x }
y[i] := t; d[t] := 0;
end;
Hieu := true;
end;
function Kapreka: Boolean;
var i: integer;
t: Boolean;
begin
Kapreka := true;
{ Khoi tri x la to hop
tang nho nhat }
{ x[1..k] = (0,1,...,k-1)
}
for i := 1 to k do x[i]
:= i-1;
if (x[k] = b1) then v :=
0 else v := k;
repeat
if (Hieu) then exit;
until not next;
Kapreka := false;
end;
procedure Run;
var i: byte;
begin
Doc;
assign(g,gn);
rewrite(g);
if (Kapreka) then
for i := k downto 1 do
write(g,y[i])
else write(g,0);
writeln(g); close(g);
end;
BEGIN
Run;
END.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét