Số sát sau cùng chữ số

Cho số tự nhiên x chiều dài N. Hãy đổi chỗ các chữ số của x để thu được số y sát sau số x.

NXT.INP	NXT.OUT	Dữ liệu vào: tệp văn bản NXT.INP Dòng đầu tiên: số tự nhiên N, 2 £ N £ 1000. Dòng thứ hai: số x Dữ liệu ra: tệp văn bản NXT.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.
6 239521	1 251239

Thuật toán

Trước hết để ý rằng muốn thu được số sát sau của x thì ta phải sửa các chữ số ở hàng thấp nhất có thể của x, do đó thuật toán sẽ duyệt các chữ số của x từ phải qua trái. Ta sẽ tìm hai chữ số x_j và x_i đầu tiên của x tính từ phải qua trái thỏa các điều kiện sau:

Thuận thế phải nhất: x_i < x_j, 1 £ i < j £ N: x_i đứng trước x_j và nhỏ hơn x_j.

Nếu không tìm được hai chữ số như vậy tức là x[1..n] là dãy được sắp giảm dần thì mọi hoán vị các chữ số của x không thể cho ra số lớn hơn x: bài toán vô nghiệm.

Nếu tìm được một thuận thế phải nhất (x_i, x_j) như trên thì ta sửa x như sau:

- Đổi chỗ  x_i và x_j ,

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

Với thí dụ x[1..6] = (2,3,9,5,2,1) ta tìm được: i = 2, x[2] = 3, j = 4, x[4] = 5.

Sau khi hoán vị x[i] và x[j] ta thu được,  x  = (2,5,9,3,2,1)

Số này còn lớn, nếu lật lại đoạn x[3..6] sẽ thu được, x  = (2,5,1,2,3,9). Đây là số cần tìm.

Dưới đây là thuật toán vận dụng thuận thế phải nhất để tạo ra số sát sau theo điều kiện của đầu bài.

   1. Tìm điểm gãy: Duyệt ngược x[1..n] để tìm i đầu tiên thỏa x[i] < x[i+1]. Nếu tìm được i thì thực hiện bước 2, ngược lại: dừng thuật toán với kết quả vô nghiệm.

   2. Tìm điểm vượt: Duyệt ngược x[i..n] để tìm j đầu tiên thỏa x[i] < x[j]. Để ý rằng, nếu đã tìm được i thì j luôn tồn tại (?).

   3. Hoán vị x[i] và x[j],

   4. Lật đoạn x[i+1..N ].

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

Hàm Next dưới đây sửa trực tiếp x[1..n] để thu được số sát sau. Vì số x có thể có đến 1000 chữ số nên ta biểu diễn x theo kiểu mảng kí tự với khai báo type mc1 = array[0..1000] of char. Ta cũng sử dụng phần tử x[0] làm lính canh và khởi trị x[0] := pred('0') là kí tự sát trước chữ số 0.

(* Pascal *)

function Next(var x: mc1; n: integer): Boolean;

   var i,j: integer;

       t: char;

 begin

   Next := false; x[0] := pred('0');

   { Tim diem gay }  i := n - 1;

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

   { x[i] < x[i+1] }

   if (i = 0) then exit; { Ko co diem gay: vo nghiem }

   { Tim diem vuot } j := n;

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

   { Doi cho } t := x[i]; x[i] := x[j]; x[j] := t;

   { Lat doan x[i+1..n] }  i := i + 1; j := 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