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.
Chú ý:
Khi viết hàm đệ quy, cần xác định:
• Điều kiện dừng
• Trường hợp đệ quy
28 trang |
Chia sẻ: thuychi16 | Lượt xem: 838 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Giáo trình môn học Cấu trúc dữ liệu và giải thuật, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
G V : L Ê T H Ị N GỌC HẠN H
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
8/21/2015 Data structure & Algorithm
1
ĐÁNH GIÁ MÔN HỌC
Thang điểm: 10
Tỉ lệ điểm thành phần:
Chuyên cần : giữa kỳ : cuối kỳ
(1:3:6)
Đồ án miễn thi cuối kỳ: gồm 5 đồ án, mỗi
nhóm tối đa 2 thành viên. Nộp trước ngày
30/10/2014.
8/21/2015 Data structure & Algorithm 2
TÀI LIÊU THAM KHẢO
Giáo trình “Cấu trúc dữ liệu và giải thuật”,
Trần Hạnh Nhi, Dương Anh Đức, Nxb
ĐHQG TP. HCM.
Data Structures And Problem Solving Using
C++ , Mark Weiss, Florida International
University.
8/21/2015 Data structure & Algorithm 3
G V : L Ê T H Ị N GỌC HẠN H
ÔN TẬP
8/21/2015 Data structure & Algorithm
4
NỘI DUNG
8/21/2015 Data structure & Algorithm 5
Cấu trúc
Con trỏ
Đệ quy
1
2
3
1
2
3
ĐỆ QUY
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.
Chú ý:
Khi viết hàm đệ quy, cần xác định:
• Điều kiện dừng
• Trường hợp đệ quy
8/21/2015 Data structure & Algorithm 6
ĐỆ QUY – VÍ DỤ
Tính tổng S(n) = 1 + 2 + + n
Ta có:
S(n) = (1 + 2 + + n-1) + n
Trường hợp n>0:
S(n) = S(n-1) + n (điều kiện đệ quy)
Trường hợp n=0:
S(0) = 0 (điều kiện dừng)
8/21/2015 Data structure & Algorithm 7
ĐỆ QUY – VÍ DỤ
Tính tổng S(n) = 1 + 2 + + n
int Tong(int n)
{
if (n == 0)//điều kiện dừng
return 0;
return Tong(n-1) + n;
}
8/21/2015 Data structure & Algorithm 8
ĐỆ QUY – BÀI TẬP
1. Với a > 0, cho dãy số thực được cho theo
công thức truy hồi sau:
𝒙𝟎 = 1; 𝒙𝒏=
𝒙𝒏−𝟏
𝟐
+
𝒂
𝟐𝒙𝒏−𝟏
nếu n ≥ 1
2. Cho mảng một chiều các số nguyên. Viết
hàm tính tổng các số lẻ có trong mảng bằng
phương pháp đệ quy
8/21/2015 Data structure & Algorithm 9
CẤU TRÚC (STRUCT)
Cấu trúc là phương pháp/cách thức tập hợp
các thông tin dữ liệu khác nhau vào trong một
dữ liệu.
• Dễ dàng lưu trữ, truy cập, sử dụng.
• Định nghĩa thành kiểu dữ liệu riêng
Ví dụ:
NGAY gồm ngay (nguyên), thang (nguyên), nam
(nguyên)
SINHVIEN gồm mssv (chuỗi), hoten (chuỗi),
ngaysinh (NGAY), quequan (chuỗi)
8/21/2015 Data structure & Algorithm 10
CẤU TRÚC (STRUCT)
Thành phần của cấu trúc:
• Kiểu dữ liệu chuẩn.
• Kiểu cấu trúc khác.
• Sử dụng từ khóa struct.
• Sử dụng như một kiểu dữ liệu tự định
nghĩa.
8/21/2015 Data structure & Algorithm 11
STRUCT– KHAI BÁO
Cách 1:
struct
{
;
;
} , ;
Ví dụ:
struct DIEM
{
int x;
int y;
} diem1, diem2;
8/21/2015 Data structure & Algorithm 12
Cách 2:
struct
{
;
;
};
struct ;
Ví dụ:
struct DIEM
{
int x, y;
}; DIEM diem1, diem2;
STRUCT
Sử dụng:
;
Ví dụ:
NGAY NgayBatDau, NgayKetThuc;
8/21/2015 Data structure & Algorithm 13
STRUCT
Truy cập thành phần của cấu trúc:
NGAY ngaysinh;
ngaysinh.ngay = 10;
ngaysinh.thang = 1;
ngaysinh.nam = 1990;
SINHVIEN sv;
printf(“Ho ten sinh vien : %s”, sv.hoten);
8/21/2015 Data structure & Algorithm 14
BÀI TẬP
Định nghĩa kiểu dữ liệu thí sinh (THISINH) gồm các
thông tin: số báo danh (sbd), ngày sinh (ngaysinh), họ
tên (hoten), khối thi (khoithi), điểm môn thi 1 (mon1),
điểm môn thi 2 (mon2), điểm môn thi 3 (mon3), tổng
điểm thi (tongdiem).
Viết hàm nhập các thông tin của thí sinh.
Hàm xuất các thông tin của thí sinh.
Viết hàm tính tổng điểm thi của thí sinh.
Hàm xử lý: nếu tổng điểm thi trên 15 điểm và không có
điểm khống chế (2 điểm) thì thí sinh đó trúng tuyển,
ngược lại là không trúng tuyển.
Hàm main, xuất các thông tin của thí sinh đã nhập và
kết quả thi của thí sinh.
8/21/2015 Data structure & Algorithm 15
CON TRỎ (POINTER)
Địa chỉ trong bộ nhớ:
8/21/2015 Data structure & Algorithm 16
CON TRỎ (POINTER)
Địa chỉ trong bộ nhớ:
int X = 5;
8/21/2015 Data structure & Algorithm 17
Biến con trỏ: loại biến dùng để chứa địa chỉ.
Khai báo:
*;
8/21/2015 Data structure & Algorithm 18
CON TRỎ (POINTER)
Ví dụ:
int *a; /*con trỏ đến kiểu int*/
float *b; /*con trỏ đến kiểu float*/
NGAY *pNgay; /*con trỏ đến kiểu NGAY*/
SINHVIEN *pSV; /*con trỏ đến kiểu
SINHVIEN*/
8/21/2015 Data structure & Algorithm 19
CON TRỎ (POINTER)
Lưu ý:
• Xác định địa chỉ ô nhớ: toán tử &
• Xác định giá trị của ô nhớ tại địa chỉ trong
biến con trỏ: toán tử *
• Truy cập thành phần trong cấu trúc:
8/21/2015 Data structure & Algorithm 20
CON TRỎ (POINTER)
Ví dụ:
int i;
int *p;
p = &i;
int j;
j = *p;
int day = pNgay->ngay;
8/21/2015 Data structure & Algorithm 21
CON TRỎ - VÍ DỤ
CON TRỎ - VÍ DỤ
#include
int main()
{
int i,j;
int *p;
p = &i;
*p = 5;
j = i;
printf("%d %d %d\n", i, j, *p);
return 0;
}
8/21/2015 Data structure & Algorithm 22
CÁC CẤU TRÚC ĐIỀU KHIỂN
Cấu trúc lựa chọn thực hiện lệnh theo tình
huống:
If; if else; switch .
8/21/2015 Windows Programming 23
CÁC CẤU TRÚC ĐIỀU KHIỂN
8/21/2015 Windows Programming 24
CÁC CẤU TRÚC ĐIỀU KHIỂN
Viết chương trình nhập vào năm dương
lịch (từ 1975 trở đi) và in ra các giải thể
thao lớn được tổ chức trong năm đó. Biết
rằng:
Các năm chia hết cho 4 có tổ chức
Olympic và các giải bóng Châu Âu
Các năm chia 4 dư 2 có tổ chức WorldCup
Các năm lẻ và cũng là các năm chia 4 dư 1
hoặc dư 3 thì tổ chức Sea Games
8/21/2015 Windows Programming 25
CÁC CẤU TRÚC ĐIỀU KHIỂN TRONG
C#
Các cấu trúc lặp để thực thi lệnh theo chu
kỳ:
For ; dowhile; while
8/21/2015 Windows Programming 26
CÁC CẤU TRÚC ĐIỀU KHIỂN
8/21/2015 Windows Programming 27
BÀI TẬP
Định nghĩa kiểu dữ liệu thí sinh (THISINH) gồm các
thông tin: số báo danh (sbd), ngày sinh (ngaysinh), họ tên
(hoten), khối thi (khoithi), điểm môn thi 1 (mon1), điểm
môn thi 2 (mon2), điểm môn thi 3 (mon3), tổng điểm thi
(tongdiem).
Viết hàm nhập các thông tin của thí sinh.
Hàm xuất các thông tin của thí sinh.
Viết hàm tính tổng điểm thi của thí sinh.
Hàm xử lý: nếu tổng điểm thi trên 15 điểm và không có
điểm khống chế (2 điểm) thì thí sinh đó trúng tuyển,
ngược lại là không trúng tuyển.
Hàm main, xuất các thông tin của thí sinh đã nhập và kết
quả thi của thí sinh.
8/21/2015 Data structure & Algorithm 28