[Stack]Captcha - Simple Project

Bài toán này nằm trong loạt bài giới thiệu các kiểu dữ liệu - Data Structure

Captcha được phát minh ra nhằm mục đích bảo vệ các trang web và hệ thống khỏi các hành vi phá hoại của các chương trình giả dạng con người (nhằm các mục đích xấu) hay gọi là bot hoặc spam bots. Captcha là chương trình phép thử tự động được tạo ra với mục đích hầu hết mọi người có thể vượt qua trong khi các chương trình máy tính hiện đại không thể vượt qua, đảm bảo robot không thể liên tục truy cập vào server từ một địa chỉ. Captcha là một mã hình ảnh đã được xử lý để robot rất khó đọc được. Tuy nhiên Captcha nảy sinh ra một vấn đề, đó là tốn thời gian của người dùng một cách vô nghĩa . Một vài ông kỹ sư đầu to ở Mỹ đã nghĩ ra một cách rất thông minh giải quyết vấn đề này. Họ dùng mã Captcha cấu tạo gồm 2 phần, phần 1 hệ thống đã biết mã thật (nó hiển thị gì) và phần 2 chưa biết. Người ta sẽ thống kê các kết quả người dùng gõ mã mà đúng phần 1, và được 1 bảng dữ liệu cho phần mã 2. Dữ liệu này được dùng để xác định chính xác đoạn mã 2 viết gì. Nó được sử dụng để số hóa các văn bản mà các hệ thống bot khác không làm được (như dự án số hóa toàn bộ sách của Google cần cái này), giúp tiết kiệm bộ nhớ(lưu text thì đỡ tốn bộ nhớ hơn ảnh), nhận diện chữ viết, huấn luyện robot..vv... Và mã capcha sau khi dc giải mã có thể lại được dùng làm mã capcha thật (đoạn mã 1 ở trên), vào chắc chắn robot ko thể phá được. Sau khi thu thập được dữ liệu gõ capcha của người dùng, mã đúng của nó là kết quả mà trên 75% người dùng gõ. Đó là bài toán thực tế, nhưng hoạt động của nó không hề đơn giản, ở đây mình chỉ đưa ra 1 bài toán rất đơn giản, khi dữ liệu đã được thu thập và sắp xếp. Trong một bài khác, chúng ta sẽ làm việc với dữ liệu thực tế hơn.

Sử dụng Captcha để nhận diện chữ viết, dùng cho các ứng dụng khác

1. USING

Stack

2. QUESTION

Giả sử dữ liệu đã được thu thập và lưu trữ cho từng mã Captcha một, bài toán ở đây rất đơn giản, tìm và in ra đoạn mã được người dùng điền nhiều nhất và tỉ lệ phần trăm (định dạng %.0f) của mã đó trong toàn bộ dữ liệu được lưu.

[Algorithm] Sample Project

Bài này trong loạt bài giới thiệu về các thuật toán và ứng dụng của chúng. Bài viết này mình sẽ mô phỏng theo cấu trúc của 1 bài viết dùng một thuật toán nào đó giải quyết các vấn đề trong thực tế. Khung sườn của 1 bài viết sẽ được trình bày dưới đây.

Các công cụ được sử dụng như đã được giới thiệu là phần mềm VisualStudio bản từ 2012 trở lên. Vì với những bản từ 2012 mới hỗ trợ tối đa cho việc debug và test. Chương trình cũng chỉ bao gồm 2 file là Source chứa code solution, và 1 file input.txt chứa dữ liệu đầu vào.
Đôi khi sẽ có một phần giới thiệu sơ lược về thuật toán sẽ áp dụng, mô tả cách hoạt động và hiệu quả của thuật toán.

[Dynamic] Part1.Bài toán cây ATM

Bài toán này nằm trong loạt bài giới thiệu thuật toán "Quy hoạch động" - Dynamic

Thuật toán quy hoạch động là gì ???? Trước khi bắt đầu chúng ta sẽ xem một ví dụ thực tế đơn giản để thấy thuật toán "Quy hoạch động" (Dynamic) hoạt động như thế nào và được ứng dụng làm gì!! 

1. ĐỀ BÀI

Để tiết kiệm tối đa chi phí vận hành và tăng tốc độ giao dich, các ngân hàng muốn thiết kế một thuật toán cho các cây ATM để cây ATM có thể trả được đúng số tiền dựa trên những loại tiền có trong ATM đó, và số tờ tiền rút ra là nhỏ nhất. Ví dụ : Một cây ATM chỉ còn tiền các mệnh giá 20$, 50$ , một khách hàng muốn rút 110$, thì cây ATM sẽ tính toán và trả 1 tờ 50$ và 3 tờ 20$. Nếu khách hàng muốn rút 60$ thì cây ATM sẽ báo không thực hiện được giao dịch. Hãy viết thuật toán thực hiện yêu cầu trên, đầu ra ghi số lượng tờ tiền rút ra, nếu không thể thực hiện giao dịch, in ra -1.


Giới hạn : Số Testcase NT không quá 30, Số loại tiền N không quá 10, Giá trị 1 loại tiền không quá 10000, Số tiền rút ra không quá 1000000.