Xuất

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Hàm nhiều tham số

Đề bài

Bạn được cho một số nguyên dương $N$. Bạn hãy xuất ra $N$ dòng được tổ chức như sau:

1 N
2 N - 1
3 N - 2
.....
N - 1 2
N 1

Dữ liệu nhập: gồm một số nguyên dương duy nhất là số $N$ $(1 \le N \le 50)$.

Dữ liệu xuất: gồm $N$ dòng được tổ chức theo format của đề.

Ví dụ – input

4

Ví dụ – output

1 4
2 3
3 2
4 1

Lời mở đầu

Bài thứ hai của chương Đệ quy cơ bản, vẫn là một bài "in ấn" rất nhẹ nhàng. Mình giải bằng vòng lặp trước để thấy quy luật, rồi chuyển sang hàm đệ quy có 2 tham số – mỗi lời gọi mang theo đủ thông tin của dòng cần in, lời gọi sau chỉ việc "dịch" 2 số đi một bước.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

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

Bộ test50 testÝ tưởngtổng N + 1Cách 1vòng lặpCách 2đệ quy

Bộ testBộ test chính thức có gì?

Số test	Giá trị N	Số dòng phải in	Subtask
50	Test thứ $i$ có $N = i$ (đủ mọi giá trị từ 1 đến 50)	1 … 50	Không chia subtask

Dữ liệu rất nhỏ, chỉ cần in đúng định dạng là đủ. Chú ý trường hợp $N = 1$: in đúng 1 dòng 1 1.

Ý tưởngHai số trên mỗi dòng luôn có tổng N + 1

Nhìn ví dụ $N = 4$: các dòng là $(1, 4),$ $(2, 3),$ $(3, 2),$ $(4, 1)$. Số đầu tăng dần từ $1$ lên $N$, số sau giảm dần từ $N$ về $1$, và tổng hai số luôn bằng $N + 1$. Vậy dòng thứ $i$ là i và N - i + 1.

Cách nghĩ đệ quy

Hàm xuat(a, b) nghĩa là: "in dòng a b, rồi in tiếp các dòng sau đó". Dòng sau của a b là (a + 1) (b - 1), nên chỉ cần in dòng hiện tại rồi gọi xuat(a + 1, b - 1). Khi $b = 0$ là đã in đủ $N$ dòng → điểm dừng. Cả bài chỉ là một lời gọi xuat(1, N).

Em nhập $N$ rồi bấm Tiếp để xem cây đệ quy và từng dòng được in ra:

N =

Ví dụ nhanh:

Cách 1Vòng lặp for

C++▶ Chạy tay từng dòng codeCách 1: vòng for in i và n − i + 1.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Với mỗi i từ 1 tới n, in i và n - i + 1. Nhớ xuống dòng "\n" sau mỗi cặp.

Không gian$O(1)$

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.003s; bản Python đúng 50/50 test, test đúng chạy lâu nhất 0.022s.

Cách 2Đệ quy 2 tham số

C++▶ Chạy tay từng dòng codeCách 2: xuat(a, b) in dòng "a b" rồi gọi xuat(a + 1, b − 1), dừng khi b = 0.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Điểm dừng if(b == 0) return;: sau $N$ lần gọi, $b$ giảm từ $N$ về $0$ – đúng lúc đã in đủ $N$ dòng. Dùng điều kiện a > n cũng được, nhưng khi đó phải để n là biến toàn cục; với điều kiện b == 0 hàm không cần biết $n$.
2. Lệnh in đặt trước lời gọi đệ quy nên các dòng được in theo thứ tự lúc "đi xuống": xuat(1, N) in dòng đầu tiên, xuat(2, N - 1) in dòng thứ hai…
3. Độ sâu đệ quy là $N + 1 \le 51$ tầng – rất an toà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.003s; bản Python đúng 50/50 test, test đúng chạy lâu nhất 0.022s.

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. Vòng lặp	C++	50/50	0.003s	Full điểm
	Python	50/50	0.022s	Full điểm
2. Đệ quy	C++	50/50	0.003s	Full điểm
	Python	50/50	0.022s	Full điểm

Ghi chú của mình: cả vòng lặp lẫn đệ quy, C++ lẫn Python đều đạt full điểm, mỗi test dưới 0,05 giây. Bài học rút ra: khi viết đệ quy, hãy cho mỗi lời gọi mang theo đủ thông tin để tự làm phần việc của nó (ở đây là cả 2 số của dòng), lời gọi tiếp theo chỉ cần thay đổi tham số một chút.

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 😇