Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



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.
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 divmod 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
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts