Một bài toán nhỏ và cách tư duy

Trưa chủ nhật vô tình thấy bài post và đọc được mấy comment thấy vui vui nên viết bài chơi. Nói trước bài này dễ vậy chứ không có dễ đâu.

Vấn đề là khi gặp vấn đề chúng ta tập trung ngay vào cái phần khó nhất là thuật giải chính mà bỏ qua những vấn đề khác cũng cấp thiết không kém là output với input. Khi làm việc thực tế, xử lý kiểu dữ liệu cũng là thứ cần làm rõ vì nó quyết định thành công hay thất bại của bạn

Thuật toán nên tối ưu ASAP

Tại sao phải nên tối ưu? Vì nếu không tối ưu vài bữa nữa bạn cũng phải vào tối ưu, refactor viết code lại phần bạn đã làm với một tâm trạng mệt mỏi chán nản mà lại không đem lại giá trị, tính năng mới cho sản phẩm.

Trong thực tế, không cần phải vừa tìm một cách giải và chăm chú triển khai cách giải ngay và nộp bài đi về mà cần phải dành thêm tí thời gian nữa để tối ưu. Nếu bạn đủ giỏi và kinh nghiệm chinh chiến lâu thì đúng là nghĩ phát ra ngay nhưng thường là phải nghĩ thêm chút nữa.

Vậy làm sao để tránh chuyện nghĩ ra thuật toán chưa tối ưu.

Phân giải vấn đề nhỏ ra và tối ưu cục bộ trước (không được sót tình huống đặc biệt)

Những bạn đã comment chắc chắn bạn nghĩ rất nhanh về thuật toán chia hết cho 9 và nhét số vào. Và cũng trong các comment đó mình không nhìn thấy các bạn trình bày việc nhét số như thế nào vì các bạn đã cho rằng mình xong phần khó rồi. Thật ra phần khó nằm ở chuyện nhét số đó. Ngoài ra các bạn cũng không có xử lý trường hợp đặc biệt.

Ngoài ra bạn phải để ý về input với output trong lập trình. Đề bài trình bày số nguyên như vậy là đủ nhưng khi lập trình bạn phải xác định lưu input N là kiểu gì. Bạn dùng int cũng được và string cũng được. Nó sẽ có lợi có hại hết sẽ nằm trong mục phân tích sau. Mình giả sử sẽ chọn kiểu int vừa đủ xài

Mình sẽ chia vấn đề ra làm 2 vấn đề nhỏ hơn là

• Tìm cái chữ số để nhét vào
• Tìm vị trí để nhét vào

Tìm chữ số để nhét vào

Hi vọng ai cũng trả lời được một số chia hết cho 9 khi tổng các chữ số chia hết cho 9. Sau đó bạn lập tức suy nghĩ về việc tính tổng các chữ số lại (gọi là t), sau đó tìm số dư của giá trị đó chia cho 9 (r = t % 9). Vậy chữ số từ 0 tới 9 cần tìm đó là x = 9 - r

Thuật toán này sẽ giới thiệu thêm 1 vấn đề khác là tách cái số int N nhập vào thành các chữ số để ngồi tính tổng và có thể sau này sẽ dùng để nhét vào.

Thuật toán này không sai, chỉ có là chưa tối ưu. Bạn phải nghĩ giải pháp cho 1 vấn đề nhỏ nữa là trả về tổng các chữ số của 1 số cho trước nữa. Nếu hồi cấp 3 code bằng pascal thì mình sẽ vật vã rất nhiều dòng code mới xong còn giờ với python mình thì sẽ mất khoảng 1 2 dòng gì đó.

Nhưng:

Tối ưu là bạn chỉ việc lấy chính số N mà dùng. Cụ thể để tính r như trên mình dùng luôn công thức r = N % 9 và tính x = 9 - r.

Công thức tính x đơn giản là x = (9 - (N%9))

Lưu ý sẽ có trường hợp x == 9 thì mình sẽ phải đổi lại x = 0 nha. Tại vì N đã chia hết cho 9 rồi nên bắt buộc nhét ta sẽ nhét số 0 chứ mắc gì phải nhét số 9 cho nó to.

Tìm vị trí để nhét vào

Phần này thuật toán dễ xài thì cứ thử sai nhét vào và tìm số nhỏ nhất xong rồi xuất ra kiểu như

foundmin = vô cực
foreach (vị trí nhét x vào):
    if ({số trả ra} < foundmin):
        foundmin = {số trả ra}
print(foundmin)

Và dĩ nhiên cái này cũng có thể tối ưu luôn vì code này phải xử lý m lần với m là số chữ số của số N. Và mình sẽ để dành cho anh em suy nghĩ chơi.

Nhớ sẽ có trường hợp x = 0 cần xử lý tinh tế chút vì nếu nhét vào bên trái nghĩa là coi như không nhét

Tối ưu toàn bộ các vấn đề con

Các vấn đề con có liên quan nhau cho nên mình cần đứng xa một chút để tối ưu mối liên hệ đó ví dụ nếu tìm ra được x là số 0 thì chắc chắn chúng ta sẽ nhét vào vị trí chữ số thứ 2 của số N mà không cần tính toán gì phức tạp

Phải tối ưu code liên quan tới kiểu dữ liệu

Như trên đã giả định mình nhập N vào với kiểu là số int. Tuy nhiên bạn có thể trick user ở đoạn nhập số bằng nhiều cách khác nhau để hướng về việc nhập một list chữ số và đơn giản hóa việc xử lý.

Nhưng nói chung mình khuyên là đi theo con đường int và viết thêm phần xử lý vì nếu muốn tái sử dụng lại thuật toán này thì mình sẽ viết thành hàm với parameter là int cho tiện rồi xử lý gì đó bên trong sau

Bài giải gợi ý

Input là số N kiểu int

Output là số NN kiểu int (nếu được trả về thêm vị trí nhét vào)

Viết kiểu function để dùng lại khi cần