Số lẻ
Đề bài
Bạn được cho một số nguyên dương $N$. Bạn hãy in ra tất cả các số lẻ trong các số nguyên dương thuộc đoạn $[1, N]$ và theo thứ tự tăng dần.
Dữ liệu nhập: gồm một số nguyên dương $N$ duy nhất $(1 \le N \le 50)$.
Dữ liệu xuất: gồm một dòng duy nhất gồm toàn bộ các số lẻ của các số nguyên dương từ $1$ đến $N$. Các số lẻ cách nhau bởi một dấu cách và được sắp xếp tăng dần theo giá trị.
81 3 5 7Lời mở đầu
Đây là bài mở màn của chương Đệ quy cơ bản. Dùng vòng for thì bài này chỉ cần 1 dòng, nhưng mục tiêu của bài là để các bạn tập viết hàm đệ quy và hiểu thật rõ máy tính chạy một hàm đệ quy như thế nào: lời gọi nào được đẩy vào ngăn xếp, khi nào thì quay về. Mình sẽ giải bằng 2 cách đệ quy: in trước rồi mới gọi và gọi trước rồi mới in – hai kiểu này sẽ còn gặp lại suốt chương.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Số test | Giá trị N | Subtask |
|---|---|---|
| 50 | Test thứ $i$ có $N = i$, tức là đủ mọi giá trị $N = 1, 2, \dots, 50$ | Không chia subtask |
Bộ test "quét" hết mọi giá trị của $N$ nên code sai ở trường hợp biên nào (ví dụ $N = 1$, hay $N$ chẵn/lẻ) cũng sẽ lộ ra. Với $N \le 50$, độ sâu đệ quy tối đa chỉ 50 tầng – không có gì phải lo về tốc độ hay tràn ngăn xếp.
Ý tưởngHàm đệ quy = điểm dừng + lời gọi bài toán nhỏ hơn
Một hàm đệ quy luôn có 2 phần:
- Điểm dừng (trường hợp cơ sở): trường hợp nhỏ tới mức trả lời ngay được, không cần gọi tiếp.
- Lời gọi đệ quy: giải bài toán hiện tại bằng cách nhờ chính hàm đó giải một bài toán nhỏ hơn.
Với bài này có 2 cách "thu nhỏ" bài toán:
inLe(i) in các số lẻ từ $i$ tới $N$: in $i$, rồi nhờ inLe(i + 2) in phần còn lại. Dừng khi $i > N$.Cách 2 – đi ngược:
sole(k) in các số lẻ trong $[1, k]$: nhờ sole(k - 1) in xong đoạn $[1, k - 1]$ trước, sau đó nếu $k$ lẻ thì in $k$. Dừng khi $k = 0$.Điểm thú vị của Cách 2: lời gọi đi từ $N$ xuống $0$, nhưng các số lại được in ra theo thứ tự tăng dần – vì lệnh in nằm sau lời gọi đệ quy, nên nó chỉ chạy khi các lời gọi bên dưới đã xong và "quay về". Em chọn cách, nhập $N$ rồi bấm Tiếp để xem cây đệ quy:
Cách 1In trước, gọi sau
Biến n để toàn cục cho hàm đệ quy dùng được. Hàm inLe(i) chỉ cần nhớ đang đứng ở số lẻ nào.
- Điểm dừng
if(i > n) return;phải đặt đầu tiên, nếu không hàm sẽ gọi mãi không dừng (tràn ngăn xếp). - Mỗi lời gọi tăng $i$ thêm 2 nên chỉ đi qua các số lẻ $1, 3, 5, \dots$ – không cần kiểm tra chẵn lẻ. Số tầng đệ quy khoảng $N / 2$.
- Lệnh in nằm trước lời gọi đệ quy → số được in ngay khi "đi xuống".
Kết quả chạy thật: bản C++ đúng 50/50 test, test đúng chạy lâu nhất 0.006s; bản Python đúng 50/50 test, test đúng chạy lâu nhất 0.020s.
Cách 2Gọi trước, in sau
Lần này hàm nhận độ dài đoạn $k$ và giải bài toán "in các số lẻ trong $[1, k]$" bằng bài toán nhỏ hơn $[1, k - 1]$.
sole(n)gọisole(n - 1), … , xuống tớisole(0)thì dừng. Lúc này ngăn xếp có $N + 1$ lời gọi đang "chờ".- Từ
sole(0)quay vềsole(1): 1 lẻ → in 1. Quay vềsole(2): 2 chẵn → không in. Quay vềsole(3): in 3… Nhờ vậy dãy in ra tăng dần dù lời gọi đi từ lớn xuống nhỏ. - Nếu đổi chỗ 2 dòng (in trước, gọi sau) thì dãy sẽ in ra giảm dần (sole(n) sẽ in n trước tiên).
Kết quả chạy thật: bản C++ đúng 50/50 test, test đúng chạy lâu nhất 0.004s; bản Python đúng 50/50 test, test đúng chạy lâu nhất 0.023s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. In trước, gọi sau | C++ | 50/50 | 0.006s | Full điểm |
| Python | 50/50 | 0.020s | Full điểm | |
| 2. Gọi trước, in sau | C++ | 50/50 | 0.004s | Full điểm |
| Python | 50/50 | 0.023s | Full điểm |
Nhận xét
Đăng nhận xét