Kỹ thuật lập trình Bài 2 – Chương trình con và đệ quy
Ngô Hữu Dũng
31
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
// Khai báo prototype
Input
Chương trình con
1. #include
2. int cong(int,int);
3. void main()
4. {
5.
6.
7.
int a = 5, b, c; b = cong(a, 3); c = cong(3,cong(a,b)); printf("Tong la %d",cong(b,c));
FUNCTION
// Hàm chi tiết
Output
return x + y;
32
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
8. 9. } 10. int cong(int x, int y) 11. { 12. 13. }
Main()
Function1()
Thành phần Kiểu trả về của hàm Tên hàm Tham số
Tham biến Tham trị
Function3()
Function2()
Function4()
Lệnh return trả về giá trị cho hàm Khai báo prototype Gọi hàm Phạm vi của biến
Return-type function-name(argument declarations) {
declarations and statements
}
33
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Kiểu trả về của hàm
Hàm có thể trả về một giá trị
1. int cong(int x, int y) 2. {
return x + y;
int float char …
3. 4. }
void: Không trả về giá trị
1. float nhan(int x, int y) 2. {
return x * y;
Khi kết thúc, hàm sẽ mang một giá trị trừ trường hợp hàm mang kiểu void.
3. 4. }
1. void in(char line[]) 2. {
printf("%s",line);
34
Ngô Hữu Dũng
3. 4. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Tên hàm và tham số
1. int cong(int x, int y) 2. {
return x + y;
3. 4. }
1. float nhan(int x, int y) 2. {
return x * y;
Tên hàm do người lập trình đặt Không được trùng với từ khóa Các ký tự liên tiếp nhau Gồm ký tự, số, dấu gạch chân Không gồm các ký tự đặc biệt Có nghĩa, dễ hiểu Tham số (đối số)
Một, nhiều hoặc không có tham số Mỗi tham số đều có kiểu dữ liệu Các tham số có thể được dùng như
3. 4. }
một biến cục bộ trong hàm.
1. void in(char line[]) 2. {
printf("%s",line);
35
Ngô Hữu Dũng
3. 4. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Giá trị trả về
Hàm return trả về giá trị cho hàm
Đồng thời kết thúc hàm
1. int cong(int x, int y) 2. {
return x + y;
Cú pháp: return
3. 4. }
1. float nhan(int x, int y) 2. {
return x * y;
Kiểu dữ liệu của
3. 4. }
Hàm void không có giá trị trả về Không dùng lệnh return (Ví dụ 3)
1. void in(char line[]) 2. {
printf("%s",line);
36
Ngô Hữu Dũng
3. 4. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Khai báo prototype
1. int cong(int x, int y) 2. {
return x + y;
3. 4. }
1. int cong(int, int); 2. float nhan(int, int); 3. void in(char);
Prototype: Khai báo các hàm dùng
1. float nhan(int x, int y) 2. {
return x * y;
trong chương trình Kiểu trả về Tên hàm Danh sách tham số (nếu có) Dấu chấm phẩy ;
3. 4. }
Đầu chương trình hoặc trong file
1. void in(char line[]) 2. {
printf("%s",line);
header (*.h)
37
Ngô Hữu Dũng
3. 4. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Gọi hàm
Lệnh gọi hàm Tên hàm Danh sách tham số (nếu có)
Theo thứ tự Cùng kiểu dữ liệu
1. #include
6.
Hàm có thể trả về một giá trị có kiểu
7.
int a = 5, b, c; b = cong(a, 3); c = b + cong(a,b); printf("Tong: %d", c);
của kiểu trả về của hàm.
return x + y;
38
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
8. 9. } 10. int cong(int x, int y) 11. { 12. 13. }
Phạm vi của biến (1)
// Biến toàn cục
1. #include
2. float b = 9;
3. void half(float a)
4. {
5.
6.
// Biến cục bộ trong hàm half // Biến toàn cục
a = a / 2; b = b / 2; printf("a = %f, b = %f\n", a, b);
7. 8. } 9. void main() 10. { 11.
12.
// Biến cục bộ // Gọi hàm half
float a = 15; half(a); printf("a = %f, b = %f\n", a, b);
13. 14. }
39
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Phạm vi của biến (2)
// Biến toàn cục
1. #include
2. float x = 5, y = 6;
3. void nhandoi(float x)
4. {
5.
6.
// Biến cục bộ // Biến toàn cục
x = x * 2; y = y * 2; printf("x = %f, y = %f\n", x, y);
7. 8. } 9. void main() 10. { 11.
12.
// Biến cục bộ // Gọi hàm nhandoi
float y = 7; nhandoi(x); printf("x = %f, y = %f\n", x, y);
13. 14. }
40
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Phạm vi của biến (3)
1. #include
// Phạm vi hàm main
5.
6.
int x = 5; if (x) {
7.
// Phạm vi lệnh if
8.
9.
int x = 10; x++; printf("x = %d\n",x);
10.
11.
} x++; printf("x = %d\n",x);
41
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12. 13. }
Ví dụ - Số nguyên tố
Các thành phần của hàm?
1. int ngto(int a) 2. {
3.
4.
int i;
for (i=2;i
?
?
?
?
5.
if (a%i==0) return 0;
Ý nghĩa của hàm và các câu
return 1;
6.
7. }
lệnh?
?
?
?
42
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
// Hàm kiểm tra số nguyên tố
Ví dụ - Số nguyên tố (tt)
1. #include
2. int ngto(int a)
3. {
4.
5.
int i;
for (i=2;i
6.
if (a%i==0) return 0;
// Nếu chia chẵn
// Không có giá trị nào chia chẵn
return 1;
7.
8. }
9. void main()
10. {
11.
12.
int n; printf("Nhap n: "); scanf("%d",&n);
// Nếu ngto(n) khác zero
if (ngto(n))
13.
printf("%d la so nguyen to.",n);
14.
else
// Nếu ngto(n) bằng zero
printf("%d khong phai la so nguyen to.",n);
15.
16. }
43
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ - Sắp xếp chọn
1. void selectionsort(int a[], int n)
2. {
3.
4.
5.
int i, j, min;
for (i = 0; i<=n-1; i++)
{
6.
7.
8.
9.
min = i;
for (j = i+1; j <= n-1; j++)
if (a[j] < a[min])
min = j;
10.
hoanvi(&a[i], &a[min]);
}
44
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11.
12. }
Ví dụ - Sắp xếp nổi bọt
1. void bubblesort(int a[], int n)
2. {
3.
4.
5.
int i,j;
for (i=0;i<=n-1;i++)
{
6.
7.
for (j=0;j<=n-2-i;j++)
{
8.
if (a[j]>a[j+1])
9.
swap(a[j], a[j+1]);
10.
}
}
45
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11.
12. }
Ví dụ - Sắp xếp chèn
1. void insertionsort(int a[], int n)
2. {
3.
4.
5.
int i,j, value;
for (i=1; i
6.
7.
8.
value = a[i];
for (j=i; j>0 && value
9.
a[j] = a[j-1];
10.
11.
}
a[j]= value;
}
46
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Ví dụ - Tìm kiếm tuần tự
1. int search (int a[], int n, int key)
2. {
3.
4.
5.
int i;
for (i=0; i
6.
if (a[i] == key)
7.
return i;
8.
}
return -1;
9.
10. }
47
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Ví dụ - Tìm kiếm nhị phân
1. int bsearch(int a[], int low, int high, int key)
2. {
3.
4.
5.
6.
7.
int mid;
if (low > high)
return -1;
mid = (low + high)/2;
if (key == a[mid])
8.
9.
return mid;
else if (key < a[mid])
10.
return bsearch(a, low, mid-1, key);
11.
else
return bsearch(a, mid+1, high, key);
48
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Quy nạp toán học
Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.
Phương pháp quy nạp:
Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng
Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.
Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + …+ (2n-1) = n2 (*), với n ≥ 1
Bước cơ sở: Trường hợp n = 1, (2n-1) = n2 = 1 là đúng hiển nhiên.
Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2
Khi đó S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1)
= (k + 1)2
Vậy S(k + 1) đúng S(n) đúng với mọi n ≥ 1.
49
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Lập trình đệ quy
Lập trình tính S(n) = 1 + 3 + 5 + … + (2n – 1) = n2 với n bất kỳ, n ≥ 1.
Từ bài toán quy nạp ta có:
Bước cơ sở: S(1) = 1
Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1]
Phương pháp lập trình đệ quy:
Phần cơ sở: S(1) = 1
Phần đệ quy: S(n) = S(n – 1) + (2n – 1)
Áp dụng vào lập trình:
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
50
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hàm đệ quy
Là hàm có phép gọi lại chính nó
Áp dụng cho những bài toán có tính chất quy nạp
Gồm hai phần cơ bản
Phần cơ sở: Trường hợp ban đầu, hiển nhiên.
Phần đệ quy: Có phép gọi lại hàm.
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
51
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hoạt động?
1.
2.
int S(int n)
{
3.
// Gọi hàm S(4)
Giả sử n = 5, hàm đệ quy chạy như sau:
S(5) = S(4) + 9
4.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
5.
}
// Gọi hàm S(3)
S(4) = S(3) + 7
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
// Return S(1)
S(2) = S(1) + 3
S(1) = 1
S(2) = 1 + 3 // Return S(2)
// Return S(3)
S(3) = 1 + 3 + 5
// Return S(4)
S(4) = 1 + 3 + 5 + 7
// Return S(5)
S(5) = 1 + 3 + 5 + 7 + 9 = 25
52
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa
Exponent
53
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa (tt)
Viết hàm đệ quy tính E(n) = an với a R, a ≠ 0, n N và n ≥ 0.
Phép quy nạp
Bước cơ sở: E(0) = a0 = 1
Bước quy nạp: E(k+1) = a x E(k)
1. float E(float a, int n)
2. {
3.
if (n==0) return 1;
else return a * E(a,n-1);
Hàm đệ quy:
E(4) = 2*E(3)
E(3) = 2*E(2)
E(2) = 2*E(1)
Phần cơ sở: E(0) = 1
Phần đệ quy: E(n) = a x E(n-1)
E(1) = 2*E(0)
E(0) = 1
E(1) = 2
Hoạt động:
E(2) = 2*2
Giả sử a = 2, n = 4
E(3) = 2*2*2
E(4) = 2*2*2*2 = 24
54
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Giai thừa
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
Bước cơ sở: ???
Bước quy nạp: ???
Chứng minh: ???
Hàm đệ quy
Phần cơ sở: ???
Phần đệ quy: ???
Hoạt động: ???
55
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Giai thừa (tt)
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
1. int F(int n)
2. {
3.
if (n==1) return 1;
else return n * F(n-1);
Bước cơ sở: F(1) = 1
Bước quy nạp: F(k+1) = (k+1) x F(k)
Chứng minh:
Giả sử F(k) = k!
Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!)
F(4) = 4*F(3)
F(3) = 3*F(2)
Hàm đệ quy
F(2) = 2*F(1)
F(1) = 1
E(2) = 2*1
Phần cơ sở: F(1) = 1
Phần đệ quy: F(n) = n * F(n-1)
E(3) = 3*2*1
E(4) = 4*3*2*1 = 16
Hoạt động: Cho n = 4
56
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Dãy số Fibonacci
Viết hàm đệ quy tính Fib(n) là phần tử thứ n của dãy số Fibonacci
Dãy Fibonaci: 1 1 2 3 5 8 13 21 34 55…
Tính chất: Số sau bằng tổng hai số liền trước nó.
Quy nạp
Fib(1) = 1, Fib(2) = 1
Fib(k) = Fib(k-1) + Fib(k-2)
Hàm đệ quy ?
Phần cơ sở: ?
Phần đệ quy: ?
57
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Dãy số Fibonacci (tt)
1. // Fibonacci: 1 1 2 3 5 8 13 21 34 55...
2. #include
3. int fib(int n) // Tìm số Fibonacci thứ n
4. {
5.
if (n==1 || n==2) return 1;
return fib(n-1) + fib(n-2);
// Phần cơ sở
// Phần đệ quy
6.
7. }
8. void main()
9. {
10.
11.
int n;
do{
// Nhập n>=1
12.
scanf("%d",&n);
13.
}while(n<1);
printf("Fibinaci(%d) = %d.", n, fib(n));
14.
15. }
58
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Bài toán Tháp Hanoi
59
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Hết bài 2
Chương trình con
Ví dụ vận dụng chương trình con
Phép quy nạp
Giải thuật đệ quy
Ví dụ vận dụng giải thuật đệ quy
60
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
? ? ? ?
5.
if (a%i==0) return 0;
Ý nghĩa của hàm và các câu
return 1;
6. 7. }
lệnh? ? ? ?
42
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
// Hàm kiểm tra số nguyên tố
Ví dụ - Số nguyên tố (tt)
1. #include
2. int ngto(int a)
3. {
4.
5.
int i;
for (i=2;i
6.
if (a%i==0) return 0;
// Nếu chia chẵn
// Không có giá trị nào chia chẵn
return 1;
7.
8. }
9. void main()
10. {
11.
12.
int n; printf("Nhap n: "); scanf("%d",&n);
// Nếu ngto(n) khác zero
if (ngto(n))
13.
printf("%d la so nguyen to.",n);
14.
else
// Nếu ngto(n) bằng zero
printf("%d khong phai la so nguyen to.",n);
15.
16. }
43
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ - Sắp xếp chọn
1. void selectionsort(int a[], int n)
2. {
3.
4.
5.
int i, j, min;
for (i = 0; i<=n-1; i++)
{
6.
7.
8.
9.
min = i;
for (j = i+1; j <= n-1; j++)
if (a[j] < a[min])
min = j;
10.
hoanvi(&a[i], &a[min]);
}
44
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11.
12. }
Ví dụ - Sắp xếp nổi bọt
1. void bubblesort(int a[], int n)
2. {
3.
4.
5.
int i,j;
for (i=0;i<=n-1;i++)
{
6.
7.
for (j=0;j<=n-2-i;j++)
{
8.
if (a[j]>a[j+1])
9.
swap(a[j], a[j+1]);
10.
}
}
45
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11.
12. }
Ví dụ - Sắp xếp chèn
1. void insertionsort(int a[], int n)
2. {
3.
4.
5.
int i,j, value;
for (i=1; i
6.
7.
8.
value = a[i];
for (j=i; j>0 && value
9.
a[j] = a[j-1];
10.
11.
}
a[j]= value;
}
46
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Ví dụ - Tìm kiếm tuần tự
1. int search (int a[], int n, int key)
2. {
3.
4.
5.
int i;
for (i=0; i
6.
if (a[i] == key)
7.
return i;
8.
}
return -1;
9.
10. }
47
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Ví dụ - Tìm kiếm nhị phân
1. int bsearch(int a[], int low, int high, int key)
2. {
3.
4.
5.
6.
7.
int mid;
if (low > high)
return -1;
mid = (low + high)/2;
if (key == a[mid])
8.
9.
return mid;
else if (key < a[mid])
10.
return bsearch(a, low, mid-1, key);
11.
else
return bsearch(a, mid+1, high, key);
48
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Quy nạp toán học
Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.
Phương pháp quy nạp:
Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng
Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.
Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + …+ (2n-1) = n2 (*), với n ≥ 1
Bước cơ sở: Trường hợp n = 1, (2n-1) = n2 = 1 là đúng hiển nhiên.
Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2
Khi đó S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1)
= (k + 1)2
Vậy S(k + 1) đúng S(n) đúng với mọi n ≥ 1.
49
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Lập trình đệ quy
Lập trình tính S(n) = 1 + 3 + 5 + … + (2n – 1) = n2 với n bất kỳ, n ≥ 1.
Từ bài toán quy nạp ta có:
Bước cơ sở: S(1) = 1
Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1]
Phương pháp lập trình đệ quy:
Phần cơ sở: S(1) = 1
Phần đệ quy: S(n) = S(n – 1) + (2n – 1)
Áp dụng vào lập trình:
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
50
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hàm đệ quy
Là hàm có phép gọi lại chính nó
Áp dụng cho những bài toán có tính chất quy nạp
Gồm hai phần cơ bản
Phần cơ sở: Trường hợp ban đầu, hiển nhiên.
Phần đệ quy: Có phép gọi lại hàm.
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
51
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hoạt động?
1.
2.
int S(int n)
{
3.
// Gọi hàm S(4)
Giả sử n = 5, hàm đệ quy chạy như sau:
S(5) = S(4) + 9
4.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
5.
}
// Gọi hàm S(3)
S(4) = S(3) + 7
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
// Return S(1)
S(2) = S(1) + 3
S(1) = 1
S(2) = 1 + 3 // Return S(2)
// Return S(3)
S(3) = 1 + 3 + 5
// Return S(4)
S(4) = 1 + 3 + 5 + 7
// Return S(5)
S(5) = 1 + 3 + 5 + 7 + 9 = 25
52
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa
Exponent
53
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa (tt)
Viết hàm đệ quy tính E(n) = an với a R, a ≠ 0, n N và n ≥ 0.
Phép quy nạp
Bước cơ sở: E(0) = a0 = 1
Bước quy nạp: E(k+1) = a x E(k)
1. float E(float a, int n)
2. {
3.
if (n==0) return 1;
else return a * E(a,n-1);
Hàm đệ quy:
E(4) = 2*E(3)
E(3) = 2*E(2)
E(2) = 2*E(1)
Phần cơ sở: E(0) = 1
Phần đệ quy: E(n) = a x E(n-1)
E(1) = 2*E(0)
E(0) = 1
E(1) = 2
Hoạt động:
E(2) = 2*2
Giả sử a = 2, n = 4
E(3) = 2*2*2
E(4) = 2*2*2*2 = 24
54
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Giai thừa
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
Bước cơ sở: ???
Bước quy nạp: ???
Chứng minh: ???
Hàm đệ quy
Phần cơ sở: ???
Phần đệ quy: ???
Hoạt động: ???
55
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Giai thừa (tt)
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
1. int F(int n)
2. {
3.
if (n==1) return 1;
else return n * F(n-1);
Bước cơ sở: F(1) = 1
Bước quy nạp: F(k+1) = (k+1) x F(k)
Chứng minh:
Giả sử F(k) = k!
Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!)
F(4) = 4*F(3)
F(3) = 3*F(2)
Hàm đệ quy
F(2) = 2*F(1)
F(1) = 1
E(2) = 2*1
Phần cơ sở: F(1) = 1
Phần đệ quy: F(n) = n * F(n-1)
E(3) = 3*2*1
E(4) = 4*3*2*1 = 16
Hoạt động: Cho n = 4
56
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Dãy số Fibonacci
Viết hàm đệ quy tính Fib(n) là phần tử thứ n của dãy số Fibonacci
Dãy Fibonaci: 1 1 2 3 5 8 13 21 34 55…
Tính chất: Số sau bằng tổng hai số liền trước nó.
Quy nạp
Fib(1) = 1, Fib(2) = 1
Fib(k) = Fib(k-1) + Fib(k-2)
Hàm đệ quy ?
Phần cơ sở: ?
Phần đệ quy: ?
57
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Dãy số Fibonacci (tt)
1. // Fibonacci: 1 1 2 3 5 8 13 21 34 55...
2. #include
3. int fib(int n) // Tìm số Fibonacci thứ n
4. {
5.
if (n==1 || n==2) return 1;
return fib(n-1) + fib(n-2);
// Phần cơ sở
// Phần đệ quy
6.
7. }
8. void main()
9. {
10.
11.
int n;
do{
// Nhập n>=1
12.
scanf("%d",&n);
13.
}while(n<1);
printf("Fibinaci(%d) = %d.", n, fib(n));
14.
15. }
58
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Bài toán Tháp Hanoi
59
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Hết bài 2
Chương trình con
Ví dụ vận dụng chương trình con
Phép quy nạp
Giải thuật đệ quy
Ví dụ vận dụng giải thuật đệ quy
60
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
6.
if (a%i==0) return 0;
// Nếu chia chẵn
// Không có giá trị nào chia chẵn
return 1;
7. 8. } 9. void main() 10. { 11.
12.
int n; printf("Nhap n: "); scanf("%d",&n); // Nếu ngto(n) khác zero if (ngto(n))
13.
printf("%d la so nguyen to.",n);
14.
else
// Nếu ngto(n) bằng zero
printf("%d khong phai la so nguyen to.",n);
15. 16. }
43
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ - Sắp xếp chọn
1. void selectionsort(int a[], int n) 2. {
3.
4.
5.
int i, j, min; for (i = 0; i<=n-1; i++) {
6.
7.
8.
9.
min = i; for (j = i+1; j <= n-1; j++) if (a[j] < a[min]) min = j;
10.
hoanvi(&a[i], &a[min]);
}
44
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11. 12. }
Ví dụ - Sắp xếp nổi bọt
1. void bubblesort(int a[], int n) 2. {
3.
4.
5.
int i,j; for (i=0;i<=n-1;i++) {
6.
7.
for (j=0;j<=n-2-i;j++) {
8.
if (a[j]>a[j+1])
9.
swap(a[j], a[j+1]);
10.
}
}
45
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11. 12. }
Ví dụ - Sắp xếp chèn
1. void insertionsort(int a[], int n) 2. { 3.
4.
5.
int i,j, value;
for (i=1; i
6.
7.
8.
value = a[i];
for (j=i; j>0 && value
9.
a[j] = a[j-1];
10.
11.
}
a[j]= value;
}
46
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Ví dụ - Tìm kiếm tuần tự
1. int search (int a[], int n, int key)
2. {
3.
4.
5.
int i;
for (i=0; i
6.
if (a[i] == key)
7.
return i;
8.
}
return -1;
9.
10. }
47
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Ví dụ - Tìm kiếm nhị phân
1. int bsearch(int a[], int low, int high, int key)
2. {
3.
4.
5.
6.
7.
int mid;
if (low > high)
return -1;
mid = (low + high)/2;
if (key == a[mid])
8.
9.
return mid;
else if (key < a[mid])
10.
return bsearch(a, low, mid-1, key);
11.
else
return bsearch(a, mid+1, high, key);
48
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Quy nạp toán học
Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.
Phương pháp quy nạp:
Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng
Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.
Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + …+ (2n-1) = n2 (*), với n ≥ 1
Bước cơ sở: Trường hợp n = 1, (2n-1) = n2 = 1 là đúng hiển nhiên.
Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2
Khi đó S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1)
= (k + 1)2
Vậy S(k + 1) đúng S(n) đúng với mọi n ≥ 1.
49
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Lập trình đệ quy
Lập trình tính S(n) = 1 + 3 + 5 + … + (2n – 1) = n2 với n bất kỳ, n ≥ 1.
Từ bài toán quy nạp ta có:
Bước cơ sở: S(1) = 1
Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1]
Phương pháp lập trình đệ quy:
Phần cơ sở: S(1) = 1
Phần đệ quy: S(n) = S(n – 1) + (2n – 1)
Áp dụng vào lập trình:
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
50
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hàm đệ quy
Là hàm có phép gọi lại chính nó
Áp dụng cho những bài toán có tính chất quy nạp
Gồm hai phần cơ bản
Phần cơ sở: Trường hợp ban đầu, hiển nhiên.
Phần đệ quy: Có phép gọi lại hàm.
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
51
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hoạt động?
1.
2.
int S(int n)
{
3.
// Gọi hàm S(4)
Giả sử n = 5, hàm đệ quy chạy như sau:
S(5) = S(4) + 9
4.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
5.
}
// Gọi hàm S(3)
S(4) = S(3) + 7
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
// Return S(1)
S(2) = S(1) + 3
S(1) = 1
S(2) = 1 + 3 // Return S(2)
// Return S(3)
S(3) = 1 + 3 + 5
// Return S(4)
S(4) = 1 + 3 + 5 + 7
// Return S(5)
S(5) = 1 + 3 + 5 + 7 + 9 = 25
52
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa
Exponent
53
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa (tt)
Viết hàm đệ quy tính E(n) = an với a R, a ≠ 0, n N và n ≥ 0.
Phép quy nạp
Bước cơ sở: E(0) = a0 = 1
Bước quy nạp: E(k+1) = a x E(k)
1. float E(float a, int n)
2. {
3.
if (n==0) return 1;
else return a * E(a,n-1);
Hàm đệ quy:
E(4) = 2*E(3)
E(3) = 2*E(2)
E(2) = 2*E(1)
Phần cơ sở: E(0) = 1
Phần đệ quy: E(n) = a x E(n-1)
E(1) = 2*E(0)
E(0) = 1
E(1) = 2
Hoạt động:
E(2) = 2*2
Giả sử a = 2, n = 4
E(3) = 2*2*2
E(4) = 2*2*2*2 = 24
54
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Giai thừa
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
Bước cơ sở: ???
Bước quy nạp: ???
Chứng minh: ???
Hàm đệ quy
Phần cơ sở: ???
Phần đệ quy: ???
Hoạt động: ???
55
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Giai thừa (tt)
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
1. int F(int n)
2. {
3.
if (n==1) return 1;
else return n * F(n-1);
Bước cơ sở: F(1) = 1
Bước quy nạp: F(k+1) = (k+1) x F(k)
Chứng minh:
Giả sử F(k) = k!
Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!)
F(4) = 4*F(3)
F(3) = 3*F(2)
Hàm đệ quy
F(2) = 2*F(1)
F(1) = 1
E(2) = 2*1
Phần cơ sở: F(1) = 1
Phần đệ quy: F(n) = n * F(n-1)
E(3) = 3*2*1
E(4) = 4*3*2*1 = 16
Hoạt động: Cho n = 4
56
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Dãy số Fibonacci
Viết hàm đệ quy tính Fib(n) là phần tử thứ n của dãy số Fibonacci
Dãy Fibonaci: 1 1 2 3 5 8 13 21 34 55…
Tính chất: Số sau bằng tổng hai số liền trước nó.
Quy nạp
Fib(1) = 1, Fib(2) = 1
Fib(k) = Fib(k-1) + Fib(k-2)
Hàm đệ quy ?
Phần cơ sở: ?
Phần đệ quy: ?
57
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Dãy số Fibonacci (tt)
1. // Fibonacci: 1 1 2 3 5 8 13 21 34 55...
2. #include
3. int fib(int n) // Tìm số Fibonacci thứ n
4. {
5.
if (n==1 || n==2) return 1;
return fib(n-1) + fib(n-2);
// Phần cơ sở
// Phần đệ quy
6.
7. }
8. void main()
9. {
10.
11.
int n;
do{
// Nhập n>=1
12.
scanf("%d",&n);
13.
}while(n<1);
printf("Fibinaci(%d) = %d.", n, fib(n));
14.
15. }
58
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Bài toán Tháp Hanoi
59
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Hết bài 2
Chương trình con
Ví dụ vận dụng chương trình con
Phép quy nạp
Giải thuật đệ quy
Ví dụ vận dụng giải thuật đệ quy
60
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
6.
7.
8.
value = a[i];
for (j=i; j>0 && value
9.
a[j] = a[j-1];
10.
11.
}
a[j]= value;
}
46
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Ví dụ - Tìm kiếm tuần tự
1. int search (int a[], int n, int key)
2. {
3.
4.
5.
int i;
for (i=0; i
6.
if (a[i] == key)
7.
return i;
8.
}
return -1;
9.
10. }
47
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Ví dụ - Tìm kiếm nhị phân
1. int bsearch(int a[], int low, int high, int key)
2. {
3.
4.
5.
6.
7.
int mid;
if (low > high)
return -1;
mid = (low + high)/2;
if (key == a[mid])
8.
9.
return mid;
else if (key < a[mid])
10.
return bsearch(a, low, mid-1, key);
11.
else
return bsearch(a, mid+1, high, key);
48
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Quy nạp toán học
Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.
Phương pháp quy nạp:
Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng
Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.
Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + …+ (2n-1) = n2 (*), với n ≥ 1
Bước cơ sở: Trường hợp n = 1, (2n-1) = n2 = 1 là đúng hiển nhiên.
Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2
Khi đó S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1)
= (k + 1)2
Vậy S(k + 1) đúng S(n) đúng với mọi n ≥ 1.
49
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Lập trình đệ quy
Lập trình tính S(n) = 1 + 3 + 5 + … + (2n – 1) = n2 với n bất kỳ, n ≥ 1.
Từ bài toán quy nạp ta có:
Bước cơ sở: S(1) = 1
Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1]
Phương pháp lập trình đệ quy:
Phần cơ sở: S(1) = 1
Phần đệ quy: S(n) = S(n – 1) + (2n – 1)
Áp dụng vào lập trình:
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
50
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hàm đệ quy
Là hàm có phép gọi lại chính nó
Áp dụng cho những bài toán có tính chất quy nạp
Gồm hai phần cơ bản
Phần cơ sở: Trường hợp ban đầu, hiển nhiên.
Phần đệ quy: Có phép gọi lại hàm.
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
51
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hoạt động?
1.
2.
int S(int n)
{
3.
// Gọi hàm S(4)
Giả sử n = 5, hàm đệ quy chạy như sau:
S(5) = S(4) + 9
4.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
5.
}
// Gọi hàm S(3)
S(4) = S(3) + 7
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
// Return S(1)
S(2) = S(1) + 3
S(1) = 1
S(2) = 1 + 3 // Return S(2)
// Return S(3)
S(3) = 1 + 3 + 5
// Return S(4)
S(4) = 1 + 3 + 5 + 7
// Return S(5)
S(5) = 1 + 3 + 5 + 7 + 9 = 25
52
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa
Exponent
53
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa (tt)
Viết hàm đệ quy tính E(n) = an với a R, a ≠ 0, n N và n ≥ 0.
Phép quy nạp
Bước cơ sở: E(0) = a0 = 1
Bước quy nạp: E(k+1) = a x E(k)
1. float E(float a, int n)
2. {
3.
if (n==0) return 1;
else return a * E(a,n-1);
Hàm đệ quy:
E(4) = 2*E(3)
E(3) = 2*E(2)
E(2) = 2*E(1)
Phần cơ sở: E(0) = 1
Phần đệ quy: E(n) = a x E(n-1)
E(1) = 2*E(0)
E(0) = 1
E(1) = 2
Hoạt động:
E(2) = 2*2
Giả sử a = 2, n = 4
E(3) = 2*2*2
E(4) = 2*2*2*2 = 24
54
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Giai thừa
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
Bước cơ sở: ???
Bước quy nạp: ???
Chứng minh: ???
Hàm đệ quy
Phần cơ sở: ???
Phần đệ quy: ???
Hoạt động: ???
55
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Giai thừa (tt)
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
1. int F(int n)
2. {
3.
if (n==1) return 1;
else return n * F(n-1);
Bước cơ sở: F(1) = 1
Bước quy nạp: F(k+1) = (k+1) x F(k)
Chứng minh:
Giả sử F(k) = k!
Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!)
F(4) = 4*F(3)
F(3) = 3*F(2)
Hàm đệ quy
F(2) = 2*F(1)
F(1) = 1
E(2) = 2*1
Phần cơ sở: F(1) = 1
Phần đệ quy: F(n) = n * F(n-1)
E(3) = 3*2*1
E(4) = 4*3*2*1 = 16
Hoạt động: Cho n = 4
56
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Dãy số Fibonacci
Viết hàm đệ quy tính Fib(n) là phần tử thứ n của dãy số Fibonacci
Dãy Fibonaci: 1 1 2 3 5 8 13 21 34 55…
Tính chất: Số sau bằng tổng hai số liền trước nó.
Quy nạp
Fib(1) = 1, Fib(2) = 1
Fib(k) = Fib(k-1) + Fib(k-2)
Hàm đệ quy ?
Phần cơ sở: ?
Phần đệ quy: ?
57
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Dãy số Fibonacci (tt)
1. // Fibonacci: 1 1 2 3 5 8 13 21 34 55...
2. #include
3. int fib(int n) // Tìm số Fibonacci thứ n
4. {
5.
if (n==1 || n==2) return 1;
return fib(n-1) + fib(n-2);
// Phần cơ sở
// Phần đệ quy
6.
7. }
8. void main()
9. {
10.
11.
int n;
do{
// Nhập n>=1
12.
scanf("%d",&n);
13.
}while(n<1);
printf("Fibinaci(%d) = %d.", n, fib(n));
14.
15. }
58
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Bài toán Tháp Hanoi
59
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Hết bài 2
Chương trình con
Ví dụ vận dụng chương trình con
Phép quy nạp
Giải thuật đệ quy
Ví dụ vận dụng giải thuật đệ quy
60
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
9.
a[j] = a[j-1];
10.
11.
} a[j]= value;
}
46
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12. 13. }
Ví dụ - Tìm kiếm tuần tự
1. int search (int a[], int n, int key) 2. {
3.
4.
5.
int i;
for (i=0; i
6.
if (a[i] == key)
7.
return i;
8.
}
return -1;
9.
10. }
47
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Ví dụ - Tìm kiếm nhị phân
1. int bsearch(int a[], int low, int high, int key)
2. {
3.
4.
5.
6.
7.
int mid;
if (low > high)
return -1;
mid = (low + high)/2;
if (key == a[mid])
8.
9.
return mid;
else if (key < a[mid])
10.
return bsearch(a, low, mid-1, key);
11.
else
return bsearch(a, mid+1, high, key);
48
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12.
13. }
Quy nạp toán học
Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.
Phương pháp quy nạp:
Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng
Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.
Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + …+ (2n-1) = n2 (*), với n ≥ 1
Bước cơ sở: Trường hợp n = 1, (2n-1) = n2 = 1 là đúng hiển nhiên.
Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2
Khi đó S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1)
= (k + 1)2
Vậy S(k + 1) đúng S(n) đúng với mọi n ≥ 1.
49
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Lập trình đệ quy
Lập trình tính S(n) = 1 + 3 + 5 + … + (2n – 1) = n2 với n bất kỳ, n ≥ 1.
Từ bài toán quy nạp ta có:
Bước cơ sở: S(1) = 1
Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1]
Phương pháp lập trình đệ quy:
Phần cơ sở: S(1) = 1
Phần đệ quy: S(n) = S(n – 1) + (2n – 1)
Áp dụng vào lập trình:
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
50
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hàm đệ quy
Là hàm có phép gọi lại chính nó
Áp dụng cho những bài toán có tính chất quy nạp
Gồm hai phần cơ bản
Phần cơ sở: Trường hợp ban đầu, hiển nhiên.
Phần đệ quy: Có phép gọi lại hàm.
1. int S(int n)
2. {
3.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
51
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Hoạt động?
1.
2.
int S(int n)
{
3.
// Gọi hàm S(4)
Giả sử n = 5, hàm đệ quy chạy như sau:
S(5) = S(4) + 9
4.
if (n==1) return 1;
else return S(n-1) + (2*n – 1);
5.
}
// Gọi hàm S(3)
S(4) = S(3) + 7
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
// Return S(1)
S(2) = S(1) + 3
S(1) = 1
S(2) = 1 + 3 // Return S(2)
// Return S(3)
S(3) = 1 + 3 + 5
// Return S(4)
S(4) = 1 + 3 + 5 + 7
// Return S(5)
S(5) = 1 + 3 + 5 + 7 + 9 = 25
52
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa
Exponent
53
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa (tt)
Viết hàm đệ quy tính E(n) = an với a R, a ≠ 0, n N và n ≥ 0.
Phép quy nạp
Bước cơ sở: E(0) = a0 = 1
Bước quy nạp: E(k+1) = a x E(k)
1. float E(float a, int n)
2. {
3.
if (n==0) return 1;
else return a * E(a,n-1);
Hàm đệ quy:
E(4) = 2*E(3)
E(3) = 2*E(2)
E(2) = 2*E(1)
Phần cơ sở: E(0) = 1
Phần đệ quy: E(n) = a x E(n-1)
E(1) = 2*E(0)
E(0) = 1
E(1) = 2
Hoạt động:
E(2) = 2*2
Giả sử a = 2, n = 4
E(3) = 2*2*2
E(4) = 2*2*2*2 = 24
54
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Giai thừa
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
Bước cơ sở: ???
Bước quy nạp: ???
Chứng minh: ???
Hàm đệ quy
Phần cơ sở: ???
Phần đệ quy: ???
Hoạt động: ???
55
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Giai thừa (tt)
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n!
Phép quy nạp
1. int F(int n)
2. {
3.
if (n==1) return 1;
else return n * F(n-1);
Bước cơ sở: F(1) = 1
Bước quy nạp: F(k+1) = (k+1) x F(k)
Chứng minh:
Giả sử F(k) = k!
Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!)
F(4) = 4*F(3)
F(3) = 3*F(2)
Hàm đệ quy
F(2) = 2*F(1)
F(1) = 1
E(2) = 2*1
Phần cơ sở: F(1) = 1
Phần đệ quy: F(n) = n * F(n-1)
E(3) = 3*2*1
E(4) = 4*3*2*1 = 16
Hoạt động: Cho n = 4
56
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4.
5. }
Ví dụ vận dụng – Dãy số Fibonacci
Viết hàm đệ quy tính Fib(n) là phần tử thứ n của dãy số Fibonacci
Dãy Fibonaci: 1 1 2 3 5 8 13 21 34 55…
Tính chất: Số sau bằng tổng hai số liền trước nó.
Quy nạp
Fib(1) = 1, Fib(2) = 1
Fib(k) = Fib(k-1) + Fib(k-2)
Hàm đệ quy ?
Phần cơ sở: ?
Phần đệ quy: ?
57
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Dãy số Fibonacci (tt)
1. // Fibonacci: 1 1 2 3 5 8 13 21 34 55...
2. #include
3. int fib(int n) // Tìm số Fibonacci thứ n
4. {
5.
if (n==1 || n==2) return 1;
return fib(n-1) + fib(n-2);
// Phần cơ sở
// Phần đệ quy
6.
7. }
8. void main()
9. {
10.
11.
int n;
do{
// Nhập n>=1
12.
scanf("%d",&n);
13.
}while(n<1);
printf("Fibinaci(%d) = %d.", n, fib(n));
14.
15. }
58
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Bài toán Tháp Hanoi
59
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Hết bài 2
Chương trình con
Ví dụ vận dụng chương trình con
Phép quy nạp
Giải thuật đệ quy
Ví dụ vận dụng giải thuật đệ quy
60
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
6.
if (a[i] == key)
7.
return i;
8.
} return -1;
9. 10. }
47
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Ví dụ - Tìm kiếm nhị phân
1. int bsearch(int a[], int low, int high, int key) 2. { 3.
4.
5.
6.
7.
int mid; if (low > high) return -1; mid = (low + high)/2; if (key == a[mid])
8.
9.
return mid; else if (key < a[mid])
10.
return bsearch(a, low, mid-1, key);
11.
else
return bsearch(a, mid+1, high, key);
48
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12. 13. }
Quy nạp toán học
Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0. Phương pháp quy nạp:
Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.
Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + …+ (2n-1) = n2 (*), với n ≥ 1
Bước cơ sở: Trường hợp n = 1, (2n-1) = n2 = 1 là đúng hiển nhiên. Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2 Khi đó S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1)
= (k + 1)2
Vậy S(k + 1) đúng S(n) đúng với mọi n ≥ 1.
49
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Lập trình đệ quy
Lập trình tính S(n) = 1 + 3 + 5 + … + (2n – 1) = n2 với n bất kỳ, n ≥ 1. Từ bài toán quy nạp ta có:
Bước cơ sở: S(1) = 1 Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1]
Phương pháp lập trình đệ quy:
Phần cơ sở: S(1) = 1 Phần đệ quy: S(n) = S(n – 1) + (2n – 1)
Áp dụng vào lập trình:
1. int S(int n) 2. { 3.
if (n==1) return 1; else return S(n-1) + (2*n – 1);
50
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4. 5. }
Hàm đệ quy
Là hàm có phép gọi lại chính nó Áp dụng cho những bài toán có tính chất quy nạp Gồm hai phần cơ bản
Phần cơ sở: Trường hợp ban đầu, hiển nhiên. Phần đệ quy: Có phép gọi lại hàm.
1. int S(int n) 2. { 3.
if (n==1) return 1; else return S(n-1) + (2*n – 1);
51
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4. 5. }
Hoạt động?
1.
2.
int S(int n) {
3.
// Gọi hàm S(4)
Giả sử n = 5, hàm đệ quy chạy như sau: S(5) = S(4) + 9
4.
if (n==1) return 1; else return S(n-1) + (2*n – 1);
5.
}
// Gọi hàm S(3)
S(4) = S(3) + 7
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
// Return S(1)
S(2) = S(1) + 3 S(1) = 1
S(2) = 1 + 3 // Return S(2)
// Return S(3)
S(3) = 1 + 3 + 5
// Return S(4)
S(4) = 1 + 3 + 5 + 7
// Return S(5)
S(5) = 1 + 3 + 5 + 7 + 9 = 25
52
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa
Exponent
53
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Lũy thừa (tt)
Viết hàm đệ quy tính E(n) = an với a R, a ≠ 0, n N và n ≥ 0. Phép quy nạp
Bước cơ sở: E(0) = a0 = 1 Bước quy nạp: E(k+1) = a x E(k)
1. float E(float a, int n) 2. { 3.
if (n==0) return 1; else return a * E(a,n-1);
Hàm đệ quy:
E(4) = 2*E(3)
E(3) = 2*E(2)
E(2) = 2*E(1)
Phần cơ sở: E(0) = 1 Phần đệ quy: E(n) = a x E(n-1)
E(1) = 2*E(0)
E(0) = 1
E(1) = 2
Hoạt động:
E(2) = 2*2
Giả sử a = 2, n = 4
E(3) = 2*2*2
E(4) = 2*2*2*2 = 24
54
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4. 5. }
Ví dụ vận dụng – Giai thừa
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n! Phép quy nạp
Bước cơ sở: ??? Bước quy nạp: ??? Chứng minh: ???
Hàm đệ quy
Phần cơ sở: ??? Phần đệ quy: ???
Hoạt động: ???
55
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Giai thừa (tt)
Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x … x n = n! Phép quy nạp
1. int F(int n) 2. { 3.
if (n==1) return 1; else return n * F(n-1);
Bước cơ sở: F(1) = 1 Bước quy nạp: F(k+1) = (k+1) x F(k) Chứng minh:
Giả sử F(k) = k! Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!)
F(4) = 4*F(3)
F(3) = 3*F(2)
Hàm đệ quy
F(2) = 2*F(1)
F(1) = 1
E(2) = 2*1
Phần cơ sở: F(1) = 1 Phần đệ quy: F(n) = n * F(n-1)
E(3) = 3*2*1
E(4) = 4*3*2*1 = 16
Hoạt động: Cho n = 4
56
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
4. 5. }
Ví dụ vận dụng – Dãy số Fibonacci
Viết hàm đệ quy tính Fib(n) là phần tử thứ n của dãy số Fibonacci
Dãy Fibonaci: 1 1 2 3 5 8 13 21 34 55… Tính chất: Số sau bằng tổng hai số liền trước nó. Quy nạp
Fib(1) = 1, Fib(2) = 1 Fib(k) = Fib(k-1) + Fib(k-2)
Hàm đệ quy ? Phần cơ sở: ? Phần đệ quy: ?
57
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Ví dụ vận dụng – Dãy số Fibonacci (tt)
1. // Fibonacci: 1 1 2 3 5 8 13 21 34 55...
2. #include
3. int fib(int n) // Tìm số Fibonacci thứ n
4. {
5.
if (n==1 || n==2) return 1; return fib(n-1) + fib(n-2);
// Phần cơ sở // Phần đệ quy
6. 7. } 8. void main() 9. { 10.
11.
int n; do{
// Nhập n>=1
12.
scanf("%d",&n);
13.
}while(n<1); printf("Fibinaci(%d) = %d.", n, fib(n));
14. 15. }
58
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Bài toán Tháp Hanoi
59
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Hết bài 2
Chương trình con
Ví dụ vận dụng chương trình con
Phép quy nạp
Giải thuật đệ quy
Ví dụ vận dụng giải thuật đệ quy
60
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
![Câu hỏi trắc nghiệm Lập trình C [mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251012/quangle7706@gmail.com/135x160/91191760326106.jpg)
