Tuesday, March 15, 2016

[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.

Thursday, March 3, 2016

[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.

Saturday, February 6, 2016

[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.

Sunday, February 1, 2015

Ma trận phím và thiết kế cải tiến

Ma trận phím thường được sử dụng khi chúng ta muốn sử dụng số lượng lớn phím bấm cũng như các loại công tắc,cảm biến 2 trạng thái.Quét ma trận phím về nguyên lý thực ra không khó,tuy nhiên trong các thiết kế ma trận phím thông thường có một nhược điểm là chỉ cho phép bấm 1 nút tại một thời điểm,nếu không sẽ đọc sai kết quả.Bài này mình sẽ giới thiệu về ma trận phím,cách quét và thiết kế của ma trận kiểu mới.

1.Ma trận phím và cách đọc ma trận phím

Ma trận phím có nhiều kích thước,ở đây mình giới thiệu ma trận kích thước 2x2,được bố trí theo dạng 2 hàng 2 cột.Cũng giống như ma trận LED, các nút nhấn ở cùng hàng và cột được nối với nhau,vì thế như ma trận phím bên dưới có 4 ngõ ra (2 hàng , 2 cột).

Thursday, January 29, 2015

Tính toán cơ bản trong lập trình nhúng

Trong bài này mình sẽ giới thiệu hầu hết các thuật toán cơ bản nhất trong lập trình C (nhúng) mà mình biết,hầu hết là các thuật toán xử lý BIT,thanh ghi.Các thuật toán này hết sức cơ bản,nhiều bạn đã thành thạo rồi,tuy nhiên nó rất quan trọng và được sử dụng thường xuyên,nhưng lại thường bị mọi người bỏ qua.
Mình sẽ lấy ví dụ luôn với các thanh ghi trong module Digital I/O của MSP430 để các bạn tiện hình dung.

1.Các phép toán thông dụng

Mình chỉ nêu ra các phép toán rất hay dùng trong lập trình nhúng,các bạn tự tìm hiểu ý nghĩa vì nó rất cơ bản:
& , | , ^ , ! , ~ , << , >> , != , && , || , ++ , -- , (biểu thức điều kiện) a ? b : c , (viết tắt) ví dụ ^= ; |= 
END COMMENT FACEBOOK-->