Tài liệu hướng dẫn thực hành môn Nhập môn lập trình - Tuần 10
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HCM
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ PHẦN MỀM
HỆ CHÍNH QUI
MÔN: NHẬP MÔN LẬP TRÌNH
GVLT: ThS. PHẠM MINH TUẤN
HDTH TUẦN 10
PHẠM TÚ SAN
TRẦN NGỌC HIỆU
TP.HCM, tháng 01 năm 2013
ptsan/[email protected]n
1 Mục tiêu
Lập trình đệ quy
2 Nội dung
Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó
một cách tường minh hay tiềm ẩn
Khi viết hàm đệ quy, cần xác định:
- Điều kiện dừng
- Công thức đệ quy
Ví dụ:
Tính tổng S(n) = 1 + 2 + … + n
Ta có
S(n) = (1 + 2 + … + n-1) + n
hay S(n) = S(n-1) + n (công thức đệ quy)
S(0) = 0
(điều kiện dừng)
Ta có chương trình tương ứng với công thức đệ quy trên như sau:
int Tong(int n )
{
if (n == 0)
return 0;
return Tong(n-1) + n;
}
Mã nguồn minh họa
#include <stdio.h>
int Tong(int* a, int n)
Trang 2
ptsan/[email protected]n
{
if ( n == 0)
return a[0];
return Tong(a, n-1) + a[n];
}
void main()
{
int n;
printf("Nhap n: ");
scanf("%d", &n);
int a[100];
for (int i = 0; i < n; i++)
{
printf("Nhap a[%d] = ",i);
scanf("%d",&a[i]);
}
printf("%d\n",Tong(a, n-1));
}
3 Bài tập
1. Nhập một mảng gồm N số nguyên. Sử dụng đệ quy tính tổng N số nguyên đó.
Nhập: [1, 5, 0, 6] Xuất: S = 12
2. Nhập một mảng gồm số N số nguyên. Sử dụng đệ quy kiểm tra xem có phải là
mảng tăng dần. Nhập: [0, 1, 5, 6] Xuất: Tăng dần
x3 x5
x2n1
n
3. Nhập n. Tính S x
... 1
3! 5!
2n 1 !
4. Cho n số tự nhiên x1, x2,…, xn. Hãy tìm UCLN (x1, x2,…,xn) bằng cách sử dụng:
UCLN(x1,x2,…,xn)= UCLN(UCLN(x1,x2,…,x(n-1)),xn)
5. Bài toán mã đi tuần hoặc bài toán 8 quân hậu
6. Tìm tất cả các hoán vị của một mảng có n phần tử
7. Dãy Fibonacci
Trang 3
3 trang
21300
Free
Bạn đang xem tài liệu "Tài liệu hướng dẫn thực hành môn Nhập môn lập trình - Tuần 10", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tai_lieu_huong_dan_thuc_hanh_mon_nhap_mon_lap_trinh_tuan_10.pdf
