Số lẻ

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Ngăn xếp lời gọi

Đề 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ị.

Ví dụ – input

8

Ví dụ – output

1 3 5 7

Lờ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ộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test50 testÝ tưởngcây đệ quyCách 1in trước, gọi sauCách 2gọi trước, in sau

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:

Hai cách nhìn

Cách 1 – đi xuôi: 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 (1 hoặc 2): N =

Ví dụ nhanh:

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.

C++▶ Chạy tay từng dòng codeCách 1: inLe(i) in i rồi gọi inLe(i + 2) – in lúc đi xuống.

Dữ liệu vào (stdin) – sửa thoải mái8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Đ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).
2. 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$.
3. Lệnh in nằm trước lời gọi đệ quy → số được in ngay khi "đi xuống".

Không gian$O(N)$ (ngăn xếp)

Thời gian$O(N)$

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]$.

C++▶ Chạy tay từng dòng codeCách 2: sole(k) gọi sole(k − 1) trước rồi mới in k – in lúc quay về.

Dữ liệu vào (stdin) – sửa thoải mái5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. sole(n) gọi sole(n - 1), … , xuống tới sole(0) thì dừng. Lúc này ngăn xếp có $N + 1$ lời gọi đang "chờ".
2. 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ỏ.
3. 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).

Không gian$O(N)$ (ngăn xếp)

Thời gian$O(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

Ghi chú của mình: cả 2 cách (C++ lẫn Python) đều đạt full điểm, mỗi test chạy dưới 0,05 giây (thời gian CPU trên máy của mình, giới hạn 1 giây). Điều đáng nhớ nhất của bài: lệnh đặt trước lời gọi đệ quy chạy theo thứ tự "đi xuống", lệnh đặt sau lời gọi đệ quy chạy theo thứ tự "quay về" (ngược lại).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇