Thuật toán: In chỉ mục chính xác cho chuỗi ký tự

Question

Tôi gặp phải vấn đề sau trong khi chuẩn bị cho kỳ thi:

Hãy tưởng tượng một bảng chữ cái của các từ. Ví dụ:

a ==> 1 
b ==> 2 
c ==> 3 
... 
z ==> 26 
ab ==> 27 
ac ==> 28 
... 
az ==> 51 
bc ==> 52 
and so on. 

Chuỗi ký tự cần phải theo thứ tự tăng dần (tức là 'ab' hợp lệ nhưng 'ba' thì không).

Câu hỏi: Cho bất kỳ từ nào, in chỉ mục của nó nếu hợp lệ và 0 nếu không.

Input Output 
ab 27 
ba 0 
aez 441 

Mọi gợi ý về cách giải quyết điều này sẽ được đánh giá cao.

Answer 1

Hãy để tôi cung cấp cho bạn một vài gợi ý:

• Bạn có thể tìm thấy một công thức cho số lượng các từ như vậy của một chiều dài nhất định k?
• Hãy sửa chiều dài k và một chữ cái l. Có bao nhiêu từ dài k bắt đầu với l là chúng?

Gợi ý: Hình tam giác Pascal. Nếu bạn cần thêm một số gợi ý, http://en.wikipedia.org/wiki/Combinadic có thể giúp bạn. Nếu bạn cần một số triển khai, bạn có thể lấy cảm hứng từ hàm xếp hạng được xác định bằng (ngôn ngữ Python) https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py

Answer 2

1. đảm bảo đầu vào chỉ là chữ cái. Thất bại nếu không.
2. Thiết lập vòng lặp dựa trên độ dài chuỗi trừ 1.
3. "Trừ" giá trị của chữ cái đầu tiên trong chuỗi từ chuỗi tiếp theo. Nếu giá trị bằng 0 hoặc dương, bạn được thực hiện khi chuỗi không tăng dần để trả về 0.
4. Lặp lại bằng cách di chuyển chuỗi một chữ cái vào lúc kiểm tra chữ cái tiếp theo.
5. Nếu bạn kết thúc, đó là chuỗi thứ tự tăng dần.

Để công bằng, tôi chưa đề cập đến thuật toán về cách tính giá trị chỉ mục, chỉ là trường hợp thoát. Nhưng nó cho bạn một sự khởi đầu đúng hướng và tính toán chỉ số sẽ theo cùng một khuôn khổ.

Thông tin khác:

Bắt đầu đếm lên trên chữ cái đầu tiên. Khi bạn nhấn 'z', hãy đặt lại chuỗi hợp lệ tiếp theo và tiếp tục đếm -> "aa" không đếm được. Thêm vào tiếp theo mà ở đây là "ab". Một khi bạn nhấn "az", hãy thử "ba" - thất bại, tiếp tục thêm chữ cái cho đến khi bạn nhận được một chuỗi hợp lệ "bc" và bắt đầu đếm lại. Nó giống như một đồng hồ đo đếm được lên trên.

Đậm chậm, nhưng nó sẽ hoạt động vì đó là những gì bạn làm theo cách thủ công để nhận câu trả lời.

BTW, có một giải pháp nhiều hơn tao nhã ám chỉ bởi @hivert đó sẽ là gần như tức thì để tính toán ...