Bài 5: Hàm (chương trình con) trong C++ và Python: tham trị, tham chiếu, đệ quy
Lời mở đầu
Qua bài 4, các bạn đã viết được kha khá chương trình: tính tổng, đếm ước, kiểm tra số nguyên tố… Bây giờ giả sử đề bài yêu cầu đếm các số nguyên tố từ 1 đến $n$. Nếu nhét đoạn kiểm tra nguyên tố vào trong vòng lặp duyệt từ 1 đến $n$, code sẽ có 2 vòng lặp lồng nhau, biến nọ biến kia lẫn lộn, rất dễ sai. Còn nếu đề lại bắt kiểm tra nguyên tố ở 3 chỗ khác nhau thì phải chép đoạn code đó 3 lần! Hàm (function, hay còn gọi là chương trình con) sinh ra để giải quyết đúng chuyện này. Đây là viên gạch thứ 5, và là kỹ năng mà lập trình viên nào cũng dùng hằng ngày.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Hàm là gì? Cấu trúc một hàm
Thật ra các bạn đã dùng hàm từ bài 1 rồi: main() là một hàm, sqrt(x), abs(x), max(a, b) cũng là hàm. Ta đưa cho hàm một vài giá trị đầu vào (gọi là tham số), hàm làm việc rồi trả về một kết quả. Người gọi hàm không cần biết bên trong nó làm gì, giống như bấm máy tính bỏ túi vậy. Bài này ta sẽ tự viết hàm của riêng mình.
Hàm giống một chiếc hộp đen: đưa đầu vào, nhận lại kết quả. Viết một lần, gọi ở đâu cũng được.
Lợi ích của hàm:
- Viết một lần, dùng nhiều lần: không phải chép đi chép lại cùng một đoạn code.
- Chia để trị: bài toán lớn được chia thành nhiều việc nhỏ, mỗi việc một hàm, đọc code như đọc dàn ý.
- Dễ sửa, dễ tìm lỗi: hàm sai thì sửa đúng một chỗ, mọi nơi gọi hàm đều được sửa theo.
Cấu trúc một hàm trong C++ gồm 4 thành phần:
① kiểu của giá trị trả về · ② tên hàm (đặt theo việc hàm làm) · ③ các tham số kèm kiểu · ④ thân hàm, kết thúc bằng return.
Ví dụ đầu tiên: tính tổ hợp $C_n^k = \dfrac{n!}{k!\,(n-k)!}$. Công thức cần tính giai thừa tới 3 lần, nên ta viết hàm giaiThua một lần rồi gọi 3 lần. Bấm Tiếp ▶ để thấy chương trình "nhảy" từ main lên hàm rồi quay về như thế nào:
Code C++ và Python
#include <iostream>
using namespace std;
long long giaiThua(int x){
long long gt = 1;
for(int i = 2; i <= x; i++){
gt = gt * i;
}
return gt;
}
int main(){
int n, k;
cin >> n >> k;
long long tu = giaiThua(n);
long long mau = giaiThua(k) * giaiThua(n - k);
cout << tu / mau;
return 0;
}def giai_thua(x):
gt = 1
for i in range(2, x + 1):
gt = gt * i
return gt
n, k = map(int, input().split())
tu = giai_thua(n)
mau = giai_thua(k) * giai_thua(n - k)
print(tu // mau)main. Khi gặp lời gọi giaiThua(n): ① giá trị của n được chép vào tham số x → ② chạy thân hàm từ trên xuống → ③ gặp return thì hàm kết thúc, giá trị trả về "thế chỗ" cho lời gọi → ④ main chạy tiếp từ đúng chỗ đã dừng. Hàm phải được viết phía trên main (hoặc khai báo nguyên mẫu long long giaiThua(int x); ở trên) thì main mới "nhìn thấy" nó.def, không cần ghi kiểu: def giai_thua(x):. Thân hàm thụt lề vào trong. Python còn cho phép trả về nhiều giá trị cùng lúc: return a, b, rồi nhận bằng x, y = ham(). C++ muốn làm vậy thì dùng tham chiếu (phần 3) hoặc pair.Mô phỏng trực quan. Khi main gọi hàm giaiThua, chuyện gì xảy ra bên trong máy? Em bấm Tiếp để xem từng lời gọi được đặt lên ngăn xếp rồi gỡ ra thế nào khi tính C(n, k), rồi thử đổi n, k:
Phần 2Giá trị trả về: return, hàm void, hàm bool
Kiểu trả về cho biết hàm "nộp lại" cái gì. Có 3 dạng hay gặp nhất:
| Dạng hàm | Ví dụ khai báo | Dùng khi |
|---|---|---|
| Trả về số | int tongChuSo(int n) | Hàm tính ra một giá trị: tổng, tích, max, UCLN… |
| Trả về bool | bool laNguyenTo(int n) | Hàm trả lời câu hỏi CÓ / KHÔNG: có phải số nguyên tố? có đối xứng? |
| void | void inDay(int n) | Hàm chỉ làm một việc (in ra, đổi giá trị biến…) mà không trả về gì. |
Hàm kiểu bool là loại cực kỳ hay dùng trong lập trình thuật toán. Lưu ý return kết thúc hàm ngay lập tức, nên khi tìm thấy ước của $x$ ta return false luôn, không cần biến cờ hay break như ở bài 4. Ví dụ: in ra và đếm các số nguyên tố từ 1 đến $n$. Hãy so với cách viết ở bài 4, code gọn và dễ đọc hơn hẳn:
Code C++ và Python
#include <iostream>
using namespace std;
bool laNguyenTo(int x){
if(x < 2) return false;
for(int i = 2; i * i <= x; i++){
if(x % i == 0) return false;
}
return true;
}
int main(){
int n;
cin >> n;
int dem = 0;
for(int a = 1; a <= n; a++){
if(laNguyenTo(a)){
cout << a << " ";
dem++;
}
}
cout << endl << dem;
return 0;
}def la_nguyen_to(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
n = int(input())
dem = 0
for a in range(1, n + 1):
if la_nguyen_to(a):
print(a, end=" ")
dem += 1
print()
print(dem)Hàm void thì không có giá trị trả về, ta gọi nó như một câu lệnh riêng. Trong hàm void vẫn được viết return; (không kèm giá trị) để thoát sớm:
Code C++ và Python
void inHang(int k, char c){ // in k ký tự c trên một dòng
if(k <= 0) return; // không có gì để in thì thoát luôn
for(int i = 1; i <= k; i++) cout << c;
cout << endl;
}
int main(){
inHang(5, '*'); // *****
inHang(3, '#'); // ###
return 0;
}def in_hang(k, c): # in k ký tự c trên một dòng
if k <= 0:
return # không có gì để in thì thoát luôn
print(c * k)
in_hang(5, '*') # *****
in_hang(3, '#') # ###laNguyenTo(a); trơ trọi thì kết quả bị vứt đi. 3. Viết hàm bên dưới main mà không khai báo nguyên mẫu ở trên → lỗi "was not declared in this scope".Phần 3Truyền tham trị và truyền tham chiếu
Khi gọi giaiThua(n), hàm không dùng chính biến n mà nhận một bản sao giá trị của nó vào tham số x. Hàm có sửa x thế nào thì n ở main vẫn nguyên vẹn. Cách này gọi là truyền tham trị (pass by value), là mặc định của C++.
Nhưng nhiều khi ta muốn hàm sửa được biến bên ngoài, ví dụ hàm đổi chỗ 2 số. Khi đó thêm dấu & trước tên tham số: truyền tham chiếu (pass by reference). Tham số lúc này không phải bản sao nữa mà là một cái tên khác của chính biến bên ngoài, sửa nó là sửa luôn biến gốc.
Tham trị: hàm làm việc trên bản sao. Tham chiếu: tham số chỉ là "biệt danh" của biến gốc.
Chạy tay chương trình dưới đây để thấy rõ: doiCho1 (tham trị) đổi chỗ "hụt", còn doiCho2 (tham chiếu) đổi được thật:
Code C++ và Python
#include <iostream>
using namespace std;
void doiCho1(int x, int y){
int t = x;
x = y;
y = t;
}
void doiCho2(int &x, int &y){
int t = x;
x = y;
y = t;
}
int main(){
int a, b;
cin >> a >> b;
doiCho1(a, b);
cout << a << " " << b << endl;
doiCho2(a, b);
cout << a << " " << b;
return 0;
}# Python không có tham chiếu cho số nguyên như C++.
# Cách tự nhiên nhất: hàm trả về 2 giá trị mới.
def doi_cho(x, y):
return y, x
a, b = map(int, input().split())
a, b = doi_cho(a, b)
print(a, b)
# Thực ra Python đổi chỗ chỉ cần 1 dòng: a, b = b, astring, vector (bài 6, 8): truyền tham trị phải chép cả đống dữ liệu, rất chậm; dùng const vector<int> &a vừa nhanh vừa an toàn (const = cấm sửa). Với số nguyên bình thường thì cứ truyền tham trị.list (kiểu khả biến), hàm sửa phần tử a[0] = 5 thì list bên ngoài cũng đổi theo. Muốn hàm "trả về" nhiều giá trị thì cứ return x, y.Vì sao doiCho1 đổi “hụt” còn doiCho2 thì đổi được? Em xem hai hàm chạy trên các hộp nhớ: tham trị tạo hộp mới, còn tham chiếu chỉ dán thêm tên lên hộp cũ:
Phần 4Phạm vi biến và làm quen với đệ quy
Phạm vi (scope) của một biến là vùng code mà biến đó "sống" và được dùng:
- Biến cục bộ: khai báo bên trong một hàm (hoặc một khối
{ }), chỉ dùng được trong đó; hàm kết thúc là biến bị xoá. Hai hàm khác nhau có biến cùng tênicũng không đụng nhau. - Biến toàn cục: khai báo bên ngoài mọi hàm (thường ở ngay dưới
using namespace std;), hàm nào cũng dùng được. Trong lập trình thi đấu, mảng lớn hay được khai báo toàn cục (bài 6 sẽ nói rõ lý do).
Code C++ và Python
#include <iostream>
using namespace std;
int dem = 0; // biến toàn cục: hàm nào cũng thấy
void tang(){
dem++; // sửa được biến toàn cục
int x = 10; // biến cục bộ: chỉ sống trong hàm tang
}
int main(){
tang(); tang(); tang();
cout << dem; // 3
// cout << x; // LỖI: x không tồn tại ở đây
return 0;
}dem = 0 # biến toàn cục
def tang():
global dem # Python bắt khai báo global mới được gán lại
dem += 1
x = 10 # biến cục bộ
tang(); tang(); tang()
print(dem) # 3Một hàm hoàn toàn có thể gọi chính nó, đó gọi là đệ quy. Ý tưởng: muốn giải bài toán cỡ $n$, ta đưa về bài toán cùng dạng nhưng nhỏ hơn (cỡ $n - 1$), cứ thế cho tới trường hợp nhỏ nhất biết ngay đáp án (gọi là điểm dừng). Ví dụ giai thừa: $n! = n \times (n-1)!$ và điểm dừng $0! = 1$.
Gọi gt(3) → gt(2) → gt(1) → gt(0) chạm điểm dừng, rồi kết quả nhân ngược lên: 1 → 1 → 2 → 6.
Code C++ và Python
#include <iostream>
using namespace std;
long long gt(int n){
if(n == 0) return 1;
return n * gt(n - 1);
}
int main(){
int n;
cin >> n;
cout << gt(n);
return 0;
}def gt(n):
if n == 0:
return 1
return n * gt(n - 1)
n = int(input())
print(gt(n))if(n == 0) return 1; thì hàm gọi mãi không dừng, ngăn xếp bị tràn và chương trình bị "crash" (lỗi stack overflow, Python báo RecursionError). Ngoài ra Python mặc định chỉ cho đệ quy sâu khoảng 1000 tầng. Đệ quy là chủ đề lớn, các bạn sẽ gặp lại nhiều ở các bài đệ quy, quay lui và quy hoạch động.Đệ quy là phần khó hình dung nhất của bài hàm. Em xem mô phỏng gt(n) dưới đây: các lời gọi chồng lên nhau như chồng đĩa, mỗi lời gọi đứng chờ lời gọi bên trên trả kết quả về:
Bài tậpLuyện viết hàm
Với mỗi bài, hãy tập thói quen: viết hàm xử lý riêng, còn main chỉ lo nhập, gọi hàm và in kết quả. Code tham khảo bên dưới đều viết theo đúng tinh thần đó.
Viết hàm max3(a, b, c) trả về số lớn nhất trong 3 số nguyên. Nhập 3 số, in kết quả.
4 9 29💡 Gợi ý
max2(x, y) trước, rồi max3(a, b, c) = max2(max2(a, b), c). Đây chính là tinh thần "dùng lại hàm đã có".Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
int max2(int x, int y){
if(x > y) return x;
return y;
}
int max3(int a, int b, int c){
return max2(max2(a, b), c);
}
int main(){
int a, b, c;
cin >> a >> b >> c;
cout << max3(a, b, c);
return 0;
}def max2(x, y):
return x if x > y else y
def max3(a, b, c):
return max2(max2(a, b), c)
a, b, c = map(int, input().split())
print(max3(a, b, c))Viết hàm tongChuSo(n). Nhập $T$ rồi $T$ số nguyên dương ($\le 10^{18}$), mỗi số in ra tổng chữ số của nó trên một dòng.
3
123
9
20266
9
10💡 Gợi ý
tongChuSo(x).Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
int tongChuSo(long long n){
int s = 0;
while(n > 0){
s += n % 10;
n /= 10;
}
return s;
}
int main(){
int T;
cin >> T;
while(T--){
long long x;
cin >> x;
cout << tongChuSo(x) << endl;
}
return 0;
}def tong_chu_so(n):
s = 0
while n > 0:
s += n % 10
n //= 10
return s
T = int(input())
for _ in range(T):
x = int(input())
print(tong_chu_so(x))Viết hàm ucln(a, b) và bcnn(a, b). Nhập $a, b$ ($\le 10^9$), in UCLN và BCNN.
12 186 36💡 Gợi ý
long long vì BCNN có thể tới $10^{18}$.Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
long long ucln(long long a, long long b){
while(b != 0){
long long r = a % b;
a = b;
b = r;
}
return a;
}
long long bcnn(long long a, long long b){
return a / ucln(a, b) * b; // chia trước, nhân sau để tránh tràn
}
int main(){
long long a, b;
cin >> a >> b;
cout << ucln(a, b) << " " << bcnn(a, b);
return 0;
}def ucln(a, b):
while b != 0:
a, b = b, a % b
return a
def bcnn(a, b):
return a // ucln(a, b) * b
a, b = map(int, input().split())
print(ucln(a, b), bcnn(a, b))Số hoàn hảo là số bằng tổng các ước của nó (không kể chính nó), ví dụ $6 = 1 + 2 + 3$. Viết hàm bool hoanHao(x), in ra các số hoàn hảo không vượt quá $n$ ($n \le 10^4$).
10006 28 496💡 Gợi ý
return tong == x;. Biểu thức so sánh tự nó đã là bool, không cần if.Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
bool hoanHao(int x){
int tong = 0;
for(int i = 1; i < x; i++){
if(x % i == 0) tong += i;
}
return tong == x;
}
int main(){
int n;
cin >> n;
for(int a = 2; a <= n; a++){
if(hoanHao(a)) cout << a << " ";
}
return 0;
}def hoan_hao(x):
tong = 0
for i in range(1, x):
if x % i == 0:
tong += i
return tong == x
n = int(input())
for a in range(2, n + 1):
if hoan_hao(a):
print(a, end=" ")Viết hàm void doiCho(int &x, int &y). Dùng nó để sắp xếp 3 số $a, b, c$ theo thứ tự tăng dần rồi in ra.
7 2 52 5 7💡 Gợi ý
&, thiếu nó thì hàm đổi chỗ "hụt" như phần 3.Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
void doiCho(int &x, int &y){
int t = x;
x = y;
y = t;
}
int main(){
int a, b, c;
cin >> a >> b >> c;
if(a > b) doiCho(a, b);
if(a > c) doiCho(a, c);
if(b > c) doiCho(b, c);
cout << a << " " << b << " " << c;
return 0;
}a, b, c = map(int, input().split())
if a > b: a, b = b, a
if a > c: a, c = c, a
if b > c: b, c = c, b
print(a, b, c)Số đối xứng là số đọc xuôi hay ngược đều như nhau (121, 7, 4554). Nhập $a, b$ ($1 \le a \le b \le 10^6$), đếm số lượng số đối xứng trong đoạn $[a, b]$.
10 13012💡 Gợi ý
daoNguoc(x) (bài tập 5 của bài 4) rồi hàm bool doiXung(x) { return daoNguoc(x) == x; }. Hàm gọi hàm khác là chuyện rất bình thường. Kiểm tra ví dụ: 11, 22, …, 99 (9 số) và 101, 111, 121 (3 số), tổng là 12.Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
int daoNguoc(int x){
int d = 0;
while(x > 0){
d = d * 10 + x % 10;
x /= 10;
}
return d;
}
bool doiXung(int x){
return daoNguoc(x) == x;
}
int main(){
int a, b;
cin >> a >> b;
int dem = 0;
for(int x = a; x <= b; x++){
if(doiXung(x)) dem++;
}
cout << dem;
return 0;
}def dao_nguoc(x):
d = 0
while x > 0:
d = d * 10 + x % 10
x //= 10
return d
def doi_xung(x):
return dao_nguoc(x) == x
a, b = map(int, input().split())
print(sum(1 for x in range(a, b + 1) if doi_xung(x)))Nhập $T$ truy vấn, mỗi truy vấn gồm $a, b$ ($1 \le a \le b \le 10^5$, $T \le 10$). In ra số lượng số nguyên tố trong $[a, b]$.
2
1 10
10 204
4💡 Gợi ý
laNguyenTo ở phần 2, viết thêm hàm demNT(a, b) gọi nó. Đây là sức mạnh của hàm: viết đúng một lần, dùng mãi. Khi $T$ và $b$ lớn tới $10^6$ thì cách này sẽ chậm, các bạn sẽ học sàng Eratosthenes sau.Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
bool laNguyenTo(int x){
if(x < 2) return false;
for(int i = 2; i * i <= x; i++){
if(x % i == 0) return false;
}
return true;
}
int demNT(int a, int b){
int dem = 0;
for(int x = a; x <= b; x++){
if(laNguyenTo(x)) dem++;
}
return dem;
}
int main(){
int T;
cin >> T;
while(T--){
int a, b;
cin >> a >> b;
cout << demNT(a, b) << endl;
}
return 0;
}def la_nguyen_to(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
def dem_nt(a, b):
return sum(1 for x in range(a, b + 1) if la_nguyen_to(x))
T = int(input())
for _ in range(T):
a, b = map(int, input().split())
print(dem_nt(a, b))Dãy Fibonacci: $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$. Nhập $n$ ($n \le 90$), in $F_n$. Hãy viết cả 2 cách: đệ quy và vòng lặp, rồi thử với $n = 45$ để so tốc độ.
1055💡 Gợi ý
a, b, mỗi bước c = a + b; a = b; b = c;, chạy tức thì. Bài học: đệ quy đẹp nhưng không phải lúc nào cũng nhanh; cách khắc phục là đệ quy có nhớ.Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
long long fibDeQuy(int n){ // chậm khi n lớn
if(n <= 1) return n;
return fibDeQuy(n - 1) + fibDeQuy(n - 2);
}
long long fibLap(int n){ // nhanh
if(n <= 1) return n;
long long a = 0, b = 1;
for(int i = 2; i <= n; i++){
long long c = a + b;
a = b;
b = c;
}
return b;
}
int main(){
int n;
cin >> n;
cout << fibLap(n);
return 0;
}def fib_de_quy(n): # chậm khi n lớn
if n <= 1:
return n
return fib_de_quy(n - 1) + fib_de_quy(n - 2)
def fib_lap(n): # nhanh
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
n = int(input())
print(fib_lap(n))Nhập $a, n$ ($|a| \le 10$, $0 \le n \le 18$). Viết hàm đệ quy luyThua(a, n) tính $a^n$.
2 101024💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <iostream>
using namespace std;
long long luyThua(long long a, int n){
if(n == 0) return 1; // điểm dừng
long long nua = luyThua(a, n / 2); // lũy thừa nhanh
if(n % 2 == 0) return nua * nua;
return nua * nua * a;
}
int main(){
long long a;
int n;
cin >> a >> n;
cout << luyThua(a, n);
return 0;
}def luy_thua(a, n):
if n == 0:
return 1 # điểm dừng
nua = luy_thua(a, n // 2) # lũy thừa nhanh
if n % 2 == 0:
return nua * nua
return nua * nua * a
a, n = map(int, input().split())
print(luy_thua(a, n))
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét