›
›

Bài giảng Nhập môn lập trình - Chương 10: Một số vấn đề nâng cao - Nguyễn Minh Huy

Download
Mꢀt sꢁ vꢂn đꢃ nâng cao  
GV. Nguyꢀn Minh Huy  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
1
Nꢃi dung  
ꢀ Mꢄng đꢃng.  
ꢀ Đꢅ quy.  
ꢀ Các thuꢁt toán thông dꢆng.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
2
Nꢃi dung  
ꢀ Mꢄng đꢀng.  
ꢀ Đꢅ quy.  
ꢀ Các thuꢁt toán thông dꢆng.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
3
Mꢄng đꢃng  
ꢀ Vꢇn đꢈ vꢉi mꢄng tĩnh:  
ꢀ Phꢄi khai báo kích thưꢉc tꢊi đa.  
ꢀ Không phꢄi lúc nào cũng dùng hꢋt.  
ꢁ Tꢊn nhiꢈu bꢃ nhꢉ.  
ꢁ Nhu cꢌu mꢄng kích thưꢉc tùy biꢋn.  
ꢀ Khái niꢅm con trꢍ:  
ꢀ Biꢋn “lưu đꢃng”.  
ꢁ Có thꢎ “đꢏnh cư” ꢐ nhiꢈu ô nhꢉ.  
ꢁ “Trꢍ” đꢋn các ô nhꢉ khác nhau.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
4
Mꢄng đꢃng  
ꢀ Con trꢍ trong C:  
ꢀ Khai báo: <Kiꢎu dꢑ liꢅu> *<Tên con trꢅ>;  
ꢀ Lꢇy đꢏa chꢒ biꢋn: <Tên con trꢍ> = &<Tên biꢆn>;  
11  
5
50  
6
73  
11  
int x = 5;  
int y = 6;  
int
*p
;  
x
y
p
p = &x;  
ꢀ Truy xuꢇt dꢑ liꢅu ô nhꢉ:  
<Tên biꢋn> = *<Tên con trꢅ>;  
<Tên biꢋn> = <Tên con trꢅ>[<Chꢒ sꢊ ô nhꢉ>];  
int z = *p;  
int t = p[2];  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
5
Mꢄng đꢃng  
ꢀ Con trꢍ trong C:  
ꢀ Lꢅnh xin cꢇp vùng nhꢉ:  
ꢂ Cú pháp: calloc(<sꢊ ô nhꢉ>, <kích thưꢉc mꢓi ô nhꢉ>);  
ꢂ Trꢄ vꢈ: đꢏa chꢒ vùng nhꢉ (thành công), NULL (thꢇt bꢔi).  
ꢂ Đꢏa chꢒ trꢄ vꢈ phꢄi cùng kiꢎu vꢉi con trꢍ nhꢁn.  
ꢀ Lꢅnh thu hꢕi vùng nhꢉ:  
ꢂ Cú pháp: free(<Tên con trꢍ>);  
int *p = (int *) calloc( 5, sizeof( int ) );  
p
65  
0 0 0 0 0  
HocSinh *h = (HocSinh *) calloc( 3, sizeof( HocSinh ) );  
hoten:???  
ngaysinh:??? ngaysinh:??? ngaysinh:???  
diemvan:??? diemvan:??? diemvan:???  
diemtoan:??? diemtoan:??? diemtoan:???  
hoten:???  
hoten:???  
h
78  
free(p);  
free(h);  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
6
Nꢃi dung  
ꢀ Mꢄng đꢃng.  
ꢀ Đꢇ quy.  
ꢀ Các thuꢁt toán thông dꢆng.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
7
Đꢅ quy  
ꢀ Khái niꢅm đꢅ quy:  
ꢀ Đꢏnh nghĩa mꢃt khái niꢅm dꢖa trên chính nó.  
ꢀ Cꢇu trúc:  
ꢂ Phꢌn đꢏnh nghĩa trưꢗng hꢘp cơ bꢄn (tưꢗng minh).  
ꢂ Phꢌn đꢏnh nghĩa đꢅ quy.  
ꢀ Ví dꢆ: đꢏnh nghĩa lũy thꢙa xn  
ꢂ LT(x, 0) = 1.  
ꢂ LT(x, n) = x * LT(x, n – 1), n > 0.  
ꢀ Ưu điꢎm:  
ꢂ Nêu bꢄn chꢇt vꢇn đꢈ.  
ꢂ Ngꢚn gꢛn, dꢀ hiꢎu.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
8
Đꢅ quy  
ꢀ Hàm đꢅ quy:  
ꢀ Dùng cài đꢜt khái niꢅm đꢅ quy.  
ꢀ Cꢇu trúc:  
<Kiꢎu trꢄ vꢈ> <Tên hàm>(<Danh sách tham sꢊ>)  
{
if (<Trưꢗng hꢘp cơ bꢄn>)  
<Xꢈ lý trưꢉng hꢊp cơ bꢄn>;  
else  
<Gꢋi lꢌi hàm đꢇ quy>;  
}
long luythua(float x, int n)  
{
if ( n == 0 )  
return 1;  
return x * luythua(x, n – 1);  
}
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
9
Nꢃi dung  
ꢀ Mꢄng đꢃng.  
ꢀ Đꢅ quy.  
ꢀ Các thuꢍt toán thông dꢎng.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
10  
Các thuꢁt toán thông dꢆng  
ꢀ Bài toán sꢚp xꢋp:  
ꢀ Nhꢁp vào mꢄng N sꢊ nguyên.  
ꢀ Sꢚp xꢋp và xuꢇt mꢄng theo thꢝ tꢖ tăng dꢌn.  
ꢁ Thuꢁt toán Interchange Sort.  
ꢁ Thuꢁt toán Selection Sort.  
ꢁ Thuꢁt toán Quicksort.  
ꢞ
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
11  
Các thuꢁt toán thông dꢆng  
ꢀ Bài toán sꢚp xꢋp:  
ꢀ Nghꢏch thꢋ:  
ꢂ Cꢜp phꢌn tꢟ đꢝng không đúng thꢝ tꢖ.  
ꢂ (ai, aj) nghꢏch thꢋ ꢃ i < j và ai > aj.  
ꢀ Thuꢁt toán Interchange Sort:  
ꢂ Xét tꢇt cꢄ các cꢜp phꢌn tꢟ mꢄng.  
ꢂ Vꢉi mꢓi cꢜp, hoán vꢏ chúng nꢋu nghꢏch thꢋ.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
12  
Các thuꢁt toán thông dꢆng  
ꢀ Bài toán tìm kiꢋm:  
ꢀ Trò chơi đoán sꢊ:  
ꢂ B1: ngưꢗi chơi nghĩ ra mꢃt sꢊ nguyên N (1 <= N <= 100).  
ꢂ B2: máy đưa ra dꢖ đoán mꢃt sꢊ nguyên K.  
ꢂ B3: ngưꢗi chơi cho biꢋt K lꢉn hơn, nhꢍ hơn hay bꢠng N.  
ꢂ B4: nꢋu bꢠng ꢁ kꢋt thúc trò chơi.  
ngưꢘc lꢔi ꢁ quay lꢔi B2.  
Hãy đꢈ ra mꢃt thuꢁt toán đꢎ sꢊ lꢌn đoán cꢡa máy là ít nhꢇt.  
ꢁ Tìm kiꢋm tuꢌn tꢖ: O(n).  
ꢁ Tìm kiꢋm nhꢏ phân: O(log2n).  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
13  
Mꢃt sꢊ thuꢁt toán thông dꢆng  
ꢀ Bài toán tìm kiꢋm:  
ꢀ Tìm kiꢋm nhꢏ phân:  
ꢂ B1: đꢜt (left, right) là đoꢔn cꢌn tìm.  
ꢂ B2: nꢆu chiꢈu dài đoꢔn cꢌn tìm = 0 ꢁ kꢋt thúc thꢇt bꢔi.  
ngưꢊc lꢌi  
B2.1: kiꢎm tra phꢌn tꢟ giꢑa đoꢔn.  
B2.2: nꢆu thꢍa điꢈu kiꢅn tìm ꢁ kꢋt thúc thành công.  
ngưꢊc lꢌi  
B2.2.1: thu hꢢp mꢃt nꢟa đoꢔn cꢌn tìm  
(dꢖa vào phꢌn tꢟ giꢑa).  
B2.2.2: quay lꢔi B2.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
14  
Tóm tꢚt  
ꢀ Con trꢍ:  
ꢀ Biꢋn “tham chiꢋu”, “trꢍ” đꢋn các ô nhꢉ.  
ꢀ Toán tꢟ &: lꢇy đꢏa chꢒ ô nhꢉ.  
ꢀ Toán tꢟ *: truy xuꢇt ô nhꢉ.  
ꢀ
Đꢅ quy:  
ꢀ Đꢏnh nghĩa mꢃt khái niꢅm dꢖa trên chính nó.  
ꢀ Hàm đꢅ quy: hàm gꢛi lꢔi chính mình.  
ꢀ Thuꢁt toán thông dꢆng:  
ꢀ Sꢚp xꢋp Interchange Sort.  
ꢀ Tìm kiꢋm nhꢏ phân.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
15  
Bài tꢁp  
ꢀ Bài tꢁp 10.1:  
Thông tin mꢃt hꢛc sinh bao gꢕm: hꢛ tên, điꢎm văn, điꢎm toán.  
File input.txt chꢝa danh sách hꢛc sinh như sau:  
ꢂ Dòng đꢌu tiên chꢝa: N (sꢊ hꢛc sinh trong danh sách).  
ꢂ N dòng tiꢋp theo, dòng i (1 <= i <= N) chꢝa: hoteni vani toani  
(thông tin hꢛc sinh thꢝ i trong danh sách).  
Viꢋt chương trình C (sꢟ dꢆng kiꢎu cꢇu trúc và mꢄng đꢃng):  
ꢂ Nhꢁp danh sách hꢛc sinh tꢙ file input.txt  
ꢂ Xuꢇt danh sách hꢛc sinh giꢍi (điꢎm trung bình >= 8)  
theo thꢝ tꢖ điꢎm trung bình giꢄm dꢌn vào  
file output.txt (cꢇu trúc tương tꢖ file input.txt).  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
16  
Bài tꢁp  
ꢀ Bài tꢁp 10.2:  
Viꢋt chương trình C tìm ưꢉc chung lꢉn nhꢇt (sꢟ dꢆng đꢅ quy) như sau:  
ꢂ Nhꢁp vào hai sꢊ nguyên dương a, b.  
ꢂ Tìm và xuꢇt ưꢉc chung lꢉn nhꢇt cꢡa a, b (thuꢁt toán Euclid).  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
17  
Bài tꢁp  
ꢀ Bài tꢁp 10.3:  
Viꢋt chương trình C tính dãy Fibonacci (sꢟ dꢆng đꢅ quy) như sau:  
ꢂ Nhꢁp vào sꢊ nguyên N >= 0.  
ꢂ Xuꢇt các sꢊ Fibonacci tꢙ F0 đꢋn FN.  
Nhꢁp môn lꢁp trình ꢂ GV. Nguyꢀn Minh Huy  
18  
pdf 18 trang myanh 26980 Free
Download
Bạn đang xem tài liệu "Bài giảng Nhập môn lập trình - Chương 10: Một số vấn đề nâng cao - Nguyễn Minh Huy", để 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:

  • pdfbai_giang_nhap_mon_lap_trinh_chuong_10_mot_so_van_de_nang_ca.pdf