Một gợi ý để tìm hướng đến lời giải

MỘT SỐ GỢI Ý ĐỂ TÌM HƯỚNG ĐI ĐẾN LỜI GIẢI

Gợi ý 1. Lấy nhiều ví dụ và tự giải các ví dụ đó, qua đó
- Hiểu rõ bài toán hơn
- Hình dung quá trình tính toán ra kết quả
- Tìm được quy luật của kết quả với từng input tương ứng
- Quan sát những mỗi quan hệ giữa giả thuyết và kết luận

Gợi ý 2. Thay vì lấy các ví dụ cụ thể, chúng ta thử dùng các ký hiệu như bài toán mô tả
Qua đó có thể gợi ý cho chúng ta các mối quan hệ mà đôi khi nếu thế các số cụ thể chúng ta không thấy được.

Gợi ý 3. Vẽ hình những giả thuyết bài toán cho
Thay vì nhìn các con số, các ký hiệu, chúng ta thử vẽ các hình mà bài toán cho, rồi sau đó thử giải bằng hình ảnh đã vẽ. Từ đó có thể gợi ý cho chúng ta cách giải quyết bài toán.

Phương pháp tìm số

PHƯƠNG PHÁP TÌM SỐ

Bài toán: Cho các ràng buộc A, B, C, ... hãy tìm một số x thỏa các ràng buộc đã cho

Có hai phương pháp cơ bản để giải quyết bài toán trên.
- Phương pháp thứ nhất là xét từng số x, rồi kiểm tra có thỏa điều kiện A, B, C, ... không, hay cũng có thể chọn 1 điều kiện A làm chuẩn để giới hạn miền x rồi mới quét x để kiểm tra xem x có thỏa điều kiện B, C, ... không
- Phương pháp thứ hai làm xem x gồm có n chữ số: x=x1, x2,...,xn. Rồi tìm từng chữ số một x1, rồi x2, ... cuối cùng là xn. Hẫy cũng có thể tìm x1, rồi tìm x1x2, rồi x1x2x3, ... rồi cuối cùng là x1x2...xn

Tóm tắt hai phương pháp:
Phương pháp 1: xét miền giá trị của x
- Chọn điều kiện A để tìm các số có thể của x thỏa điều kiện A
- Xét các số x thỏa điều kiện A và kiểm tra xem có thỏa điều kiện B, C, ... không

Phương pháp 2: tìm từng chữ số của x
- Xem x=x1,x2, ..., xn
- Xét x1 có bao nhiêu khả năng, chọn những x1 nào thỏa điều kiện A, B, C, ...
- Xét x1x2 có bao nhiêu khả năng, chọn x1x2 nào thỏa điều kiện A, B, C, ...
...
Cho đến khi tìm được giá trị x cần tìm

Quản lý thời gian

QUẢN LÝ THỜI GIAN

Bước 1. Xác định các mục đích cuộc sống
- Phát triển bản thân:
  + Chuyên môn, Quản lý
  + Tư duy: tư duy logic, phương pháp học tập
  + Tĩnh tâm
  + Sức khỏe
- Gia đình: dạy con, chăm sóc gia đình
- Công việc

Bước 2. Xác định các nhiệm vụ quan trọng
- Số lượng: khoảng 2-3 nhiệm vụ
- Tiêu chuẩn của nhiệm vụ: theo tiêu chuẩn SMART:
  + Cụ thể
  + Đo lường được
  + Có thể đạt được
  + Thích đáng với hoàn cảnh cụ thể
  + Có thời hạn cụ thể

Bước 3. Lên lịch hoạt động tuần
- Gán nhiệm vụ với thời gian cụ thể trong tuần

Bước 4.
... còn tiếp

Tìm kiếm nhị phân và ứng dụng

TÌM KIẾM NHỊ PHÂN

Bài toán 1. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí trong dãy a có giá trị bằng x.
Thuật toán: binary_search(a.begin(), a.end(), x)



Bài toán 2. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí nhỏ nhất trong dãy a có giá trị lớn hơn hay bằng x.
Thuật toán: lower_bound(a.begin(), a.end(), x)


Bài toán 3. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí nhỏ nhất trong dãy a có giá trị lớn hơn x.
Thuật toán: upper_bound(a.begin(), a.end(), x)


Ứng dụng của lower_bound và upper_bound
1. Tìm đoạn phần tử giá trị bằng x
vector<int>::interator l, r;
int left, right;

l = lower_bound(a.begin(), a.end(), x);
r = upper_bound(a.begin(), a.end(), x);

left = l-x.begin();
right = r-x.begin()-1;

2. Đếm số lượng phần tử nhỏ hơn x
left = lower_bound(a.begin(), a.end(), x);
nums= left-a.begin()-1;

2. Đếm số lượng phần tử lớn hơn x
right = lower_bound(a.begin(), a.end(), x);
nums= a.end()-right;

Quản lý là gì?

QUẢN LÝ LÀ GÌ?

Người làm quản lý là người có nhiệm vụ:

1. Xác định mục tiêu
2. Cung cấp, tổ chức các nguồn lực
3. Khích lệ nhân viên
4. Giám sát các kết quả
5. Cải thiên hiệu quả làm việc

Cụ thể như sau:
- Xác định mục tiêu: xác định mục tiêu của tổ chức, của đơn vị, của nhóm làm việc, của mọi nhân viên của mình.
- Cung cấp, tổ chức các nguồn lực: cung cấp, tổ chức các nguồn lực để thực hiện được các mục tiêu
- Khích lệ nhân viên: trao đổi và khích lệ để nhân viên hoàn thành các mục tiêu đặt ra
- Giám sát các kết quả: giám sát các kết quả làm việc của nhân viên so với mục tiêu đã đặt ra
- Cải thiên hiệu quả làm việc: cải thiện hiệu quả làm việc bằng cách phát triển năng lực bản thân và năng lực của nhân viên

Mỗi nhiệm vụ của người quản lý đề ra ở trên cần phải được thực hiện hiệu quả. Để thực hiện hiệu quả nhiệm vụ của người quản lý, chúng ta cần tìm hiểu các lý thuyết liên quan đến từng nhiệm vụ trong các công trình nghiên cứu.

Lý do chia sẽ kiến thức

LÝ DO CHIA SẼ KIẾN THỨC

Tại sao chúng ta nên chia sẽ những gì chúng ta biết?

Lý do người ta chia sẽ kiến thức và nên chia sẽ kiến thức là:
1. Để giúp đỡ những người cần có kiến thức đó
Giúp đỡ mọi người có thể xuất phát từ:
- Những khó khăn mà mình đã gặp phải, nhưng không tìm được ai, tài liệu nào để hỗ trợ cho chúng ta. Nên chúng ta chia sẽ chỉ đơn giản là để giúp đỡ những ai  gặp phải những khó khăn như chúng ta đã gặp.
- Xuất phát từ tâm lý cá nhân là cảm thấy mình có giá trị khi khi mình có thể giúp đỡ được ai đó.

2. Chia sẽ kiến thức là một phương pháp học hiệu quả:
Chúng ta học lần thứ nhất khi chúng ta giải quyết vấn đề. Khi chúng ta giải quyết vấn đề chúng ta sẽ phân tích vấn đề, rồi chọn mô hình đã biết để giải quyết khó khăn trước mắt. Khi không giải quyết được chúng ta chọn lại mô hình khác, hay dựa trên những logic phân tích được chúng ta tinh chỉnh lại phương pháp đã có để giải quyết vấn đề. Qua việc giải quyết vấn đề như vậy chúng ta sẽ học cách phân tích đề, học cách chọn mô hình, học cách tinh chỉnh mô hình, nhưng mục tiêu cuối cùng chúng ta nhắm tời là giải cho được vấn đề đang gặp, còn quá trình đi đến lời giải vấn đề có mức đô ưu tiên thấp hơn.

Chúng ta học lần thứ hai khi chúng ta có thời gian suy ngẫm lại vấn đề đã giải quyết. Khi chúng ta chia sẽ kiến thức (như viết blog, viết sách, giảng dạy, ...) đó là cơ hội tuyệt vời để chúng ta suy ngẫm lại. Bằng phương tiện chia sẽ, chúng ta sẽ:
  + Suy ngẫm, nghiền ngẫm lại những điều đã biết
  + Nhìn nhận lại quá trình suy nghĩ, và đặt ra những câu hỏi như: vấn đề cốt lõi ở đây là gì? Tại sao đi theo con đường đó thì giải quyết vấn đề? Tạo sao chúng ta bị chi phối làm đi lạc khỏi lời giải của vấn đề, ...
  + Liên kết những ý tưởng khác lại với nhau
  + Sắp xếp lại ý tưởng cho rành mạch

Như vậy, việc chia sẽ kiến thức vừa là cơ hội để giúp đỡ người khác, vừa là cơ hội để nghiền ngẫm, học tập để thấu hiểu vấn đề hơn.

Cách tiếp cận kiến thức mới

CÁCH TIẾP CẬN KIẾN THỨC MỚI

Kiến thức mới có thể ví như là vùng đất mới mà lần đầu tiên chúng ta tiếp cận, khám phá. Cho nên khi học một kiến thức mới chúng ta sẽ lúng túng, vụng về là chuyện thường tình. Tuy nhiên chúng ta có thể tiếp cần kiến thức dễ dàng hơn, dễ ghi nhớ hơn nếu chúng ta có phương pháp tiếp cận hiệu quả. Phương pháp sau là một gợi ý để chúng ta có thể tiếp cận kiến thức mới một cách nhanh chóng

Bước 1. Bài toán / Vấn đề:
Phát biểu ngắn gọn bài toán/vấn đề muốn giải quyết

Bước 2. Nêu hiệu quả của kiến thức/phương pháp mới để giải quyết bài toán trên

Bước 3. Biểu diễn
Nêu định nghĩa/khái niệm cốt lõi của phương pháp

Bước 4. Các phép toán
Nêu các phép toán/thao tác của phương pháp cung cấp

Lý do nên tham gia các kỳ thi lập trình

LÝ DO NÊN THAM GIA CÁC KỲ THI LẬP TRÌNH

Mục đích của thi lập trình: 
Mục đích của thi lập trình (competitive programming) là viết chương trình máy tính để giải quyết các vấn đề liên quan đến logic và toán học. Các bài toán cần giải quyết nằm trong phạm vi: tổ hợp, lý thuyết số, lý thuyết đồ thị, hình học, phân tích chuỗi và các cấu trúc dữ liệu [1].

Tiến trình giải quyết vấn đề: 
Giải quyết vấn đề bằng lập trình thường gồm 4 bước chính:
(1) đọc hiểu rõ chi tiết vấn đề
(2) thiết kế thuật toán hiệu quả
(3) cài đặt thuật toán bằng ngôn ngữ cụ thể
(4) kiểm thử, debug chương trình kỹ càng

Lợi ích của việc tham gia thi lập trình:
Qua đó chúng ta thấy khi tham gia thi lập trình sẽ giúp chúng ta:
1. Kiến thức: chúng ta sẽ có đầy đủ kiến thức cơ bản về phương pháp giải quyết vấn đề bằng lập trình như: cấu trúc dữ liệu, thuật toán, phương pháp thiết kế thuật toán
2. Kỹ năng: chúng ta sẽ có kỹ năng đọc đề, kỹ năng phân tích logic, kỹ năng sử dụng các kỹ thức uyển chuyển, kỹ năng thiết kế thuật toán, kỹ năng sử dụng ngôn ngữ lập trình, kỹ năng debug, kỹ năng code các ý thành các chương trình
3. Thái độ: 
- Tự tin: vì đã có đầy đủ kiến thức cơ bản, kỹ năng sử dụng các kiến thức cơ bản một cách uyển chuyển, linh hoạt
- Khiêm tốn: bên cạnh sự tự tin về những gì mình có, chúng ta cũng sẽ có thái độ khiêm tốn vì có nhiều vấn đề không phải lúc nào chúng ta cũng giải quyết được, cần phải có thời gian, phương pháp tiếp cận phù hợp.
- Chú ý chi tiết, kỹ càng: trước khi thiết kế ra thuật toán hiệu quả, chúng ta cần tận dụng từng ràng buộc của bài toán (chú ý chi tiết từng ràng buộc của bài toán), nhìn nhận các kiến thức ở nhiều góc nhìn khác nhau (các kiến thức được xem xét kỹ càng).
- Điềm tĩnh: Qua giải quyết các vấn đề khó, chúng ta sẽ được tôi luyện thái độ điềm tĩnh trong suy nghĩ, bình tĩnh phân tích từng nội dung của vấn đề.
4. Cơ hội: khi đã có kiến thức, kỹ năng giỏi, chúng ta mới có cơ hội để giúp đỡ, chia sẽ các kiến thức kỹ năng với những người cần giúp đỡ.

Tài liệu tham khảo
[1]. https://en.wikipedia.org/wiki/Competitive_programming

Chiến lược thi ACM/ICPC

CHIẾN LƯỢC THI ACM/ICPC

Vai trò thành viên trong nhóm: 

1. Vai trò Người đọc đề (A): Chuyên đọc đề và giải thích đề
2. Vai trò Người lập trình (B): Tập trung code
3. Vai trò Người giám sát (C): Quan sát người B code và phát hiện lỗi để báo ngay

1. Bắt đầu nhận đề thi

Lúc đầu:

- Cả 3 thành viên đều đóng vai trò người đọc đề: đọc lướt qua các đề bài để xác định đề bài dễ nhất. 

- Theo dõi bảng scoreboard để xác định bài dễ nhất (được nhiều nhóm giải được nhất)

Sau khi đã xác nhận bài dễ nhất: 

  + Hai người sẽ đóng vai B, C: Tập trung đọc kỹ đề và giải quyết bài toán đó

  + Người thứ ba đóng vai trò Người đọc đề: Tìm đề bài dễ tiếp theo, đọc hiểu kỹ để giải thích lại cho hai người còn lại sau này.

2. Giải quyết bài toán

Bước 1. Đọc đề và tìm thuật toán: Cả B và C:

  + Cùng đọc hiểu kỹ bài toàn

  + Lấy nhiều ví dụ và cùng giải thử

  + Một người đưa ra ý tưởng giải, một người lắng nghe và nhận xét, xác định đúng không, và bổ sung khi cần

  + Đưa ra các bước giải cụ thể

  + Xác định các hàm cần viết

  + Viết ra giấy các bước 

  + Viết ra giấy tên các hàm cần cài đặt

Bước 2. Cài đặt chương trình

  + Một người đóng vai trò viết code

  + Một người đóng vai trò quan sát, phát hiện sai sót

  + Nếu đang cài đặt mà người viết code bị  bí thì hai người đổi vai trò cho nhau

Bước 3. Test và Debug

  + Chạy các test case

  + Debug các lỗi

Bước 4. Submit bài

  + Bỏ các dòng lệnh debug

  + Submit bài

3. Qua bài mới

Sau khi giải quyết thành công một bài thì qua bài dễ kế tiếp

- Người A trình bày nội dung bài toán

- Nguời B, C đọc lại đề lần nữa để xác định nội dung giải thích và tiến hành giải quyết bài toán

- Người A tìm bài dễ tiếp theo để đọc hiểu đề

Khó khăn và giải pháp đọc hiểu một bài toán tin học

NHỮNG KHÓ KHĂN KHI ĐỌC HIỂU MỘT BÀI TOÁN TIN HỌC

Khi đọc một bài toán tin học, chúng ta thường có những cảm nhận tâm lý ban đầu có thể gây cản chở cho chúng ta đọc hiểu bài toán. Một trong những cảm nhận thông thường khi chúng ta nhìn qua đề bài như sau:

1. Đề bài quá dài
- Điều này sẽ làm cho chúng ta ngại đọc vì sợ mất nhiều thời gian đọc đề
- Bài có nhiều sự kiện nên chúng ta ngại vì khó nhớ hết các sự kiện trong bài


2. Miền giá trị của biến quá lớn
- Làm cho chúng ta cảm nhận bài toán chắc sẽ khó


Một số gợi ý sau giúp chúng ta giải tỏa được phần nào tâm lý trên
1. Đề bài quá dài
- Đọc đến đâu nên ghi chú lại những thông tin quan trọng cần nhớ.
- Tóm tắt ý từng đoạn muốn nói gì, diễn đạt lại theo ý mình
- Dùng ký hiệu toán để mô tả bài toán: ví dụ như đặt tên biến, sử dụng các phép toán, biểu diễn các ràng buộc bài toán bằng các phương trình, các bất phương trình. Cách làm này sẽ bỏ đi các "râu ria" của bài toán và sẽ giúp ta đi vào bản chất yêu cầu của bài toán.


2. Miền giá trị của biến quá lớn
- Hãy xem đây là thông tin hướng dẫn cách chúng ta tìm ra thuật toán, nghĩa là nếu làm theo cách thông thường thì sẽ bị vướng về số lớn.
- Đề bài gợi chúng ta nên suy nghĩ theo hướng xử lý khác, như:
  + Thay vì xử cả số, thì chúng ta xử lý từng vị trí chữ số,
  + Tìm mẫu kết quả trong các ví dụ
  + Duyệt một lần (tìm kiếm tuyến tính)
  + Tìm kiếm nhị phân
  + Tìm bất phương trình, tìm điều kiện để dấu bằng xảy ra trong bất phương trình
  + Tìm công thức toán tổ hợp (tránh vòng lặp)
  + Tìm min của nghiệm, tìm max của nghiệm, cho nghiệm bằng max rồi từ từ tối ưu cho nhỏ lại
...

Quy trình giải quyết một bài toán tin học

QUY TRÌNH GIẢI QUYẾT MỘT BÀI TOÁN TIN HỌC

Quy trình giải một bài toán tin học
Giải quyết một bài toán tin học thường được tiến hành theo các bước sau:

1. Đọc hiểu bài toán
2. Thiết kế thuật toán
3. Viết chương trình
4. Kiểm tra chương trình
5. Rà soát lại trước khi submit bài

1. Đọc hiểu bài toán
Giai đoạn đầu tiên là cần phải hiểu đúng yêu cầu bài toán. Chỉ cần hiểu sai, hiểu lầm một khái niệm trong bài toán có thể dẫn đến lời giải hoàn toàn sai. Đã hiểu sai bài toán rồi thì dù chúng ta bỏ công sức thiết kế thuật toán tối ưu cở nào, cẩn thận code từng dòng lệnh ra sao thì công sức ấy cũng là công "giã tràng xe cát biển đông"!

Ví dụ: Đề cho đường thẳng đi qua 2 điểm, nhưng khi đọc vì quá chú tâm đến 2 điểm nên có thể chúng ta lại nghĩ là đoạn thẳng.

Cho nên chúng ta nên cẩn trọng khi đọc đề bài toán. Giành thời gian để đọc hiểu từng đoạn văn yêu cần của bài toán. Cần suy ngẫm từ từ cho đến khi hiểu rõ các ngõ ngách của đề bài.

Một số bước để đọc hiểu đề bài toán có thể tóm tắt như sau:

1. Đọc từng câu, từng đoạn, để hiểu cơ bản bài toán
2. Đọc input và output của bài toán
3. Đọc lại từng câu, từng đoạn, hiểu rõ từng câu, từng đoạn của bài toán
4. Đọc input và output của bài toán, chú ý kích thước dữ liệu của bài toán
5. Giải các ví dụ trong đề bài để hiểu rõ thêm bài toán
6. Lấy thêm các ví dụ để hiểu rõ thêm bài toán

- Nếu vẫn chưa hiểu bài toán, thì đọc đi đọc lại để tìm những chổ chưa hiểu. Nếu vẫn chưa hiểu bài toán thì nên nghĩ ngơi một chút, rồi sau đó cứ đọc đi đọc lại cho đến khi nào hiểu bài toán.

Bài toán cần đọc lại nhiều lần để:
(1) Cảm giác thân thuộc với bài toán
(2) Mỗi lần đọc là một lần nghĩ khác đi một chút bài toán
(3) Phát hiện ra một số điều trước đây chưa nhìn ra


Tóm lại, đọc đề bài toán cần hết sức cẩn trọng, chưa hiểu đề, hiểu đề lơ mờ thì nhất quyết không giải bài toán đó.

2. Thiết kết thuật toán

Để thiết kế ra được thuật toán giải quyết bài toán, chúng ta cần phải tự mình giải trước các ví dụ của bài toán. Trong quá trình tự giải quyết các ví dụ, chúng ta sẽ dần dần hình thành hướng giải quyết bài toán. Từ đó đưa ra quy tắc từng bước giải quyết bài toán. Sau đó chúng ta cần kiểm nghiệm quy tắc này bằng cách áp dụng quy tắc đưa ra xem có thể giải các ví dụ được không.

Như vậy, chúng ta có thể đưa ra một số bước gợi ý để tìm lời giải của bài toán

1. Lấy từng ví dụ, từ nhỏ đến lớn. Giải các ví dụ bài toán theo như cách bài toán muốn định hướng chúng ta làm (không quan tâm có hiệu quả hay không mà chỉ quan tâm giải được)
2. Quan sát các nghiệm của bài toán: Bằng cách quan sát các nghiệm của bài toán, chúng ta có thể phát hiện ra quy luật của nghiệm, từ đó dẫn đến lời giải bài toán
3. Quan sát quá trình tự giải bài toán, có thể hình thành nên bộ quy tắc từng bước để giải bài toán
4. Tối ưu bộ quy tắc để có thể giải nhanh hơn
5. Thử sắp xếp dữ liệu xem có lợi thế gì không
6. Chú ý kích thước dữ liệu của bài toán để từ đó tinh chỉnh quy tắc giải bài toán
7. Thử phân loại bài toán này thuộc dạng phương pháp nào: chia để trị, tham lam, quy hoạch động, vét, sắp xếp, tìm kiếm nhị phân, tìm kiếm 2 con trỏ, tìm kiếm tam phân, BFS, Lý thuyết đồ thị, ...

Tài liệu tham khảo giá trị

CÁC TÀI LIỆU THAM KHẢO GIÁ TRỊ

Những cuốn sách về phương pháp học

1. Peter Hollins, "Learn Like Einstein: Memorize More, Read Faster, Focus Better, and Master Anything With Ease… Become An Expert in Record Time (Accelerated Learning)", 2017
2. Benedict Carey, "How We Learn: The Surprising Truth About When, Where, and Why It Happens", 2015

Những cuốn sách về tâm trí

1. Buddhism (Đạo Phật)
2. Epictetus, "Art of Living", 2013 (Nghệ thuật sống)
3. Lao Tzu, "Tao" (Đạo đức kinh của Lão Tử)
4. Viktor E. Frankl, "Man's Search for Meaning", 2006 (Đi tìm lẽ sống)
5. Stephen R. Covey, "The 8th Habit: From Effectiveness to Greatness", 2005
6. Michael A. Singer, "The Untethered Soul, The Journey Beyond Yourself", 2007 (Cởi trói linh hồn)
7. Don Miguel Ruiz, "The Four Agreements, A Practical Guide to Personal Freedom", 1997 (Bốn thỏa ước)

Đức phật

Epictetus

Lão Tử

Viktor E. Frankl

Michael A. Singer

Stephen R. Covey

Don Miguel Ruiz

Sàng nguyên tố trong thời gian tuyến tính

SÀNG NGUYÊN TỐ TUYẾN TÍNH

Cấu trúc dữ liệu int uocso[...]
Lúc đầu cho uocso[i] = 0 với uy ước uocso[i] = 0 thì i là số nguyên tố.
Sau đó:
- Nếu uocso[i] = 0 tức là i là số nguyên tố ta gán uocso[i] = i, nghĩa là i là số nguyên tố nên ước số của i là số i
- Nếu uocso[i] = k thì ước số nguyên tố nhỏ nhất của i là k

Nhận xét: sau khi chạy xong thuật toán thì có thể dùng mảng uocso[] theo 2 cách:
Cách 1: Dùng để kiểm tra số nguyên i có là số nguyên tố không: nếu uocso[i]=i thì i là số nguyên tố
Cách 2: Dùng để biết số nguyên tố nhỏ nhất của hợp số i là bao nhiêu, từ đó dùng để phân tích nhanh số nguyên i ra thành các thừa số nguyên tố

Cấu trúc dữ liệu vector<int> primes
primes dùng để chứa các số nguyên tố

Thuật toán: 
Xét từng số i từ 2 đến N
  - Nếu i là số nguyên tố thì: thêm i vào primes và cho uocso[i]=i
  - Xét các số nguyên tố đã lưu trong mảng primes và số nguyên tố này nhỏ hơn hay bằng ước số nguyên tổ nhỏ nhất của số i (tức là số nguyên tố lưu trong uocso[i]):
     + Bỏ đi các bội i là i*primes[j] hay ghi nhận uocso[i*primes[j]] là primes[j]



Chương trình:
const int N = 32000000
vector<int> primes;
int uocso[N];

void Sang() {
  for (int i=2; i<=N; i++) {
    if (uocso[i] == 0) {
      uocso[i] = i;
      primes.push_back(i);
    }

    for (int j=0; j<primes.size() && 
                  primes[j]<=uocso[i] && 
                  i*primes[j]<=N; j++)
      uocso[i*primes[j]] = primes[j];
  }
}

Vòng lặp kép học tập

VÒNG LẶP KÉP CỦA HỌC TẬP

Tác giả: hai nhà tâm lý học người Mỹ Chris Argyris và Donald Schön

Năm: 1974

Nội dung:

Nguồn: https://doublelooplearning.co.uk/about/ 

Phương pháp vòng lặp đơn: là khi chúng ta cố gắng khắc phục vấn đề bằng cách tìm ra phương thức hành động khác, trong khi các giá trị, mục tiêu, kế hoạch hay quy tắc… vẫn giữ nguyên.

Phương pháp vòng lặp kép: là khi chúng ta tìm ra nguyên nhân thực sự đằng sau vấn đề, có thể nghi ngờ, đặt câu hỏi và thay đổi các giá trị, mục tiêu, kế hoạch hay nguyên tắc…

Điều này có nghĩa là thay vì chỉ cố gắng sửa đổi hành động để đạt được mục tiêu như trong phương pháp vòng lặp đơn, chúng ta nghiên cứu, tìm ra nguyên nhân cốt lõi phát sinh vấn đề và khắc phục từ đó. Với tổ chức, đó có thể là các chính sách, quy chuẩn; với cá nhân, nó có thể là các giả định, động cơ mà chúng ta dựa trên nó để đưa ra các kế hoạch, mục tiêu.

Phương pháp vòng lặp kép đòi hỏi chủ thể phải có khả năng:

• Tự nhận thức bản thân để biết được đâu thực sự là nguyên nhân bởi sai lầm thường nằm trong chủ thể
• Dũng cảm chấp nhận sai lầm
• Hành động hợp lý để sửa đổi

Tài liệu tham khảo:

- Argyris, M. and Schön, D. (1974) Theory in Practice. Increasing professional effectiveness, San Francisco: Jossey-Bass. Landmark statement of 'double-loop' learning' and distinction between

espoused theory and theory-in-action.

- Argyris, C. and Schon, D. A. (1978) Organizational Learning: A theory of action perspective. Reading, MA: Addison Wesley.

Tiếp cận ngôn ngữ lập trình mới

TIẾP CẬN NGÔN NGỮ LẬP TRÌNH NHƯ THẾ NÀO?

Khi dự định học một ngôn ngữ lập trình mới, chúng ta thường cảm thấy choáng ngợp vì sự lạ lẫm, đồ sộ, phức tạp của ngôn ngữ mới. Chính vì vậy, chúng ta cần suy nghĩ về phương pháp tiếp cận ngôn ngữ để việc học ngôn ngữ mới diễn ra tự nhiên và nhanh chóng.

Khi học một ngôn ngữ lập trình mới, chúng ta có thể từng bước tìm hiểu các thành phần cơ bản của ngôn ngữ như sau:
- Học cách khai báo một số kiểu cơ bản: số nguyên, số thực, ký tự, chuỗi, mảng một chiều, mảng hai chiều (hay nhiều chiều hơn)
- Xem qua các phép toán trên số: +, -, x, :, chia lấy dư (mod)
- Tìm hiểu 3 loại lệnh: lệnh gán, lệnh điều kiện, lệnh lặp
- Các thao tác trên mảng một chiều, hai chiều
- Sử dụng các hàm cơ bản trên chuỗi: sao chép chuỗi con, xóa chuỗi con, chèn chuỗi con, ...
- Cách viết hàm
- Viết thử các thuật toán cơ bản: như sắp xếp, tìm kiếm, ...

Sau khi đã tìm hiểu và thực hành các nội dung trên, chúng ta có thể tự tin cho rằng mình đã nắm được nội dung cơ bản của ngôn ngữ mới và có thể sử dụng ngôn ngữ mới để làm việc và/hoặc sẵn sàng học thêm những phần cao cấp khác của ngôn ngữ mới.

Sàng nguyên tố trên đoạn [L, R]

SÀNG NGUYÊN TỐ TRÊN ĐOẠN [L, R]

Bài toán: Hãy tìm các số nguyên thuộc đoạn [L, R], trong đó (1<=L<=R<=2.000.000.000 và R-L<=1.000.000).

Thuật toán:
- Trường hợp 1. Nếu R<=1.000.000 thì áp dụng phương pháp sàng bình thường
- Trường hợp 2. Nếu R>1.000.000 thì ta có có nhận xét

Nhận xét: nếu số nguyên n không là số nguyên tố thì n có ước số là sqrt(n).
Trong trường hợp n là số lớn nhất như trong đề bài, tức là n=2.000.000.000 thì n có ước số nhỏ hơn hay bằng sqrt(n)=44.722. Vậy ta sẽ tìm các số nguyên tố nhỏ hơn hay bằng 44.722


Bước 1. Sàng các số nguyên tố trên đoạn [1...44.722], để cho gọn gàng ta có thể sàng trên đoạn [1...50.000], còn nếu chính xác thì ta chỉ cần sàng trên đoạn [1...sqrt(R)]
Bước 2. Xét các số nguyên tố i trong đoạn [1...sqrt(R)], ta sẽ loại bỏ đi các số không nguyên tố j là bội của i. Nhưng để cho nhanh ta phải tính toán sao cho j thuộc [L, R]

Cách tính j:
- Nếu L chia hết cho i thì j=L
- Nếu L không chia hết cho i thì:
  + Tìm số lớn nhất gần L mà chia hết cho i, tức là ta lấy số L trừ đi phần dư khi chia L cho i: k=L-(L%i). Lúc này k chia hết cho i.
  + Vậy j = k+i sẽ là số lớn hơn L và chia hết cho i

Cách đánh dấu đoạn [L, R]:
- Vì L, R có thể lên đến 2 tỷ, nhưng đoạn từ L đến R chỉ có tối đa 1 triệu số nên ta ánh xạ đoan [L, R] sang đoạn [0, R-L]

#include <bits/stdc++.h>
using namespace std;

bitset<1000000+10> isSmallPrime;
bitset<1000000+10> isLargePrime;

vector<int> primes;

void SangTrenDoan(int L, int R) {
  // Buoc 1: Sang các số nguyên tố <= sqrt(R)
  int n = (int) sqrt(R);
  isSmallPrime.set(); isSmallPrime[0]=isSmallPrime[1]=false;
  for (int i=4; i<=n; i+=2) isSmallPrime[i]=false;

  for (int i=3; i*i<=n; i+=2)
    if (isSmallPrime[i])
      for (int j=i*i; j<=n; j+=i) isSmallPrime[j]=false;

  // Bước 2: Sang các số nguyên tố thuộc đoạn [L, R]
  isLargePrime.set();
  for (int i=2; i*i<=R; i++)
    if (isSmallPrime[i]) {
      if (L%i==0) 
        for (int j=L; j<=R; j+=i) isLargePrime[j-L]=false;
      else if (L>i) {
        int du = L%i;
        for (int j=(L-du)+i; j<=R; j+=i) isLargePrime[j-L]=false;
      }
    }
   
  for (int i=L; i<=R; i++)
    if (isLargePrime[i-L]) primes.push_back(i);
}

Lập trình là gì

LẬP TRÌNH LÀ GÌ?

Lập trình là gì?
Lập trình là giải quyết vấn đề bằng cách viết các chương trình máy tính.

Định nghĩa ngắn gọn trên, nhấn mạnh rằng người lập trình là người giải quyết vấn đề, là một solver. Qua đó định hướng cho người lập trình là phải luôn luôn có thói quen suy nghĩ về các cách giải quyết vấn đề.

Học lập trình cần học gì?
Vì lập trình là giải quyết vấn đề nên người lập trình cần phải học:
(1) Học ngôn ngôn ngữ lập trình: Học ngôn ngữ lập trình để chúng ta có thể hiểu được khả năng của máy tính, khả năng của ngôn ngữ. Và qua ngôn ngữ lập trình chúng ta sẽ thể hiện các ý tưởng của mình cho máy tính thực hiện
(2) Học phương pháp giải quyết vấn đề: Học phương pháp giải quyết vấn đề thông qua các phần như
  + Học các thuật toán và cấu trúc dữ liệu kinh điển
  + Học phương pháp thiết kế thuật toán, như: (1) phương pháp chia để trị, (2) phương pháp quy hoạch động, (3) phương pháp tham lam, (4) phương quay lui, (5) phương pháp nhánh cận
  + Học các mô hình toán, công cụ toán cho từng loại bài toán
  + Rèn luyện, tìm tòi, học hỏi các ý tưởng giải quyết từng bài toán cụ thể khác nhau

Việc học ngôn ngữ mới có thể thực hiện trong 1-2 tuần là có thể nắm được cơ bản của ngôn ngữ và có có thể sử dụng ngôn ngữ đó để làm việc. Trong quá trình làm việc chúng ta sẽ tìm hiểu thêm về ngôn ngữ và sẽ dần dần thành thạo ngôn ngữ.

Việc học phương pháp giải quyết vấn đề là hành trình không bao giờ kết thúc. Chính vì vậy chúng ta không thể ép bản thân phải nắm mọi thứ trong thời gian ngắn. Chúng ta cứ từ từ học, cần học điều đặn mỗi ngày một chút

Lập trình, khoa học và nghệ thuật

Lập trình, khoa học và nghệ thuật

Lập trình vừa mang tính khoa học vừa mang tính nghệ thuật

1. Tính khoa học của lập trình thể hiện:
Mỗi bước trong thuật toán, mỗi lệnh trong chương trình phải:
- Có lý do
- Logic
- Chính xác
- Được chứng minh rõ ràng hay phải dựa trên mô hình toán, hay mô hình xác suất đã được chứng minh
- Tính khoa học còn thể hiện ở sự bất định của chương trình, chương trình thường có lỗi, cần luôn cải tiến, xem đi xem lại


2. Tính nghệ thuật của lập trình thể hiện:
- Trong ý tưởng:
  + Ý tưởng đơn giản, hiệu quả
  + Ý tưởng có tính bất ngờ
  + Ý tưởng được lấy ra trong đời sống thường ngày hay trong thế giới tự nhiên
  + Mỗi ý tưởng đều có một câu truyện đằng sau nó

- Trong khi viết chương trình:
  + Cấu trúc chương trình đơn giản, rõ ràng, đẹp đẽ
  + Các biến được đặt tên có nghĩa, dễ đọc, dễ hiểu
  + Mỗi đoạn chương trình được viết ngắn gọn, dễ đọc, dễ nhớ
  + Mỗi dòng lệnh, đoạn mã thể hiện một câu truyện. Chúng diễn đạt rất tự nhiên những suy nghĩ của người lập trình

Cho nên khi lập trình, chúng ta cần chú ý, thể hiện cả tính khoa học và tính nghệ thuật trongchương trình.

Cây khung nhỏ nhất - Thuật toán Prim

Cây khung nhỏ nhất - Thuật toán Prim

Độ phức tạp: O(E * logV)


#include <bits/stdc++.h>
using namespace std;

const int INT_MAX = 1e9; typedef pair<int, int> pii;

// input
vector<vector<pii> > adj;

// output
vector<int> pre;


long long Prim() {
  int n = adj.size();
  pre.assign(n, -1);
  vector<bool> visited(n);
  vector<int> dist(n, INT_MAX);
  dist[0] = 0;

  priority_queue<pii, vector<pii> , greater<pii> > q;
  q.push(make_pair(0, 0));

  long long res = 0;

  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    
    if (visited[u]) continue;

    visited[u] = true;
    res += d;

    for (int i = 0; i < (int) adj[u].size(); i++) {
      int v = adj[u][i].first;

      if (visited[v]) continue;

      int nprio = g[u][i].second;
      if (dist[v] > nprio) {
        dist[v] = nprio;
        pred[v] = u;
        q.push(make_pair(nprio, v));
      }
    }
  }

  return res;
}


int main() {
  adj.resize(3);
  adj[0].push_back(make_pair(1, 10));
  adj[1].push_back(make_pair(0, 10));
  adj[1].push_back(make_pair(2, 10));
  adj[2].push_back(make_pair(1, 10));
  adj[2].push_back(make_pair(0, 5));
  adj[0].push_back(make_pair(2, 5));

  long long res = Prim();
  cout << res << endl;
}

Ước số chung lớn nhất - Bội số chung nhỏ nhất

Thuật toán tìm ước số chung lớn nhất - bội số chung nhỏ nhất

Khái niệm: Ước số chung lớn nhất của hai số nguyên a và b, ký hiêu là USCLN(a, b), là số nguyên d lớn nhất mà cả a và b đều chia hết cho d.

Công thức: USCLN(a, b) = USCLN(b, a mod b)

Nhận xét: Công thức đệ quy trên sẽ dừng khi b=0 và kết quả là a

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int USCLN(int a, int b) {

  if (b==0) return a;

  return USCLN(b, a%b);

}

Khái niệm: Bội số chung nhỏ nhất của hai số nguyên a và b, ký hiêu là BSCNN(a, b), là số nguyên d nhỏ nhất mà d đều chia hết cho cả a và b.

Công thức: BSCNN(a, b) = (a*b)/USCLN(a, b)

Nhận xét: Cả a và b đều chia hết cho USCLN(a, b) nên chúng ta có thể viết lại công thức trên để tránh việc tràn số khi tính toán phép nhân trước: BSCNN(a, b) = a/USCLN(a, b)*b;

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int BSCNN(int a, int b) {

  return a/USCLN(a, b)/b;

}

Phân tích thừa số nguyên tố

Thuật toán phân tích thừa số nguyên tố

Chức năng: Phân tích số nguyên n thành các thừa số nguyên tố

Chương trình:

#include <bits/stdc++.h>

using namespace std;

vector<int> p, alpha;

void Factor(int n) {

  if ((n<=1000000 && isPrime[n]) || (n>1000000 && IsPrime(n) == true)) {

    p.push_back(n); alpha.push_back(1);

    return;

  }

  int i=0;

  while (n>1) {

    while ((i<primes.size()) && (n%primes[i]!=0)) i++;

    if (i==primes.size()-1) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

    int count=0;

    while (n%primes[i] == 0) {

      count++; 

      n = n/primes[i];

    }

    p.push_back(primes[i]); alpha.push_back(count);

    if ((n<=1000000 && isPrime[n])) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

  }

}

Kiểm tra số nguyên tố

Thuật toán kiểm tra số nguyên tố

Chức năng: Kiểm tra số nguyên n có phải là số nguyên tố không

Thuật toán 1: Kiểm tra số n có chia hết cho các số i, số nguyên i chạy từ 2 đến sqrt(n), hay không
Thuật toán 2: Cải tiến giá trị của biến chạy i
Số nguyên i luôn có một trong các dạng sau:
  (1) 6k+1, 6k-1
  (2) 6k+2, 6k-2

  (3) 6k+3, 6k-3

Trường hợp i có dạng 6k+2, 6k-2, lúc đó i chia hết cho 2. Nếu n chia hết cho i thì n chia hết cho 2
Trường hợp i có dạng 6k+3, 6k-3, lúc đó i chia hết cho 3. Nếu n chia hết cho i thì n chia hết cho 3

Chúng ta kiểm tra trường hợp i có dạng (1) và (2) riêng bằng cách kiểm tra n có chia hết cho 2 hay 3 không

Sau đó chúng ta xét i có dạng (3), tức là i có giá trị: (5, 7), (11, 13), (17, 19), ...

Độ phức tạp: O(sqrt(n))

Chương trình:

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int n) {

  if (n<2) return false;

  if (n==2 || n==3) return true;

  if (n%2==0 || n%3==0) return false;

  for (int i=5; i*i<=n; i+=6)

    if (n%i==0 || n%(i+2)==0) return false;

  return false;

}

Nếu chúng ta đã tính sàng nguyên tố hoặc việc tính sàng nguyên tố không ảnh hưởng độ phức tạp của thuật toán cả chương trình thì chúng ta có thuật toán kiểm tra số nguyên tố sau hiệu quả hơn bằng cách xét xem n có chia hết các số nguyên tố không.

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int n) {

  if (n<2) return false;

  if (n<=1000000) return isPrime[i];

  for (int i=0; primes[i]*primes[i]<=n; i++)

    if (n%primes[i]==0) return false;

  return false;

}

Sàng nguyên tố Eratosthenes

Thuật toán Sàng nguyên tố Eratosthenes

Chức năng: Sàng nguyên tố Eratosthenes có hai chức năng

(1) Liệt kê các số nguyên tố nhỏ hơn hay bằng n

(2) Tạo mảng dùng để truy vấn kiểm tra môt số có phải là số nguyên tố hay không

Độ phức tạp: O(N*loglogN)

Chương trình:

#include <bits/stdc++.h>

using namespace std;

bitset<1000000+10> isPrime;

vector<int> primes;

void Eratosthenes(int n) {

  isPrime.set(); isPrime[0]=isPrime[1]=false;

  for (int i=4; i<=n; i+=2) isPrime[i]=false;

  for (int i=2; i*i<=n; i++)

    if (isPrime[i])

     for (int j=i*i; j<=n; j+=i) isPrime[j] = false;

  for (int i = 2; i <= n; i++) if (isPrime[i]) primes.push_back(i);

}

Các khía cạnh của toán học

Toán học có 3 khía cạnh:
1. Các cấu trúc (biểu diễn, mô tả): cấu trúc đồ thị, cấu trúc nhóm (cấu trúc đối xứng), cấu trúc số phức, cấu trúc số tự nhiên, ... Cần phải học cách phân tích các cấu trúc, tìm các cấu trúc thích hợp.
2. Các đại lượng (con số, các phép toán, các đo lường, tính toán)
3. Các thuật toán (phương pháp tiếp cận, chiến lược, các bước)