Số sát sau cùng độ cao

Chiều dài của một số tự nhiên là số chữ số của số đó. Độ cao của một số tự nhiên là tổng các chữ số của số đó. Cho số tự nhiên x ghi trong hệ đếm b, có chiều dài N. Tìm số tự nhiên y sát sau x có cùng chiều dài, cùng độ cao và cùng hệ đếm với x.

DOCAO.INP	DOCAO.OUT
10 5 2 3 9 9 0	1 2 4 0 8 9

Dữ liệu vào: tệp văn bản DOCAO.INP

Dòng đầu tiên: hai số tự nhiên b và N cách nhau qua dấu cách, 2 £ b £ 100, 2 £ N £ 1000.

Dòng thứ hai: số x với các chữ số ghi cách nhau qua dấu cách.

   Dữ liệu ra: tệp văn bản DOCAO.OUT

   Dòng đầu tiên: ghi 1 nếu có nghiệm, 0: nếu vô nghiệm.

   Dòng thứ hai: số y với các chữ số ghi cách nhau qua dấu cách.

Thuật toán

Độ cao của số x sẽ không đổi nếu ta đồng thời tăng và giảm hai chữ số của x cùng một đơn vị. Ta duyệt lần lượt các chữ số của x từ phải qua trái, trước hết tìm chữ số  x_j  > 0 đầu tiên để có thể giảm 1 đơn vị. Tiếp đến ta duyệt tiếp từ j-1 qua trái tìm một chữ số x_i < (b-1) đầu tên sau j để có thể tăng thêm 1 đơn vị. Nếu không tìm được x_j hoặc x_i thì x không có số sát sau. Nếu tìm được đồng thời hai chữ số x_j và x_i  như trên thì ta sửa x như sau:

·         Giảm x_j 1 đơn vị,

·         Tăng thêm x_i 1 đơn vị,

·         Lật lại đoạn x[i+1..n].

Với thí dụ x[1..5] = (2,3,9,9,0) trong hệ đếm thập phân (b = 10) ta tìm được j = 4, x[j] = 9, i = 2, x[i] = 3. Sau khi giảm x[4] và tăng x[2] 1 đơn vị ta thu được x[1..5] = (2,4,9,8,0). Số này còn lớn, nếu lật lại đoạn x[3..5] sẽ thu được x[1..5] = (2,4,0,8,9). Đây là số cần tìm.

Vì sao lại làm như vậy?  Giải thích điều này khá dễ nếu để ý rằng x[j+1..n] chứa toàn 0 (chữ số nhỏ nhất trong hệ đếm b) và  x[i+1..j-1] chứa toàn (b-1) (chữ số lớn nhất trong hệ đếm b). Từ đó suy ra rằng đoạn x[i+1..n] được sắp tăng. Lật lại đoạn đó ta sẽ thu được dãy các chữ số giảm dần. Vì x[i] đã được thêm 1 đơn vị nên nó lớn hơn số ban đầu. Khi lật lại ta sẽ thu được số sát sau số ban đầu.

Hàm Next dưới đây biến đổi trực tiếp x[1..n] để thu được số sát sau. Ta sử dụng phần tử x[0] = b làm giới hạn cho quá trình duyệt ngược. Phần tử x[0] này được gọi là lính canh. Nó có nhiệm vụ làm cho vòng lặp dừng một cách tự nhiên mà không cần phải kiểm tra giới hạn chỉ số của mảng (rang check).

Độ phức tạp: cỡ N, do mỗi chữ số của x được thăm và xử lí không quá 2 lần.

(* Pascal *)

function Next(var x: mi1; n,b: integer): Boolean;

   var i,j,t,b1: integer;

 begin

   Next := FALSE;

   x[0] := b; j := n;

   while (x[j] = 0) do j := j - 1;

   if (j = 0) then exit; { ko co so sat sau }

   i := j - 1; b1 := b - 1 ;

   while (x[i] = b1) do i := i - 1;

   if (i = 0) then exit; { Ko co so sat sau }

   x[j] := x[j] - 1; x[i] := x[i] + 1;

   i := i + 1; j := n;

   { Lat doan x[i..n] }

   while (i < j) do

     begin

       t := x[i]; x[i] := x[j]; x[j] := t;

       i := i + 1; j := j - 1;

     end;

   Next := TRUE;

 end;

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH