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



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ố  xj  > 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ố xi < (b-1) đầu tên sau j để có thể tăng thêm 1 đơn vị. Nếu không tìm được xj hoặc xi thì x không có số sát sau. Nếu tìm được đồng thời hai chữ số xj và xi  như trên thì ta sửa x như sau:
·         Giảm xj 1 đơn vị,
·         Tăng thêm xi 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
LẬP TRÌNH
tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts