Chuyên đề 2: Giải toán & Thuật toán số học (Chi tiết từng bài)

Chuyên đề này hướng dẫn chi tiết từng bài học từ Tuần 13 đến Tuần 23 theo lộ trình ôn thi Tin học trẻ. Mỗi bài học tập trung vào giải thuật tối ưu và cấu trúc lệnh kéo thả tương ứng.

📘 Bài 1 (Tuần 13): Nhập dữ liệu & Định dạng đầu ra

Mục tiêu: Đọc dữ liệu đầu vào có ràng buộc và định dạng hiển thị kết quả đúng chuẩn phòng thi.

1. Kỹ thuật lấy thông tin từ người dùng

Sử dụng câu lệnh hỏi [Nhập dữ liệu] và đợi. Dữ liệu nhập vào sẽ lưu ở biến câu trả lời.

Nếu đề bài yêu cầu nhập nhiều giá trị (ví dụ nhập 2 số $A$ và $B$ ), ta thực hiện hỏi 2 lần:
- Hỏi "Nhập số A: " $\to$ đặt [A] thành [câu trả lời]
- Hỏi "Nhập số B: " $\to$ đặt [B] thành [câu trả lời]

2. Định dạng đầu ra phức tạp bằng khối `kết hợp (join)`

Khi in ra màn hình, giám khảo yêu cầu định dạng rõ ràng (ví dụ: "Ước chung lớn nhất là: 12" hoặc "Số 23 là số nguyên tố").

Khối lệnh kết hợp (join) trong nhóm Operators mặc định ghép 2 chuỗi văn bản. Để ghép nhiều chuỗi, ta lồng các khối kết hợp vào nhau:
- kết hợp [Số ] [ kết hợp [ N ] [ là số nguyên tố ] ]
- Kết quả in ra sân khấu qua câu lệnh nói: nói [chuỗi kết hợp] trong [5] giây.

📘 Bài 2 (Tuần 14): Thuật toán Min, Max & Tính tổng dồn

Mục tiêu: Duyệt các số nhập vào để tìm phần tử lớn nhất/nhỏ nhất và cộng lũy kế.

1. Thuật toán tìm giá trị lớn nhất (Max) / nhỏ nhất (Min)

Giả sử người dùng nhập vào một dãy gồm $N$ số. Ta cần tìm số lớn nhất.

Giải thuật:
1. Hỏi số thứ nhất $\to$ Đặt biến max thành câu trả lời.
2. Lặp lại N - 1 lần để nhập các số tiếp theo:
  - Hỏi "Nhập số tiếp theo: "
  - Nếu câu trả lời > max thì:
    - Đặt max thành câu trả lời.
3. Sau vòng lặp, max chính là số lớn nhất.

2. Thuật toán Tính tổng dồn (Accumulator)

Tính tổng các số từ $1$ đến $N$ .

Khởi tạo biến tong_so = 0, biến chạy i = 1.
Lặp lại N lần:
- Đặt tong_so thành tong_so + i.
- Thay đổi i một lượng 1.

📘 Bài 3 (Tuần 15): Làm chủ Danh sách (List/Mảng)

Mục tiêu: Sử dụng mảng động để xử lý dãy số có kích thước lớn.

1. Khởi tạo mảng trống

Ở đầu chương trình, luôn phải dùng lệnh: xóa tất cả của [danh sách]. Nếu không, danh sách sẽ giữ nguyên các số cũ của lần chạy trước làm sai lệch kết quả.

2. Thuật toán duyệt danh sách tìm kiếm phần tử chẵn

Giả sử có danh sách day_so chứa các số ngẫu nhiên. Ta muốn lọc các số chẵn ra một danh sách khác tên là so_chan:

xóa tất cả của [so_chan]
Đặt biến chỉ số i = 1
Lặp lại kích thước của [day_so] lần:
- Nếu (phần tử i của [day_so] mod 2) = 0 thì:
  - Thêm phần tử i của [day_so] vào so_chan.
- Thay đổi i một lượng 1.

📘 Bài 4 (Tuần 16): Thuật toán Kiểm tra Số nguyên tố tối ưu

Mục tiêu: Lập trình kiểm tra số nguyên tố chạy trong dưới 1 giây với N lên tới 10^9 (1 tỷ).

1. Tại sao cần tối ưu căn bậc hai?

Nếu kiểm tra số N = 10^9 bằng cách chia thử từ 2 đến N-1, Scratch sẽ phải lặp 1 tỷ lần, mất khoảng vài phút và bị treo máy. Tuy nhiên, nếu số N có một ước số lớn hơn căn bậc hai của N thì chắc chắn nó phải có một ước số khác tương ứng nhỏ hơn hoặc bằng căn bậc hai của N. Do đó, ta chỉ cần chia thử từ 2 đến phần nguyên của căn bậc hai của N. Số lần lặp giảm từ 1 tỷ xuống còn khoảng 31,622 lần (chạy mất chưa tới 0.05 giây).

2. Khối lệnh Scratch tối ưu:

scratch

định nghĩa kiem_tra_nguyen_to [N]
đặt [la_so_nguyen_to] thành [1]
nếu < [N] < [2] > thì
  đặt [la_so_nguyen_to] thành [0]
ngược lại
  đặt [i] thành [2]
  lặp lại cho đến khi << [i] > [làm tròn xuống (căn bậc hai của (N))] > hoặc < [la_so_nguyen_to] = [0] >>
    nếu < (N mod i) = [0] > thì
      đặt [la_so_nguyen_to] thành [0]
    thay đổi [i] một lượng [1]

📘 Bài 5 (Tuần 17): Phân tích thừa số nguyên tố & Sàng Eratosthenes

Mục tiêu: Thực hiện phân tích cấu trúc nhân tử và tìm nhanh tập hợp số nguyên tố.

1. Phân tích thừa số nguyên tố (Prime Factorization)

Đặt biến chia = 2.
Lặp lại cho đến khi N = 1:
- Nếu N mod chia = 0 thì:
  - Thêm chia vào danh sách cac_thua_so.
  - Đặt N thành N / chia.
- Ngược lại:
  - Thay đổi chia một lượng 1.

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

Sử dụng một danh sách có $N$ phần tử để đánh dấu.

Điền đầy danh sách danh_dau gồm $N$ phần tử có giá trị ban đầu là 1 (biểu thị là số nguyên tố).
Đặt danh_dau[1] = 0.
Đặt biến p = 2.
Lặp lại cho đến khi p * p > N:
- Nếu phần tử p của danh_dau = 1 thì:
  - Đặt biến bội số k = p * p.
  - Lặp lại cho đến khi k > N:
    - Đặt phần tử k của danh_dau thành 0 (loại bỏ bội số của p).
    - Đặt k thành k + p.
- Thay đổi p một lượng 1.
Sau khi sàng xong, các vị trí có giá trị 1 trong danh sách danh_dau chính là các số nguyên tố.

📘 Bài 6 (Tuần 18): Thuật toán tìm UCLN và BCNN

Mục tiêu: Lập trình tìm ước và bội chung của hai số dựa trên số dư.

Thuật toán Euclid chia dư (Modulo):

So với việc tìm tất cả các ước của cả hai số rồi so sánh (rất chậm), thuật toán chia dư Euclid thực hiện hoán đổi giá trị chia dư cho đến khi số dư bằng 0.

Khai báo 2 biến a = A, b = B.
Lặp lại cho đến khi b = 0:
- Đặt biến tạm temp thành b.
- Đặt b thành a mod b.
- Đặt a thành temp.
Sau vòng lặp, ước chung lớn nhất (UCLN) chính là giá trị của biến a.
Tính BCNN: BCNN = (A * B) / UCLN.

📘 Bài 7 (Tuần 19): Số hoàn hảo & Số đối xứng

Mục tiêu: Kiểm tra tính chất đặc biệt của một số tự nhiên.

1. Lập trình tìm Số hoàn hảo

Số hoàn hảo là số bằng tổng các ước thực sự của nó.

Khởi tạo biến tong_uoc = 1 (vì 1 luôn là ước của mọi số).
Đặt biến chạy i = 2.
Lặp lại cho đến khi i > làm tròn xuống (N / 2):
- Nếu N mod i = 0 thì:
  - Đặt tong_uoc thành tong_uoc + i.
- Thay đổi i một lượng 1.
Nếu tong_uoc = N và N > 1 thì kết luận N là số hoàn hảo.

2. Lập trình kiểm tra Số đối xứng

Chuyển số N thành chuỗi ký tự.
Đặt biến i thành độ dài của chuỗi N.
Khởi tạo chuỗi rỗng chuoi_dao_nguoc.
Lặp lại độ dài của chuỗi N lần:
- Đặt chuoi_dao_nguoc thành kết hợp [chuoi_dao_nguoc] [ký tự thứ i của chuỗi N].
- Thay đổi i một lượng -1.
Nếu N = chuoi_dao_nguoc thì concluse N là số đối xứng.

📘 Bài 8 (Tuần 20): Thuật toán Duyệt vét cạn (Vòng lặp lồng nhau)

Mục tiêu: Giải quyết bài toán bằng cách thử nghiệm toàn bộ không gian nghiệm.

Thuật toán giải bài toán "Gà và Chó"

Đề bài: Tổng số con là 36, tổng số chân là 100.

Đặt biến ga = 1.
Lặp lại 36 lần:
- Đặt biến cho thành 36 - ga.
- Nếu (ga * 2) + (cho * 4) = 100 thì:
  - Nói kết hợp [Số gà là: ] [ga] và kết hợp [Số chó là: ] [cho].
  - Dừng toàn bộ kịch bản (đã tìm thấy nghiệm).
- Thay đổi ga một lượng 1.

📘 Bài 9 (Tuần 21): Quy luật Dãy số

Mục tiêu: Xác định quy luật dãy số dựa trên vòng lặp lặp kế tiếp.

Tìm số hạng thứ $N$ của dãy Fibonacci

Dãy Fibonacci: $1, 1, 2, 3, 5, 8, 13, \dots$

Nếu N = 1 hoặc N = 2 thì kết quả là 1.
Ngược lại:
- Đặt F0 thành 1, F1 thành 1, F_next thành 0.
- Đặt biến đếm i thành 3.
- Lặp lại cho đến khi i > N:
  - Đặt F_next thành F0 + F1.
  - Đặt F0 thành F1.
  - Đặt F1 thành F_next.
  - Thay đổi i một lượng 1.
- Kết quả là F_next.

📘 Bài 10 (Tuần 22): Xử lý Chuỗi ký tự cơ bản

Mục tiêu: Làm việc với các lệnh duyệt và đếm trên chuỗi ký tự.

Thuật toán đếm số từ trong một câu văn

Mỗi từ cách nhau bởi một dấu cách " ". Thuật toán sẽ đếm số khoảng trắng để suy ra số từ.

Đặt biến dem_tu = 1 (giả định câu có ít nhất 1 từ).
Đặt biến chỉ mục i = 1.
Lặp lại độ dài của chuỗi [cau_nhap_vao] lần:
- Nếu ký tự thứ i của [cau_nhap_vao] = " " thì:
  - Thay đổi dem_tu một lượng 1.
- Thay đổi i một lượng 1.
In kết quả dem_tu.

📘 Bài 11 (Tuần 23): Chuẩn hóa chuỗi văn bản

Mục tiêu: Làm sạch dữ liệu chuỗi nhập vào bị lỗi dấu cách.

Thuật toán loại bỏ dấu cách thừa (Trái, phải và giữa các từ)

Khởi tạo chuỗi rỗng chuoi_sach.
Đặt chỉ mục i = 1.
Lặp lại độ dài của chuỗi [cau_nhap_vao] lần:
- Nếu không << ký tự thứ i của cau_nhap_vao = " "> và < ký tự thứ i+1 của cau_nhap_vao = " " >> thì:
  - Đặt chuoi_sach thành kết hợp [chuoi_sach] [ký tự thứ i của cau_nhap_vao].
- Thay đổi i một lượng 1.
(Đoạn code trên xử lý dấu cách đúp ở giữa chuỗi. Cuối cùng, thực hiện cắt dấu cách ở đầu và cuối chuỗi sạch nếu có).

Chuyên đề 2: Giải toán & Thuật toán số học (Chi tiết từng bài) ​

📘 Bài 1 (Tuần 13): Nhập dữ liệu & Định dạng đầu ra ​

1. Kỹ thuật lấy thông tin từ người dùng ​

2. Định dạng đầu ra phức tạp bằng khối kết hợp (join) ​

📘 Bài 2 (Tuần 14): Thuật toán Min, Max & Tính tổng dồn ​

1. Thuật toán tìm giá trị lớn nhất (Max) / nhỏ nhất (Min) ​

2. Thuật toán Tính tổng dồn (Accumulator) ​

📘 Bài 3 (Tuần 15): Làm chủ Danh sách (List/Mảng) ​

1. Khởi tạo mảng trống ​

2. Thuật toán duyệt danh sách tìm kiếm phần tử chẵn ​

📘 Bài 4 (Tuần 16): Thuật toán Kiểm tra Số nguyên tố tối ưu ​

1. Tại sao cần tối ưu căn bậc hai? ​

2. Khối lệnh Scratch tối ưu: ​

📘 Bài 5 (Tuần 17): Phân tích thừa số nguyên tố & Sàng Eratosthenes ​

1. Phân tích thừa số nguyên tố (Prime Factorization) ​

2. Thuật toán Sàng số nguyên tố Eratosthenes ​

📘 Bài 6 (Tuần 18): Thuật toán tìm UCLN và BCNN ​

Thuật toán Euclid chia dư (Modulo): ​

📘 Bài 7 (Tuần 19): Số hoàn hảo & Số đối xứng ​

1. Lập trình tìm Số hoàn hảo ​

2. Lập trình kiểm tra Số đối xứng ​

📘 Bài 8 (Tuần 20): Thuật toán Duyệt vét cạn (Vòng lặp lồng nhau) ​

Thuật toán giải bài toán "Gà và Chó" ​

📘 Bài 9 (Tuần 21): Quy luật Dãy số ​

Tìm số hạng thứ N của dãy Fibonacci ​

📘 Bài 10 (Tuần 22): Xử lý Chuỗi ký tự cơ bản ​

Thuật toán đếm số từ trong một câu văn ​

📘 Bài 11 (Tuần 23): Chuẩn hóa chuỗi văn bản ​

Thuật toán loại bỏ dấu cách thừa (Trái, phải và giữa các từ) ​