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



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ố xj và xi đầ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: xi < xj, 1 £ i < j £ N: xi đứng trước xj và nhỏ hơn xj.
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 (xi, xj) như trên thì ta sửa x như sau:
- Đổi chỗ  xi và xj ,
- 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
LẬP TRÌNH

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts