Ha Hoang's Blog

Khi mới bắt đầu học lập trình Python, các bạn sẽ gặp một số khó khăn ở giai đoạn đầu. Một câu hỏi đầu tiên là "nên sử dụng IDE nào để có thể lập trình Python?". Theo yêu cầu của chương trình Tin học mới 2018 về dạy học phát triển năng lực, các phần mềm sử dụng trong nhà trường để giảng dạy phải là phần mềm miễn phí, mã nguồn mở. Bởi thế, các lựa chọn sẽ ưu tiên đối với các phần mềm mã nguồn mở, tiêu chí phần mềm đơn giản, dễ sử dụng, đủ các chức năng cơ bản là được. 1. IDLE  Để lập trình Python, bạn có thể tải Python về máy của mình từ trang chủ  https://www.python.org/downloads/  sau đó cài đặt. Sau khi cài đặt, bạn có thể dùng luôn IDLE có sẵn của Python để viết chương trình. Phần mềm này cũng dễ dùng và thân thiện, nhỏ gọn lại không cần cài đặt gì thêm. 2. Thonny Thonny là một IDE miễn phí, nhỏ gọn. Việc tải và cài đặt rất nhanh chóng. Bạn có thể sử dụng để viết chương trình luôn mà không cần phải cài Python riêng vì nó đã được tích hợp trong quá trình cài đặt Thonny r...

Loạt bài Quy hoạch động cơ bản mình trình bày ở đây nhằm mục đích định rõ các bước tư duy cụ thể để đưa ra được thuật toán Quy hoạch động cho một bài toán. Sản phẩm của quá trình lập luận, suy nghĩ gồm có: định nghĩa hàm trạng thái mô tả một trạng thái chung của bài toán; một công thức Quy hoạch động thể hiện việc tính toán các trạng thái sau nhờ một vài trạng thái trước đó; một số bài toán cơ sở làm tiền đề cho việc tính các trạng thái sau và một phương án lưu trữ giá trị các trạng thái nhằm mục đích đưa ra kết quả cuối cùng hoặc truy vết tìm một phương án hợp lí. Bài này sẽ bàn về một bài Quy hoạch động điển hình "Dãy con tăng dài nhất" . Có thể bạn đã đọc, thấy bài này ở nhiều nơi rồi, ở bài viết này mình một lần nữa phân tích theo 5 bước cụ thể để các bạn mới học có thể tiếp cận một cách dễ dàng hơn. Tóm tắt bài Dãy con tăng dài nhất (LIQ) : Cho dãy gồm N phần tử a[i] với i từ 1 tới N; Hãy tính độ dài của dãy con tăng đơn điệu dài nhất. Một dãy con tăng đơn điệu là một dã...

Frog2 là một bài tập Quy hoạch động cơ bản dạng dễ . Bài này được nằm trong loạt bài mẫu nhằm giúp các bạn định hướng cách nghĩ để có thể đưa ra một thuật toán Quy hoạch động . Ở đó bao gồm các bước tư duy nhằm định nghĩa một hàm Quy hoạch động (hàm trạng thái), một công thức Quy hoạch động, các bài toán cơ sở, bảng phương án và các lưu ý khi tính bảng phương án. Bài Frog 2 có thể tóm tắt như sau: Có N hòn đá được đánh số từ 1 tới N. Hòn đá thứ i có độ cao h_i. Ban đầu chú ếch ở hòn đá 1. Chú liên tục thực hiện một loạt hành động sau: Nếu chú đang ở hòn đá i, chú có thể nhảy tới các hòn đá i+1, i+2,..., i+K và chi phí cho bước nhảy đó là |H_i - H_j| với j là hòn đá mà chú ếch nhảy tới. Hỏi chi phí tối thiểu để chú ếch nhảy từ hòn đá đầu đến hòn đá thứ N? Nếu đã làm bài Frog 1 rồi thì bạn sẽ nhận thấy ngay Frog 2 là bài khá tương tự bài Frog 1. Như vậy, cách nghĩ và cách phân tích để đưa ra phương án Quy hoạch động cũng tương tự bài Frog 1. Bạn có thể thực hành nghĩ lại theo các chỉ dẫ...

Bài FROG 1 là một bài tập Quy hoạch động cơ bản, nằm trong danh sách các bài tập thuộc kì thi DP Contest tại Atcoder. Hôm nay chúng ta cùng nhau phân tích cách nghĩ để giải bải Frog 1 bằng Quy hoạch động . Mục đích là muốn thực hành lại các bước tư duy thuật toán theo mô hình Quy hoạch động đã được trình bày ở một bài viết trước. Tóm tắt bài FROG 1: Có N hòn đá được đánh số từ 1 tới N. Ban đầu chú ếch ngồi ở hòn đá 1. Tại hòn đá i, chú ếch có thể nhảy tới hòn đá (i+1) hoặc (i+2); và chú sẽ mất chi phí là |h[i]-h[j]| với j là hòn đá đích mà chú ếch nhảy tới. Hãy tìm chi phí tối thiểu để chú ếch có thể nhảy tới hòn đá N? Ở giai đoạn ban đầu làm quen với Quy hoạch động, ta xem xét các bài toán có dấu hiệu giải được bằng phương pháp QHĐ trước để học cách phân tích (tư duy Quy hoạch động), nên tạm thời ta sẽ bỏ qua bước xác định xem bài toán liệu có thể giải được bằng phương pháp QHĐ. Định nghĩa hàm Quy hoạch động: Bài toán yêu cầu tính chi phí tối thiểu để nhảy tới hòn đá N, ta gọi F(n) ...

VSTEPS là một bài tập Quy hoạch động cơ bản , phù hợp cho các bạn luyện tập tư duy ở giai đoạn đầu khi đang làm quen với mô hình thiết kế thuật toán Quy hoạch động.  Như mình đã chia sẻ các bước suy nghĩ để xây dựng thuật toán Quy hoạch động cho một bài toán theo trình tự các bước, dưới đây là vận dụng phương pháp vào bài VSTEPS - SPOJ. Đề bài VSTEPS  được tóm tắt như sau: Một cầu thang N bậc được đánh số từ 1 tới N. Lucky có thể đi lên 1 hoặc 2 bậc. Tuy nhiên một số bậc thang bị hỏng và không thể bước chân lên được. Bậc thang 1 luôn không thủng và là vị trí đứng ban đầu của Lucky. Hỏi có bao nhiêu cách để Lucky leo hết được cầu thang? Định nghĩa hàm Quy hoạch động : bài toán yêu cầu tìm số cách để leo được lên bậc thứ N, như vậy ta gọi F(n) là số cách tới được bậc thang thứ N. Số cách này chỉ phụ thuộc vào N mà thôi. Tìm công thức Quy hoạch động : Ta giả sử đang đứng ở bậc thứ i, khi đó có hai trường hợp: Nếu bậc thứ i bị thủng --> Không có cách nào tới được bậc i đó -...

Theo kinh nghiệm dạy học của cá nhân mình, các chiến lược thiết kế thuật toán là những nội dung nâng cao, là các nội dung khó đối với nhiều giáo viên cũng như học sinh.  Giả sử giai đoạn lập trình cơ bản, các học sinh có khả năng sử dụng ngôn ngữ lập trình nào đó để biểu diễn các thuật toán cơ bản tốt rồi, học sinh có thể vận dụng tư duy để đưa ra thuật toán cho các bài toán cơ bản rồi. Vậy mà khi chuyển qua nội dung các chuyên đề nâng cao là đa số học sinh bị tụt lại 😆 Và trên thực tế, số lượng này không hề nhỏ. Vậy điều gì làm cho nội dung này là một nội dung quá khó, không thể học được với nhiều học sinh? Đối với các học sinh giỏi về Quy hoạch động, chắc là các HS đội tuyển Quốc Gia, Quốc Tế thì họ nghĩ thế nào về chủ đề này? Người ta có thấy chủ đề này "dễ" ngay từ đầu không? Và con đường để họ giỏi về nội dung này là gì? Nếu mình theo con đường đó, mình có giỏi được như họ không? Hihi, câu trả lời tôi nghĩ sẽ rất chung chung, đại khái là đọc sách chuyên đề QHĐ, đại khái...

Việc chấm bài tự động trên các trang chấm bài online rất phổ biến ở nhiều nơi, cả ở nước ngoài cũng như Việt Nam. Nhưng ở khu vực mình dạy học, chấm bài tự động như là một "đặc sản" riêng của lớp chuyên Tin học. Mình nghĩ, việc sử dụng công cụ chấm bài tự động để hỗ trợ giáo viên và học sinh trong dạy và học lập trình rất hữu ích kể cả giai đoạn lập trình cơ bản. Bởi thế, mình đã biên soạn lại các bài tập trong SGK Cánh Diều để có thể chấm tự động, đồng thời đưa lên trang này để các HS có thể sử dụng để thực hành.  Sử dụng hệ thống chấm bài tự động có nhiều lợi ích. Một là, có thể giúp giảm bớt gánh nặng đối với giáo viên trong các giờ thực hành . Giờ thực hành, giáo viên ngoài việc chuẩn bị các nội dung thực hành, giao cho các nhóm học sinh ở từng máy, rồi quan sát, hỗ trợ học sinh ở từng máy, từng bài tập,... rất nhiều việc khiến giáo viên "kiệt sức" ở mỗi giờ thực hành. Mà mỗi giáo viên, một buổi dạy 4, 5 tiết; một tuần 4,5 buổi :( Nếu không dùng công cụ chấm tự...

Theo yêu cầu cần đạt môn Tin học 2018 cho thấy, việc dạy học lập trình chú trọng nhiều tới kĩ năng thực hành. Ngay từ những bài đầu tiên học sinh đã có được trải nghiệm viết được một vài chương trình đơn giản hoàn chỉnh. Bởi thế, thời lượng dành cho các hoạt động thực hành trên máy là rất nhiều.  Việc dạy học phần thực hành khiến giáo viên rất vất vả. Có lẽ, hiệu quả dạy học lập trình đa số không đạt như kì vọng là do tổ chức thực hành chưa được tốt. Hoạt động học tập trong các giờ thực hành đòi hỏi học sinh làm việc thực sự theo nhóm nhỏ (tối đa 02 học sinh/ máy tính), rất cục bộ. Trong giờ thực hành giai đoạn đầu học lập trình, phần nặng nhất đối với giáo viên lại không nằm ở nội dung thực hành mà ở các hoạt động quan sát, hỗ trợ kịp thời các nhóm học sinh gặp vướng mắc. Thường giáo viên chỉ đủ thời gian hỗ trợ một vài nhóm nhỏ. Không có thời gian xem xét, giúp đỡ các nhóm khác là nguyên nhân chính gây ra việc học sinh rơi vào trạng thái "bơ vơ", không biết làm thế nào tiếp...

CHIA - Chia hết Tiền gửi ngân hàng  http://laptrinh.ntu.edu.vn/Problem/Details/2244 Khuyến mãi bia  USCLN - Ước số chung lớn nhất HOHA - Số hoàn hảo ALBO - Alice và Bob NGTO - Số nguyên tố AMPHO - Âm phổ BINAS - Liệt kê chuỗi nhị phân HIPHA - Hình phạ t

Đây là dịch sơ bài Uva 10360 Rat Attack trên Uva Link gốc và test:  Uva 10360 (Rat Attack) https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1301 Dịch Uva 10360 Rat Attack Cho ma trận 2 chiều có kích thước có thể lên đến 1025x1025 chứa các chú chuột ở nút giao hàng, cột. Có khoảng N (~2000) con chuột ở các ô trên đó, hãy xác định ô nào (x,y) mà nếu đặt bom có bán kính sát thương d (<=50) thì có thể tiêu diệt được nhiều chuột nhất? Input: - Dòng đầu là số lượng test - Mỗi test chứa:    + số d: bán kính sát thương của quả bom    + số N: số lượng nhóm chuột    + N dòng kế tiếp, mỗi dòng gồm 3 số: x, y, và số lượng chuột trong nhóm (x,y) Output: với mỗi test, đưa ra ba số, x,y là vị trí đặt bom và G là số lượng chuột lớn nhất bị tiêu diệt, các số cách nhau ít nhất một dấu cách. Ví dụ: Input: 1 1 2 4 4 10 6 6 20 Output: 5 5 30 Uva 10360 Solution C1: Duyệt C2: Quy hoạch động

Đây là lời dịch sơ bài Uva 725 Division trên Uva Link đề gốc và test:  Uva 725 (Divisons) https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=666 Uva 725 Division Cho hai số có 5 chữ số abcde và fghij với mỗi kí tự là khác nhau trong khoảng 0..9 và một số nguyên dương N trong khoảng 2..79. Yêu cầu: tìm ra hai số đó thỏa mãn phép chia abcde/fghij=N Gợi ý bài Uva 725 Division: Duyệt các giá trị có thể có của fghij (trong khoảng 01234 đến 98765), với mỗi fghij ta tính được abcde=N*fghij; tiến hành kiểm tra abcde thỏa mãn các số khác nhau và khác các số trong fghij.

Luyện tập trên NTU Coder . Tham khảo lý thuyết: cuốn Kỹ thuật thiết kế thuật toán của Lê Minh Hoàng . Bài tập: Hiệu số Dãy con tăng dài nhất

QBTICKET - Mua vé tàu hoả Tuyến đường sắt từ thành phố A đến thành phố B đi qua một số nhà ga. Tuyến đường có thể biểu diễn bởi một đoạn thẳng, các nhà ga là các điểm trên đó. Tuyến đường bắt đầu từ A và kết thúc ở B, vì thế các nhà ga sẽ được đánh số bắt đầu từ A (có số hiệu là 1) và B là nhà ga cuối cùng. Giá vé đi lại giữa hai nhà ga chỉ phụ thuộc vào khoảng cách giữa chúng. Cách tính giá vé như sau: Khoảng cách giữa hai nhà ga (X) Khoảng cách 0 < X <= L1 -> Giá vé C1 Khoảng cách 0 < X <= L2 -> Giá vé C2 Khoảng cách 0 < X <= L3 -> Giá vé C3 Nghĩa là với các giá vé C1, C2, C3 tương ứng bạn sẽ đi quảng đường tối đa là L1, L2, L3. Vé để đi thẳng từ nhà ga này đến nhà ga khác chỉ có thể đặt mua nếu khoảng cách giữa chúng không vượt quá L3. Vì thế nhiều khi để đi từ nhà ga này đến nhà ga khác ta phải đặt mua một số vé. Hơn thế nữa, nhân viên đường sắt yêu cầu hành khách chỉ được giữ đúng một vé khi đi trên tàu và vé đó sẽ bị huỷ khi hành k...

PNUMBERS HSPC14J MPRIME

Bài tập áp dụng kỹ thuật tham lam, mức độ dễ. ATM Tìm số Vắt sữa bò Cắm điện Khiêu vũ Giao đấu (OLP 2014) Đổ xăng Thu hoạch táo Nối chuỗi xích Lì xì Phân nhóm (Jakarta 2014 - A) Thang máy (Codeforces) Tặng hoa 20/11

Đây là một trong những kĩ thuật cơ bản, tương đối đơn giản và dễ hiểu. Tài liệu ở đây: Kĩ thuật quay lui Kĩ thuật quay lui Danh sách bài tập luyện tập: Liệt kê chuỗi nhị phân Liệt kê chuỗi hoán vị Liệt kê chuỗi k-phân Trò chơi Line Dãy ngoặc đúng Cái túi Ốc sên ăn rau Tám hậu Hái nấm

DANH SÁCH BÀI TẬP THỨ 7 (16/01/2015) S ố hoàn hảo 2 Chồng gạch Tổng nguyên tố Nguyên tố - nguyên tố cùng nhau

Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể. Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể. Bài toán tổng quát : ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó. Cách giải quyết : Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất. Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuậ...

Mọi số tự nhiên đều có thể biểu diễn được dưới dạng nhị phân. Đối với máy tính, các giá trị số được lưu bởi các biến dưới dạng chuỗi nhị phân có độ dài tương ứng với kiểu biến đó.     Trong ngôn ngữ Pascal, một số kiểu phổ biến như:         –     byte  : độ dài 8 BIT         –     integer  : độ dài 2*8 = 16 BIT         –     longint  : độ dài 4*8 = 32 BIT     Các BIT của biến được đánh số từ phải sang trái bắt đầu từ 1.      Ưu điểm của xử lý BIT:      1/ Bộ nhớ:  Xử lý BIT có thể được dùng làm mảng đánh dấu. Thay vì sử dụng 1 biến Boolean chỉ đánh dấu được 1 phần tử là True hay False, ta có thể xử lý BIT để đánh dấu 8 BIT tương ứng với 8 phần tử.      2/ Tốc độ:  Các phép xử lý BIT có tốc độ nhanh hơn các phép xử lý khác....