nguyenthanhanh_nguyenthanhanh
New Member
Download miễn phí Bài giảng Kỹ thuật lập trình - HUT
Đệquy là phương pháp giúp chúng ta tìm giải thuật cho các bài toán
khó . Giải thuật giải bài toán bằng đệquy thường rất đẹp (gọn gàng,
dễhiểu ,dễchuyển thành chương trình trên các NNLT).
•Nhưng như đã chỉra ởtrên việc xửlý giải thuật đệquy lại thường
gây khó khăn cho máy tính (tốn không gian nhớvà thời gian xửlý.
•Một cách tổng quát người ta đã chỉra rằng : Mọi giải thuật đệquy
đều có thểthay thếbằng một giải thuật không đệquy.
•Sơ đồ đểxây dựng chương trình cho một bài toán khó khi ta không
tìm được giải thuật không đệquy thường là :
– Dùng quan niệm đệquy đểtìm giải thuật cho bài toán .
– Mã hóa giải thuật đệquy .
–Khử đệquy đểcó được một chương trình không đệquy .
• Tuy nhiên do việc khử đệquy không phải bao giờcũng dễvà vì vậy
trong nhiều trường hợp ta cũng phải chấp nhận sưdụng chương trình
đệquy
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ố…Tên biến nên mô tả được ý nghĩa của nó
Tránh dùng các ký tự gây lầm lẫn
Nên áp dụng các quy ước đặt tên biến chuẩn khi
lập trình
Kiểu dữ liệu cơ bản
voidchardouble
Kiểu dữ liệu cơ bản
floatint
Những kiểu dữ liệu dẫn xuất
intshort short int(chiếm ít bộ nhớ hơn int)
Kiểu dữ liệu dẫn xuấtKiểu dữ liệu
cơ bản
Bộ bổ từ (Modifiers)
kiểu dữ liệu
int unsigned int(chỉ là số dương)unsigned
int/double
Long int /longdouble
(chiếm nhiều bộ nhớ hơn
int/double)
long
Kiểu dữ liệu & phạm vi giá trị
Kiểu Dung lượng
tính bằng bit
Phạm vi
char 8 -128 tới 127
Unsigned char 8 0 tới 255
signed char 8 -128 tới 127
int 16 -32,768 tới 32,767
unsigned int 16 0 tới 65,535
signed int 16 Giống như kiểu int
short int 16 Giống như kiểu int
unsigned short int 16 0 tới 65, 535
Biểu thức (Expressions)
Sự kết hợp các toán tử và các toán hạng
Toán hạng
Toán Tử
Ví dụ: 2 * y + 5
Toán tử gán
Toán tử gán (=) có thể được dùng với bất kỳ
biểu thức C hợp lệ nào
(Giá trị trái) (Giá trị phải)
(Tên biến) (Biểu thức)
(Toán tử gán)
Bốn Kiểu Toán Tử
Số học
(Arithmetic)
Quan hệ
(Relational)
Logic
(Logical)
Nhị phân
(Bitwise)
Vào ra trong C
#include
• Đây là câu lệnh tiền xử lý
stdio.h là tập tin header (header file)
Chứa các macro sử dụng cho nhiều
hàm nhập/xuất trong C
Các macro trong stdio.h giúp các hàm
printf(), scanf(), putchar(), getchar()
thực thi
Các cấu trúc điều khiển
• Rẽ nhánh
– If
– switch
• Lặp
– For
– While
– Do …While
Lệnh IF
• if (expression)
statement;
else
statement;
Lệnh switch
Vòng lặp For
Cú pháp:
for (initialize counter; conditional test; re-evaluation parameter)
{
statement
}
initialize counter là một lệnh gán để khởi tạo biến điều
khiển của vòng lặp trước khi đi vào vòng lặp
conditional test là một biểu thức quan hệ để chỉ định
khi nào vòng lặp sẽ kết thúc
• re-evaluation parameter định nghĩa cách thức thay đổi
của biến điều khiển vòng lặp mỗi khi vòng lặp được
thực thi
Vòng lặp While
while (condition is true)
statement ;
Cú pháp
Vòng lặp while lặp lại các lệnh
trong khi một biểu thức điều kiện
mang giá trị True
Vòng lặp Do…While
Trong vòng lặp do while phần thân của vòng lặp
được thực thi trước khi biểu thức điều kiện được kiểm
tra
Khi điều kiện mang giá trị False, vòng lặp do while
sẽ được kết thúc, và điều khiển chuyển đến lệnh xuất
hiện ngay sau lệnh while
• Cú pháp
do{
statement;
} while (condition);
Mảng
• Danh sách các phần tử có kiểu giống
nhau
• Khai báo
– [Kiểu dữ liệu] [Tên mảng][số lượng phần
tử]
– Ví dụ:
• char a[10];
• a[5]
• a+5
Contrỏ
Chương II: Đệ qui
• 1. Mô tả đệ qui
• 2. Bài toán đệ qui
• 3. Khử đệ qui
1. Mô tả đệ qui
• 1.1 Khái niệm về đệ qui
• 1.2 Các loại đệ qui
• 1.3 Mô tả đệ qui các cấu trúc dữ liệu
• 1.4 Mô tả đệ qui các giải thuật
• 1.5 Các dạng đệ qui đơn giản thường
gặp
1.1 Khái niệm về đệ qui
• Mô tả mang tính đệ qui về một đối
tượng là mô tả theo cách phân tích đối
tượng thành nhiều thành phần mà
trong số các thành phần có thành phần
mang tính chất của chính đối tượng
được mô tả.
• Tức là mô tả đối tượng qua chính nó.
1.1 Khái niệm về đệ qui
• Mô tả đệ quy tập số tự nhiên N :
– Số 1 là số tự nhiên ( 1 - N).
– Số tự nhiên bằng số tự nhiên cộng 1.
• Mô tả đệ quy cấu trúc ds(list) kiểu T :
– Cấu trúc rỗng là một ds kiểu T.
– Ghép nối một thành phần kiểu T(nút kiểu
T ) với một ds kiểu T ta có một ds kiểu T.
• Mô tả đệ quy cây gia phả : Gia phả
của một người bao gồm người đó và
gia phả của cha và gia phả của mẹ.
1.1 Khái niệm về đệ qui
• Mô tả đệ quy thủ tục sắp tăng dãy
• a[m] ( dãy a[m], a[m+1], . . . , a[n] )
bằng phương pháp Sort_Merge (SM):
• SM (a[m]) ≡Merge ( SM(a[m :
(n+m) div 2]) , SM (a[(n+m) div 2 +1
: n] )
– Với : SM (a[x : x]) là thao tác rỗng
(không làm gì cả ).
– Merge (a[x : y] , a[(y+1) : z]) là thủ tục
trộn 2 dãy tăng a [x : y] , a[(y+1) : z] để
được một dãy a[x : z] tăng.
1.1 Khái niệm về đệ qui
• Mô tả đệ qui hàm giai thừa
– 0!=1
– F(n)=n*F(n-1)
• Ưu điểm của phương pháp mô tả đệ
qui
– Mô tả tập lớn tác đối tượng chỉ qua một
vài mệnh đề
– Mô tả một bài toán lớn chỉ qua một số ít
thao tác
1.1 Khái niệm về đệ qui
• Mô tả đệ qui gồm hai phần
– Phần neo:trường hợp suy biến của đối
tượng
• Ví dụ: 1 là số tự nhiên, cấu trúc rỗng là ds
kiểu T, 0 ! = 1 , SM (a[x]) là thao tác rỗng.
– Phần quy nạp: mô tả đối tượng (giải
thuật) thông qua chính đối tượng (giải
thuật ) đó một cách trực tiếp hay gián
tiếp.
• Ví dụ:
n! = n * (n – 1) !
SM (a[m]) ≡ Merge (SM (a[m
m+n) div 2] , SM (a[(m+n) div 2 +1 : n]) )
1.2 Các loại đệ qui
• Gồm hai loại
– Đệ qui trực tiếp
– Đệ qui gián tiếp
1.2 Các loại đệ qui
• Đệ quy trực tiếp là loại đệ quy mà
đối tượng được mô tả trực tiếp qua nó
– A mô tả qua A, B, C,...trong đó B, C, ...
không chứa A.
• Đệ quy gián tiếp là loại đệ quy mà
đối tượng được mô tả gián tiếp qua nó
– A mô tả qua A1 ,A2 ,..., An .Trong đó có
một Ai được mô tả qua A.
1.3 Mô tả đệ qui các cấu trúc dữ liệu
• Cấu trúc dữ liệu có tính đệ quy thường gồm một
số thành phần dữ liệu cùng kiểu được ghép nối
theo cùng một cách
• Ví dụ :
– Mô tả đệ quy cây nhi phân :Cây nhi phân kiểu T
• hay là một cấu trúc rỗng (phần neo).
• hay là một nút kiểu T (nút gốc) và 2 cây nhị phân kiểu T rời
nhau (cây con nhị phân phải, cây con nhị phân trái) kết hợp
với nhau .
– Mô tả đệ quy mảng nhiều chiều :
• Mảng một chiều là dãy có thứ tự các thành phần cùng kiểu .
• Mảng n chiều là mảng 1 chiều mà các thành phần có kiểu
mảng n-1 chiều .
1.4 Mô tả đệ qui các giải thuật
• Giải thuật đệ qui
– Giải thuật đệ quy là giải thuật có chứa thao tác gọi đến nó
– Đặc điểm: mô tả một dãy lớn các thao tác bằng một số ít các thao
tác trong đó có chứa thao tác gọi lại giải thuật (gọi đệ quy)
– Biểu diễn giải thuật đệ qui
• P Ù P[ S , P ]
• Điều kiện dừng
– Biểu diễn tổng quát
• P Ù if B then P[ S , P ]
• hay P Ù P[ S , if B then P ]
• Chương trình con đệ qui
– Hàm đệ qui
– Thủ tục đệ qui
1.4 Mô tả đệ qui các giải thuật
• Dãy các giai thừa : { n! } ? 1 ,1 , 2 , 6 , 24 , 120 . . .
– Ký hiệu FAC(n ) = n ! .
• FAC(0 ) = 1 ; ( 0 ! = 1 )
• FAC(n ) = n * FAC(n - 1 ) ; ( n ! = n * (n - 1 ) ! ) với n >= 1
• Giải thuật đệ quy tính FAC(n ) là :
– FAC(n )
– if (n = 0 ) then return 1 ;
– else return (n * FAC(n - 1 )) ;
1.4 Mô tả đệ qui các giải thuật
• Dãy số Fibonaci(FIBO) :{ FIBO (n) } ≡ 1 ,1 , 2 ,
3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , .
. .
– FIBO(0 ) = FIBO (1 ) = 1 ;
– FIBO(n ) = FIBO (n - 1 ) + FIBO ( n - 2 ) ; với n > = 2
• Giải thuật đệ quy tính FIBO ( n ) là :
– FIBO(n)
– if ((n = 0 ) or ( n = 1 )) then return 1 ;
– else return ( FIBO (n - 1) + FIBO (n - 2)) ;
1.5 Các dạng đệ qui đơn giản thường gặp
• Đệ qui tuyến tính: là dạng đệ qui trực tiếp đơn giản
nhất có dạng
– P Ù {
– If (B) thực hiện S;
– else { thực hiện S* ; gọi P }
– }
Với S , S* là các thao tác không đệ quy .
Ví dụ:...