Giúp mình giải bài tập pascal này với! Mình đang gấp lắm

TỪ ĐIỂN
Người ngoài hành tinh rất yêu quý đất nước Việt Nam. Họ quyết định đến thăm chúng ta. Tuy nhiên vì ngôn ngữ bất đồng nên không hiểu những người ngoài hành tinh muốn nói gì. Vì vậy phải mang theo từ điển của mình ra để cho họ xem. Sau đó sẽ đoán xem là họ muốn nói đến từ nào trong từ điển. Từ điển cũng chỉ gồm 26 chữ cái thường từ a đến z. Tuy nhiên vì không thể giải thích được với nhau nên hiện tại bước đầu giao tiếp vẫn là đoán từ và các câu hỏi để đoán từ phải vô cùng đơn giản. Người ngoài hành tinh chỉ có thể hiểu các câu hỏi sau:
1. Có bao nhiêu kí tự C trong từ đó?
2. Kí tự tại vị trí X là kí tự gì?
Nhiệm vụ của các bạn là viết một chương trình GUESS.PAS, sử dụng các hàm trong thư viện DIC.PP để thực hiện khảo sát từ điển trong file dữ liệu vào DIC.DAT và đưa ra từ mà người ngoài hành tinh muốn nói là từ gì.
File DIC.DAT được cung cấp cho các bạn mô tả từ điển chỉ gồm danh sách các từ đôi một khác nhau. Trong đó mỗi từ nằm trên một dòng và chỉ gồm các chữ cái in thường từ ‘a’ đến ‘z’. Số lượng từ trong file DIC.DAT tối đa là 106 từ và mỗi từ dài tối đa 50 kí tự.
Chương trình GUESS.PAS của bạn phải khai báo sử dụng thư viện DIC.PP bằng cú pháp:
Uses dic;
Các hàm và thủ tục được cung cấp trong thư viện DIC.PP function count_char(C: char): longint;
Trả về số lượng kí tự C trong từ cần tìm.
Chi phí sử dụng hàm count_char() 1 lần là 1 đơn vị.
function get_char_at_pos(X: longint): char;
Trả về kí tự tại vị trí X trong từ cần tìm.
Nếu X lớn hơn độ dài của từ, hàm sẽ trả về kí tự ‘#’.
Chi phí sử dụng hàm get_char_at_pos() 1 lần là 10 đơn vị.
Procedure answer(s:string);
Thủ tục answer() được dùng để trả về kết quả - là từ mà em đã xác định được.
Chi phí sử dụng thủ tục answer() là 0 đơn vị.
Chương trình bắt buộc phải gọi thủ tục answer() một lần duy nhất, nếu không sẽ bị 0 điểm. Thủ tục này khi được gọi sẽ tự động thoát chương trình bằng câu lệnh exit.

Với mỗi test, nếu chương trình của bạn gọi thủ tục answer() với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá 1000 đơn vị hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận 0 điểm cho test đó.
Số điểm cho mỗi test sẽ giảm dần khi chi phí bạn sử dụng tăng lên.

Ví dụ:
Bộ từ điển có các từ sau:
cat
can
mic
man
tiger
hello
world
Từ người ngoài hành tinh muốn nói là “cat”. Các thủ tục được gọi
Giá trị trả về
Giải thích
get_char_at_pos(4)
#
Độ dài của từ “cat” là 3 nên khi hỏi độ dài bằng 4 vượt quá độ dài 3, hàm get_char_at_pos(4) trả về giá trị là dấu ‘#’.
count_char(‘c’)
1
Trong từ “cat” có 1 kí tự ‘c’ nên hàm count_char(‘c’) trả về giá trị là 1.
count_char(‘a’)
1
Trong từ “cat” có 1 kí tự ‘a’ nên hàm count_char(‘a’) trả về giá trị là 1.
count_char(‘n’)
0
Trong từ “cat” không có kí tự ‘n’ nên hàm count_char(‘n’) trả về giá trị là 0.
answer(“cat”)
Như vậy bạn đã trả lời đúng với chi phí sử dụng là 13. Chương trình khi gọi answer(“cat”) sẽ đưa đáp án đồng thời thoát chương trình chạy của bạn.
 

tengiday

Happy life
Reply: Giúp mình giải bài này với! Mình đang gấp lắm

- Bài này khó quá bạn. Mình chỉ nghĩ được thuật toán tham lam thôi, lấy ý tưởng của machine learning mình đang nghiên cứu nhé. Ý tưởng là tại mỗi bước, chúng ta chọn cái tốt nhất. Tức là chọn 1 operator sao cho split được các từ gần bằng 2 nửa nhiều nhất (giống như trong binary search vậy).
- Bởi vì chỉ có 26 ký tự và chiều dài max 50 của mỗi từ, số trường hợp cần xét là 26 + 50 = 76 trường hợp, vô cùng khả thi. Cứ như thế lặp lại tại mỗi bước.
- Cách giải này ko phải tối ưu nhất vì không tính đến thứ tự của operators. Tuy nhiên, nó hơn rất nhiều so với trường hợp tệ nhất là dùng getChar tại mỗi vị trí.
 
Reply: Giúp mình giải bài này với! Mình đang gấp lắm

- Bài này khó quá bạn. Mình chỉ nghĩ được thuật toán tham lam thôi, lấy ý tưởng của machine learning mình đang nghiên cứu nhé. Ý tưởng là tại mỗi bước, chúng ta chọn cái tốt nhất. Tức là chọn 1 operator sao cho split được các từ gần bằng 2 nửa nhiều nhất (giống như trong binary search vậy).
- Bởi vì chỉ có 26 ký tự và chiều dài max 50 của mỗi từ, số trường hợp cần xét là 26 + 50 = 76 trường hợp, vô cùng khả thi. Cứ như thế lặp lại tại mỗi bước.
- Cách giải này ko phải tối ưu nhất vì không tính đến thứ tự của operators. Tuy nhiên, nó hơn rất nhiều so với trường hợp tệ nhất là dùng getChar tại mỗi vị trí.
Không biết làm được không nhưng cũng cảm ơn bạn mình hoàn toàn không có ý tưởng gì luôn để mình xây dựng thử nếu được thì mình đăng lên cho mọi người cùng tham khảo. Cảm ơn bạn rất nhiều!!!
 

Bài viết đang hot

Thống kê

Chủ đề
102,777
Bài viết
470,596
Thành viên
340,591
Thành viên mới nhất
Quang Nguyễn NĐ
Top