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 ý ^^

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

Share this

Related Posts