Thuật toán biểu diễn số bằng que diêm

Hi các bạn, lâu quá không viết blog nên là lục nghề mất rồi :3
Mình có dạo chơi mấy group facebook về lập trình thì có thấy một bài toán mà bản thân cảm thấy rất thích nó @@

Đề bài que diêm

Đề bài que diêm

Thế là ngồi nghiên cứu nó liền, và do là chưa thấy ai (chưa thấy chứ không phải là không có) đề xuất ra cách nào nên mình chỉ suy nghĩ đến một ý tưởng của mình thôi, và blog này sẽ trình bày ý tưởng đó cùng cách thực hiện cho bạn ^^

Mình bắt đầu suy nghĩ, và nhận ra hai cái khó khăn: thứ nhất là chọn sao không được để thừa diêm, và chọn làm sao để được hai số nhỏ nhất và lớn nhất.

Các số hạng được hình thành từ các chữ số, và vì vậy, bài toán này mình nghĩ là chúng ta sẽ đi theo hướng tìm các chữ số và ghép chúng lại với nhau. Mình nhận ra rằng, nếu chúng ta có:

• - 2 que diêm: chúng ta ghép được số 1
• - 3 que diêm: chúng ta ghép được số 7
• - 4 que diêm: chúng ta ghép được số 4
• - 5 que diêm: chúng ta ghép được số 2, 3, 5
• - 6 que diêm: chúng ta ghép được số 0, 6, 9
• - 7 que diêm: chúng ta ghép được số 8

Như vậy, có thế thấy rằng, chúng ta phải có 2 que diêm trở lên để ghép thành 1 số. Điều này có nghĩa là khi ghép các que diêm lại với nhau, chúng ta không được phép để lại thấp hơn 2 que diêm. Ví dụ có 3 que diêm, chúng ta phải ghép thành số 7, vì nếu chúng ta ghép thành số 1, chúng ta sẽ dư 1 que diêm và không thể ghép số nào từ 1 que diêm cả. Và đó là mấu chốt để giải quyết khó khăn thứ hai: không để thừa que diêm nào

Thế còn khó khăn thứ nhất, nếu có n que diêm thì để tạo thành một số hạng nhỏ nhất, mình sẽ ưu tiên chọn những số tốn nhiều que diêm nhất để chúng ta chọn được ít các chữ số nhất. Ví dụ nhé, mình có 15 que diêm, mình sẽ ưu tiên chọn số 8 tốn 7 que diêm, còn dư 8 que diêm mình sẽ ưu tiên chọn số 0 hoặc 6 hoặc 9 tốn 6 que, và cuối cùng còn lại 2 que mình chọn số 1.

Thế thì ở bước hai, chọn 0 hay chọn 6 hay chọn 9? Lúc này mình suy nghĩ tiếp, chúng ta sẽ phải chọn số nhỏ nhất nghĩa là số 0. Và giả sử khi chọn xong hết toàn bộ chữ số đều là số 0 thì chúng ta phải tránh số 0 bằng cách đổi 1 chữ số đã chọn thành chữ số lớn nhì là 6, vì điều kiện đề bài không cho chữ số 0 xuất hiện đằng trước. Giả sử nếu chúng ta chọn được số 0, 1, 3 thì không vấn đề gì, chúng ta có thể xếp thành 103, nhưng nếu chúng ta chọn được 0, 0 thì rõ ràng chúng ta cần đổi số 0 thành số 6 để xếp thành 60, và bạn yên tâm chúng ta sẽ không bao giờ chọn được tất cả chữ số đều là số 0 (nếu như số đó kết hợp từ 2 chữ số trở lên). Vì sao ư?

Ta xét thử nhé, giả sử chúng ta chọn trường hợp 2 chữ số, thì nếu chọn được 2 số 0 thì nghĩa là chúng ta có 12 que diêm (mỗi số 0 chiếm 6 que diêm), nếu có 12 que diêm, thì rõ ràng theo ý tưởng, chúng ta đã chọn số 8 với 7 que diêm rồi. Suy ra không có trường hợp nào chúng ta chọn mà tất cả chữ số đều là số 0. Trừ trường hợp số hạng của chúng ta chỉ có 1 số. Thì chúng ta sẽ chuyển số 0 thành số 6, đây sẽ là điều kiện cần và đủ.

Vậy tóm lại, để tìm một số min, ta sẽ phải:

• - Sử dụng nhiều số diêm nhất có thể để chọn các chữ số
• - Chọn chữ số nào nhỏ nhất có thể
• - Không được để dư 1 que diêm
• - Nếu sau khi chọn hết mà chỉ được 1 chữ số bằng 0 thì đổi chữ số 0 đó thành số 6
• - Sắp xếp các chữ số đó lại theo thứ tự tăng dần
• - Nếu vị trí đầu là số 0, ta đổi số 0 thành vị trí sau nó.
• - Ghép các vị trí lại thành 1 số hạng hoàn chỉnh

Ví dụ nhé: ta có 15 que diêm

• - Max ghép số là 7 que, ta sử dụng 7 que: chọn được số 8
• - Dư được 8 que, max ghép số là 7 que, nhưng nếu dùng 7 que thì dư 1 que, không được, giảm xuống còn 6 que, dùng 6 que thì dư 2 que, được: ta chọn 0 hoặc 6 hoặc 9. Ưu tiên chọn số nhỏ nhất là 0
• - Max ghép số là 7 que, ta chỉ có 2 que, mà 2 que thì ứng với số 1: ta chọn số 1
• - Rốt cục ta chọn được số: 8, 0, 1 sau khi sort lại ta được 0, 1, 8
• - Do số 0 đứng đầu, ta chuyển nó về vị trí sau đó thành: 1, 0, 8
• - Đã ổn, ta ghép thành số 108 là min.

Quá ổn luôn. Tới phần tìm max, ôi dào, có ý tưởng tìm được min thì ứng dụng qua max dễ thôi. Chúng ta sẽ ưu tiên chọn ít diêm để chọn được nhiều chữ số, rồi cũng sort lại nhưng sort từ lớn tới bé rồi ghép lại ^^.

Ví dụ nhé: ta có 15 que diêm

• - Min ghép là 2, ta lấy 2 điêm: chọn được số 1
• - Dư 13, min ghép là 2, ta lấy 2 diêm nữa: chọn được số 1
• - Dư 11, tiếp tục ghép 2: chọn số 1
• - Dư 9, lại ghép 2: chọn số 1
• - Dư 7, y chang: chọn số 1
• - Dư 5, lại ghép 2: chọn số 1
• - Dư 3, không thể ghép 2, vì ghép 2 sẽ dư 1, mà dư 1 thì không có số, ta ghép 3: chọn 7
• - Suy ra ta chọn được: 1, 1, 1, 1, 1, 1, 7
• - Sort lại ta được: 7, 1, 1, 1, 1, 1, 1
• - Quá ổn ghép thành số: 7111111

Ý tưởng đã xong, nhưng ta sẽ giải quyết vấn đề như thế nào? Phần thuật toán các bạn tự suy nghĩ nhé ^^

Dưới đây là demo bằng AutoIT mình làm sẵn, rất mong được các bạn góp ý ^^

Thuật toán đệ quy tháp Hà Nội

Source tham khảo

AutoIt	http://pastebin.com/Zkk6Xsx3
C++	http://pastebin.com/90hpgPV6

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)

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

Thuật toán liệt kê Tool Auto Say Sorry

• XEM SẢN PHẨM MẪU

Xin lưu ý rằng, bài viết này không hướng dẫn cụ thể cách tạo 1 tool tương tự, mà chỉ đưa ra ý tưởng và gợi ý cách giải quyết mấu chốt của vấn đề. Vì vậy bạn cần có tư duy lập trình, kỹ năng lập trình cơ bản trước khi đọc bài viết. Cảm ơn.