Thuật toán số siêu xấu

Đề bài

Nhập vào số nguyên dương N (0 ≤ N ≤ 10000). Tìm số siêu xấu nhỏ nhất sao cho số đó lớn hơn N. Giả sử dữ liệu nhập vào hợp lệ.
Số siêu xấu là số đối xứng chỉ có các chữ số lẻ 1, 3, 5, 7, 9.
Ví dụ:
Nhập N = 49 kết quả là 55.
Nhập N = 123 kết quả là 131.
Nhập N = 7349 kết quả là 7557.

Source bài giải

AutoIt	http://pastebin.com/qff6MJuc
C#	http://pastebin.com/pYuQueAB
C++	http://pastebin.com/SiHWYwJ9
Pascal

Hướng giải

Có rất nhiều hướng giải cho một bài toán như thế này, kinh điển là việc dùng biến chạy từ n, rồi mỗi lần chạy thì kiểm tra các điều kiện như tính đối xứng của số và các chữ số lẻ.
Nhưng cách trên đa phần gây mất nhiều thời gian và công sức. Ví dụ như nhập 49, chúng ta phải chạy i đến 6 lần, và mỗi lần chạy phải kiểm tra điều kiện.
Vì lí do đó, mình đề xuất giải một cách khác tối ưu hơn, mấu chốt của vấn đề nằm ở điều kiện của số siêu xấu:

Chỉ bao gồm các chữ số lẻ
Đối xứng nhau

Vì vậy, số siêu xấu luôn có một dạng: abba với a và b là những chữ số lẻ. Như vậy, nẩy sinh một vấn đề, đó là chúng ta chỉ cần đi tìm a và b mà thôi.
Ta sẽ tiến hành tìm a và b tại hàng đơn vị cao nhất, nghĩa là đối với số 2 chữ số, ta tìm từ hàng chục; đối với số 3 chữ số; ta tìm từ hàng trăm, đối với số 4 chữ số, ta tìm từ hàng nghìn. Sỡ dĩ như vậy là do chúng ta bị ràng buộc bởi điều kiện số siêu xấu cần tìm phải lớn hơn N.

Ta tìm a và b bằng cách so sánh với các chữ số ở hàng đơn vị cao nhất của N, nếu chúng lẻ thì a hoặc b bằng chúng, nếu chúng chẳng thì a hoặc b bằng chúng cộng thêm cho 1 (để a, b lẻ)
Sau cùng ta chỉ cần tạo ra abba và so sánh lại với n. Nếu abba <= n thì ta tăng b cho 2 rồi tạo lại abba rồi so sánh.

Ý tưởng giải

Bằng ý tưởng trên, chúng ta đi vào ý tưởng giải theo bước như sau:

Bước 1:
Nhập $n với điều kiện đề bài 0 ≤ $n ≤ 10000)
Nếu $n = 9, 99, 999,... thì số siêu xấu sẽ là 11, 111, 1111,...
Bước 2:
$nLeng = độ dài của số.
Từ đó tìm được $Truc = Round($nLeng/2) là vị trí trục đối xứng

Bước 3:
Mảng $soHang[$nLeng] chứa các chữ số (bắt đầu từ trái qua phải) của $n. Mảng $sieuXau[$Truc] là các chữ số siêu xấu tính từ 0 tới trục đối xứng

Bước 4:
Chạy $i từ 0 đến $Truc, so sánh $soHang[$i] lẻ thì $sieuXau[$i] = $soHang[$i]. Ngược lại $sieuXau[$i] = $soHang[$i]+1 cho thành số lẻ.

Nếu $sieuXau[$i] > $soHang[$i] thì toàn bộ $sieuXau[] còn lại lớn hơn $i đều mang giá trị là 1 (điều kiện này để đảm bảo số siêu xấu phải là số nhỏ nhất lớn hơn n.

Nếu đã chạy xong $i thì đến bước 6

Bước 5:
Chạy từ $i = 0 đến $Truc, nếu $sieuXau[$i] > 9 thì chạy $j từ $i đến 0, so sánh nếu $sieuXau[$j] > 9 thì $sieuXau[$j] = 1, ngược lại $sieuXau[$j]+=2 rồi thoát vòng lặp $j.

Dữ liệu này mang tính chất ví dụ

Bước 6:
Ghép các số $sieuXau[] lại thành và đối xứng nó tạo thành $soSieuXau, so sánh $soSieuXau nếu lớn hơn $n thì $soSieuXau là kết quả, ngược lại tăng $sieuXau[$Truc]+= 2 rồi chạy lại bước 5 đến bước 6.

Sơ đồ thuật giải

Từ ý tưởng trên, chúng ta đưa ra cụ thể về sơ đồ thuật giải. (click vào hình để xem hình lớn)

(click vào đây để xem rõ hơn)

i'm opdo

Xin chào, mình là opdo - một đứa mê những dòng code vô tận. Rất cám ơn vì bạn đã ghé thăm blog của mình ^^. Hi vọng được bạn ủng hộ để blog mình phát triển hơn