ộ
ộN i dung trình bày N i dung trình bày
ề
ề ả ộ
ề
1. Khái ni mệ ộ ả 2. M ng m t chi u ộ ố 3. M t s bài toán trên m ng m t chi u ả 4. M ng hai chi u ộ ố 5. M t s bài toán trên m ng hai chi u
2
ề ả
1. Khái ni mệ 1. Khái ni mệ
ế ể ợ
ộ ớ
M ngả ữ là m t ộ t p h p các bi n có cùng ki u d ậ ộ ế ằ li uệ n m liên ti p nhau trong b nh và có m t tên m ngả tên chung g i là
ọ
M i ph n t
ầ ỗ ả ỉ ụ ch m c
ử ủ ầ ử ầ (index): ph n t c a m ng đ ượ đ u tiên đ ượ c đánh ố c đánh s là 0,…
N u m ng có n ph n t ầ ử
ầ ử ả thì ph n t
ầ ử ầ ỉ ụ ố ế ỉ ụ ch m c là 0 và ph n t đ u tiên có n1 cu i có ch m c là
a
3
ệ ệ
1. Khái ni m (tt) 1. Khái ni m (tt)
Mu n truy c p ph n t
ủ
ầ ủ ậ ch m c ử ỉ ụ c a nó, cú pháp: ả ả nào c a m ng thì ph i tên_m ngả [ch ỉ
a[0] = 10;
cout<
ố
ự
d a vào
m cụ ]
◦Ví d : ụ S ph n t ử ầ
ả ả
trong m ng đ
ố ị
c đ nh c a m ng, luôn
tr ọ
ượ
ố
c g i là
ủ
ả
, ph i đ
ươ
ố
cướ và không đ iổ trong su t ch cướ
kích th
ượ xác đ nh
ị
c
ng trình Có hai lo i m ng thông d ng: 1 chi u, 2 chi u 4 ụ ề ề ạ ả ề ề ả ộ ề 1. Khái ni mệ
ộ
ả
2. M ng m t chi u
ộ ố
3. M t s bài toán trên m ng m t chi u
ả
4. M ng hai chi u
ộ ố
5. M t s bài toán trên m ng hai chi u 5 ề ả Khi khai báo m ng ph i cho bi
Cú pháp khai báo m ng:ả ả ả ướ ế kích th ả
c m ng t ể ủ ả ầ ử ố ả ◦type: ki u d li u c a m ng
ữ ệ
◦arrayName: tên m ngả
◦size: s ph n t
ố t i đa trong m ng Ví d : ụ
int a[5]; a[0] a[1] a[2] a[3] a[4] float ds[100];
char st[50]; 6 a M i ph n t
ỗ
Ví d :ụ int num[3]; ầ ử num[0] = 2; // gán 2 cho ph n t num[0] ị num[1] = num[0] + 3 // num[1] có giá tr 5 ị num[2] = num[0] + num[1]; //num[2] có giá tr 7 cout<< num[0]<<"\t"< cout<<"Nhap vao phan tu dau tien"; cin>>num[0]; cout<< num[0]; 7 ầ ử ả m ng là m t ngườ ộ bi nế thông th Kích th ủ ả ằ ượ c (tính b ng byte) c a m ng đ c tính ướ
theo công th c: ứ Ví d :ụ Total_size = sizeof(type) * NumOfElements int num[100]; ả ướ Giả sử int chiếm 2 bytes, m ng num có kích
th c là: 8 sizeof(int)*100 = 2 bytes * 100 = 200 bytes Cú pháp khai báo và kh i t o m ng: ở ạ ả ◦L u ýư : ướ ả
c m ng ướ ị ở ượ
ượ ị
ở ấ Không khai báo kích th
Kích th
ả
c m ng đ
ặ
ấ
ặ
c p d u ngo c {}, đ c xác đ nh b i các giá tr trong
ẩ
c phân cách nhau b i d u ph y 9 Ví d 1:ụ int soChan[] = {2, 4, 6, 8, 10}; ị
ị ị ầ ử ố ầ soChan có 5 ph n t s nguyên, l n Ví d 2:ụ
char st[] = {'h', 'e', 'l', 'l', 'o'}; 10 M ng ả
ượ
t là:
l
soChan[0] có giá tr là 2
soChan[1] có giá tr là 4
...
soChan[4] có giá tr là 10 ố ộ ả ầ ử ầ ử ỗ ị . M i ph n t có giá tr là ạ
ỉ ụ T o m t m ng s nguyên có 10 ph n t
ả
ủ
ch m c c a nó. In m ng ra màn hình.
#include int a[N];
ả
ậ
// nh p m ng
for( int i=0; i } 11 void NhapMang( int a[ ], int n )
{ for( int i=0; i cout<<"a["<
cin>> a[i]; #include } } void XuatMang( int a[ ], int n ) { for( int i=0; i cout<< a[i]<< "\t"; int sl, a[N];
cout<<“Nhap so luong phan tu:”;
cin>>sl;
// gọi hàm để nhập mảng
NhapMang(a, sl);
// gọi hàm để xuất mảng
cout<< "In mang:\n";
XuatMang(a, sl); } } 12 n / 2 = 2 n
2 Đổi một số nguyên dương thập
phân thành số nhị phân.
void main()
{ n%2 n=46
0 23 2 11 1 2 1 2 int i, j=0, n, np[20];
cout<<"n="; cin>>n;
do{ 5
1 2 2
0 0 1
1 np[j]= n%2;
j++;
n = n/2; 0 1 1 1 0 1 np }while(n>0);
cout<<"dang nhi phan: ";
for( i=j1; i>0 ; i ) np[j] cout< 13 Đ t o ra s ng u nhiên, s d ng hàm Cú pháp: ử ụ ể ạ ẫ ố random ả ủ ế ạ ẫ ố ◦K t qu c a hàm là t o ra s nguyên ng u nhiên có ạ ị giá tr trong đo n [0, n1] Đ tránh l p l i b s gi ng nhau m i l n ch y ặ ạ ộ ố ố
ả ể
ươ
ch ng trình, ph i dùng thêm hàm ỗ ầ
ạ
randomize Đ s d ng các hàm trên thì trong ch ươ ng trình 14 ể ử ụ
ả ph i khai báo th vi n ư ệ void NhapMang( int a[], int n )
{ }
void XuatMang( int a[], int n ) { for( int i=0; i cout<< a[i]<<"\t"; } int sl, a[N];
cout<<“Nhap so luong phan tu:”;
cin>>sl;
// gọi hàm để nhập mảng
NhapMang(a, sl);
// gọi hàm để xuất mảng
cout<< "In mang:\n";
XuatMang(a, sl); 15 } ử ụ S d ng hàm rand(), trong th vi n ư ệ ả ề ẫ ố Hàm rand() tr v 1 s nguyên ng u nhiên có giá tr
ị ạ trong đo n [0, RAND_MAX] ố ượ ộ ằ ậ c đ nh nghĩa trong t p ◦RAND_MAX là m t h ng s đ
ư ấ ằ ị
tin cstdlib, nh ng ít nh t b ng 32767 ể ố ớ ườ Đ tránh phát sinh s quá l n, th ng dùng: ố ộ ◦rand()% 100 phát sinh s thu c [0, 99] ố ộ ố ộ rand()% 100 + 1 phát sinh s thu c [1, 100]
rand()% 30 + 1985 phát sinh s thu c [1985, 2014] ỗ ầ ạ Đ tránh l p l i b s gi ng nhau m i l n ch y ặ ạ ộ ố ố
ng trình, dùng thêm l nh: srand ( time(NULL) ), ộ ể
ươ
ch
hàm time thu c th vi n ệ
ư ệ 16 void NhapMang( int a[], int n )
{ }
void XuatMang( int a[], int n ) { for( int i=0; i cout<< a[i]<<"\t"; } 17 } ề ề ả ộ ề 1. Khái ni mệ
ộ
ả
2. M ng m t chi u
ộ ố
3. M t s bài toán trên m ng m t chi u
ả
4. M ng hai chi u
ộ ố
5. M t s bài toán trên m ng hai chi u 18 ề ả Tính t ng, tích các ph n t ầ ử ả ổ m ng Tìm ki m trên m ng theo đi u ki n cho tr ế ề ệ ả ướ
c Đ m s ph n t
ố ầ ử ả ệ ế ướ ề
m ng theo đi u ki n cho tr c Tìm ph n t ầ ử ớ ấ ủ ả ấ ỏ l n nh t, nh nh t c a m ng S p x p m ng tăng d n, gi m d n 19 ế ầ ắ ầ ả ả Gi
ả ử
ầ
c n tính
ổ ầ ử ả ố s a là tên m ng, n là s ph n t ị
, s là giá tr s=0 s=4 i=0 s=11 i=1 T ng giá tr các ph n t
ị
int s=0;
for( int i=0; i s=20 i=2 ầ ử ả trong m ng: s=22 i=3 4 7 9 2 1 s+=a[i]; s=23 i=4 a Tích giá tr các ph n t
ị
int s=1;
for( int i=0; i ầ ử ả trong m ng: 20 s*=a[i]; Gi ầ ử ả ố s a là tên m ng, n là s ph n t ị
, k là giá tr ả ử
mu n tìmố int flag=0; for( int i=0; i Ví d :ụ ả ằ ị ướ ◦Tìm xem trong m ng có giá tr nào b ng k cho tr c không ố
ả ự ả
ả ể ◦Tìm xem trong m ng có s âm nào không
◦Ki m tra xem m ng có ph i t ầ
tăng d n không 21 if (a[i] == k) flag=1; V trí = 2 1 3 Tìm thành công S l n so sánh: 3 22 1 3 Không tìm th yấ S l n so sánh: 8 23 Gi ầ ử ả ố ị
, k là giá tr ế ả ử
s a là tên m ng, n là s ph n t
ố
mu n đ m int dem=0;
for( int i=0; i 1 3 if (a[i] == k) dem++; Ví d :ụ ị ướ c ả ầ ử ằ
ẵ
ầ ử
ầ ử ươ ế
ế
ế ◦Đ m s ph n t
ố
◦Đ m s ph n t
ố
◦Đ m s ph n t
ố b ng giá tr cho tr
ch n trong m ng
ả
d ng trong m ng 24 ầ ử ố s a là tên m ng, n là s ph n t ị
, m là giá tr Gi
ả ử
ấ
ớ
l n nh t tìm đ ượ ả
c int m=a[0]; for( int i=0; i 1 3 if (m
m 71321 25 j
1 0 2 3 4 5 6 7 2 8 5 1 6 4 15 12
1 i N uế a[i] > a[j] thì đ i ch a[i], a[j] 26 j
2 1 3 4 5 6 7 0 8 5 2 6 4 15 1 12
2 i N uế a[i] > a[j] thì đ i ch a[i], a[j] 27 j
3 2 4 5 6 7 0 1 8 5 6 4 15 1 2 12
4 i N uế a[i] > a[j] thì đ i ch a[i], a[j] 28 0 1 j
4 3 5 6 7 2 1 2 8 6 5 15 4 12
5 i N uế a[i] > a[j] thì đ i ch a[i], a[j] 29 0 1 2 3 4 5 6 7 1 2 4 5 6 8 12 15 N uế a[i] > a[j] thì đ i ch a[i], a[j] 30 Gi for ( int i = 0; i < n 1; i++ ) for ( int j = i + 1; j < n; j++ ) if ( a[i] > a[j] ) { t = a[i] ;
a[i] = a[j];
a[j ] = t ; } 31 ả ử ầ ử ả ố s a là tên m ng, n là s ph n t ề ề ả ộ ề 1. Khái ni mệ
ộ
ả
2. M ng m t chi u
ộ ố
3. M t s bài toán trên m ng m t chi u
ả
4. M ng hai chi u
ộ ố
5. M t s bài toán trên m ng hai chi u 32 ề ả C/C++ h tr m ng nhi u chi u ỗ ợ ả ề ề D ng đ n gi n nh t c a m ng nhi u chi u là
ủ ề ề ả ấ ạ
ả ả
ơ
ề
m ng hai chi u ự ữ ủ ả ấ M ng hai chi u
ộ
m ng m t chi u ề th c ch t là m ng c a nh ng
ề ả
ả Có th xem
ể ậ ả ộ ồ m ng hai chi u ề là m t ma tr n g m 33 các dòng và các c tộ Cú pháp khai báo m ng:ả ố ◦rowSize: s dòng
◦columnSize: s c t
ố ộ Ví d :ụ 34 int a[3][4]; M ng ph i đ ả ượ ườ ố c khai báo t ng minh s dòng, ả
ố ộ
s c t ậ ộ ử
i dòng i c t j, s Đ truy c p ph n t
d ng cú pháp: ể
ụ ạ
ầ ử ả
m ng t
ả
tên_m ng[i][j] Đ duy t t
ườ
ề
chi u, th ể ệ ấ ả ầ ử t c các ph n t
ng dùng 2 vòng l p ả
trong m ng hai
ặ for: for( int i=0; i for( int j=0; j 35 //… Cú pháp khai báo và kh i t o: ở ạ Ví d :ụ 36 int a[][4] = {{1,2,3,4}, {5,6,7,8},{9,10,11,12}}; Chú ý khi khai báo và kh i t o m ng 2 chi u: ể ố ố ◦S dòng đ tr ng ố ượ ự ố ị c xác đ nh d a vào s dòng ả
ở ạ ◦S dòng c a m ng đ
ủ
ầ
trong ph n kh i t o ầ ử ủ ố ả ằ ỗ ◦S ph n t c a m i dòng ph i b ng nhau ị ầ ử ◦Giá tr các ph n t ỗ
trong m i dòng đ ượ
ằ ấ ặ
c đ t trong
ộ
ặ
c p {}, các hàng phân cách nhau b ng m t d u
ph yẩ 37 ở ạ ề ả XuatMang(a, d, c); }
void NhapMang( int a[][N], int d, int c )
{ for( int i=0; i for( int j=0; j cout<<“a[”<>a[i][j]; #include } }
void XuatMang( int a[][N], int d, int c )
{ for( int i=0; i for( int j=0; j cout< } 38 int d, c, a[M][N];
cout<<“Nhap so luong dong:”;
cin>>d;
cout<<“Nhap so luong cot:”;
cin>>c;
// gọi hàm để nhập mảng
NhapMang(a, d, c);
// gọi hàm để xuất mảng
cout<< "In mang:\n"; } cout<< "In mang:\n";
XuatMang(a, d, c); }
void NhapMang( int a[][N], int d, int c )
{ } }
void XuatMang( int a[][N], int d, int c )
{ for( int i=0; i for( int j=0; j cout< } int d, c, a[M][N];
cout<<“Nhap so luong dong:”;
cin>>d;
cout<<“Nhap so luong cot:”;
cin>>c;
// gọi hàm để nhập mảng
NhapMang(a, d, c);
// gọi hàm để xuất mảng } 39 ề ề ả ộ ề 1. Khái ni mệ
ộ
ả
2. M ng m t chi u
ộ ố
3. M t s bài toán trên m ng m t chi u
ả
4. M ng hai chi u
ộ ố
5. M t s bài toán trên m ng hai chi u 40 ề ả Tính t ng, tích các ph n t ầ ử ả ổ m ng Tìm ki m trên m ng theo đi u ki n cho tr ế ề ệ ả ướ
c Đ m s ph n t
ố ầ ử ả ế ệ ướ ề
m ng theo đi u ki n cho tr c Tìm ph n t ầ ử ớ ấ ủ ả ấ ỏ l n nh t, nh nh t c a m ng Duy t m ng hai chi u theo dòng ho c c t
ộ
ề ệ ặ ả Duy t m ng hai chi u theo đ ệ ườ ng chéo chính 41 ả
ườ ụ ề
ng chéo ph ặ
ho c đ Ví d : Xu t các s trên dòng th 2: ụ ứ ố
ấ
for (int i=0; i Ví d : Tính t ng các s trên dòng th 1:ộ
ộN i dung trình bày
N i dung trình bày
ả
ả
ề Khai báo
Khai báo
ề
ộ
ộ
2. M ng m t chi u:
2. M ng m t chi u:
type arrayName[size];
ộ
ộ
ả
ả
ử ụ
ề S d ng
ử ụ
S d ng
ề
2. M ng m t chi u:
2. M ng m t chi u:
ả
ả
ố
ề Tính s bytes
ố
Tính s bytes
ề
ộ
ộ
2. M ng m t chi u:
2. M ng m t chi u:
ề Khai báo và
Khai báo và
ề
ộ
ộ
2. M ng m t chi u:
2. M ng m t chi u:
ả
ả
ở ạ
kh i t o
ở ạ
kh i t o
type arrayName[]= {value1, value2, ..., valuen};
ề Khai báo và
Khai báo và
ề
ộ
ộ
2. M ng m t chi u:
2. M ng m t chi u:
ả
ả
ở ạ
ở ạ
kh i t o (tt)
kh i t o (tt)
ộ
ộ
ả
ả
ề Ví d 1ụVí d 1ụ
ề
2. M ng m t chi u:
2. M ng m t chi u:
ế
ế
ề
ề
ậ
ậ
ả
ả
Vi
Vi
ấ
t hàm nh p, xu t m ng 1 chi u
ấ
t hàm nh p, xu t m ng 1 chi u
ả
ả
ề Ví d 2ụVí d 2ụ
ề
ộ
ộ
2. M ng m t chi u:
2. M ng m t chi u:
ử ụ
ử ụ
ạ
ạ
ẫ
ẫ
ố
ố
S d ng hàm t o s ng u nhiên (c1)
S d ng hàm t o s ng u nhiên (c1)
int random(int n)
ụ ử ụ
ụ ử ụ
ạ
ạ
ẫ
ẫ
ố
ố
Ví d : S d ng hàm t o s ng u nhiên
Ví d : S d ng hàm t o s ng u nhiên
randomize();
for( int i=0; i
a[i] = random(100);
#include
ử ụ
ử ụ
ạ
ạ
ẫ
ẫ
ố
ố
S d ng hàm t o s ng u nhiên (c2)
S d ng hàm t o s ng u nhiên (c2)
ụ ử ụ
ụ ử ụ
ạ
ạ
ẫ
ẫ
ố
ố
Ví d : S d ng hàm t o s ng u nhiên
Ví d : S d ng hàm t o s ng u nhiên
srand ( time(NULL) );
for( int i=0; i
#include
ộ
ộN i dung trình bày
N i dung trình bày
ả
ả
3. M t s bài toán trên m ng 1
3. M t s bài toán trên m ng 1
ộ ố
ộ ố
chi uềchi uề
ầ ử
ầ ử
ổ
ổ
ị
ị
Tính t ng, tích giá tr các ph n t
Tính t ng, tích giá tr các ph n t
ề
ề
ệ
ệ
ả
Tìm ki m trên m ng theo đi u ki n
ả
Tìm ki m trên m ng theo đi u ki n
cho tr
cho tr
ế
ế
cướ
cướ
ế
ế
ọ
ọ
Minh h a: tìm ki m
Minh h a: tìm ki m
ị
5
Giá tr tìmị
a
4
2
0
7 13 5 21 6
5
2
7
6
8 15
ố ầ
ế
ế
ọ
ọ
Minh h a: tìm ki m
Minh h a: tìm ki m
9
ị
Giá tr tìm
a
4
2
0
7 13 5 21 6
5
2
7
6
8 15
ố ầ
ầ ử ả
ầ ử ả
ệ
ệ
ề
ề
m ng theo đi u ki n
m ng theo đi u ki n
ố
ế
ế
Đ m s ph n t
ố
Đ m s ph n t
cướ
cướ
cho tr
cho tr
a
4
2
0
7 13 5 21 6
5
2
7
6
8 15
ầ ử ớ
ầ ử ớ
ả
ả
Tìm ph n t
Tìm ph n t
ấ
l n nh t m ng
ấ
l n nh t m ng
a
4
2
0
7 13 5 21 6
5
2
7
6
8 15
ế
ế
ắ
ắ
ầ
ầ
ả
ả
ọ
ọ
S p x p m ng tăng d n: Minh h a
S p x p m ng tăng d n: Minh h a
ổ
ỗ
ế
ế
ắ
ắ
ầ
ầ
ả
ả
ọ
ọ
S p x p m ng tăng d n: Minh h a
S p x p m ng tăng d n: Minh h a
ổ
ỗ
ế
ế
ắ
ắ
ầ
ầ
ả
ả
ọ
ọ
S p x p m ng tăng d n: Minh h a
S p x p m ng tăng d n: Minh h a
ổ
ỗ
ế
ế
ắ
ắ
ầ
ầ
ả
ả
ọ
ọ
S p x p m ng tăng d n: Minh h a
S p x p m ng tăng d n: Minh h a
ỗ
ổ
ế
ế
ắ
ắ
ầ
ầ
ả
ả
ọ
ọ
S p x p m ng tăng d n: Minh h a
S p x p m ng tăng d n: Minh h a
ổ
ỗ
ế
ế
ắ
ắ
ầ
ầ
ả
S p x p m ng tăng d n
ả
S p x p m ng tăng d n
ộ
ộN i dung trình bày
N i dung trình bày
ớ
ớ
ả
ả
ề Gi
Gi
ề
ệ
i thi u
ệ
i thi u
4. M ng hai chi u:
4. M ng hai chi u:
ả
ả
ề Khai báo
Khai báo
ề
4. M ng hai chi u:
4. M ng hai chi u:
type arrayName[rowSize][columnSize];
ả
ả
ề L u ýưL u ýư
ề
4. M ng hai chi u:
4. M ng hai chi u:
Khai báo và kh i ở
ề Khai báo và kh i ở
ề
4. M ng hai chi u:
4. M ng hai chi u:
ả
ả
t oạt oạ
type arrayName[][columnSize] = {
{value1,value2,...,valueN},
{value1,value2,...,valueN},
{...},
{value1,value2,...,valueN}
};
ả
ả
ề Chú ý
Chú ý
ề
4. M ng hai chi u:
4. M ng hai chi u:
ế
ế
ề
ề
ấ
ấ
ậ
ậ
ả
ả
Vi
Vi
t hàm nh p, xu t m ng 2 chi u (1)
t hàm nh p, xu t m ng 2 chi u (1)
ế
ế
ề
ề
ấ
ấ
ậ
ậ
ả
ả
Vi
Vi
t hàm nh p, xu t m ng 2 chi u (2)
t hàm nh p, xu t m ng 2 chi u (2)
srand(time(NULL));
for( int i=0; i
for( int j=0; j
#include
ộ
ộN i dung trình bày
N i dung trình bày
ả
ả
5. M t s bài toán trên m ng hai
5. M t s bài toán trên m ng hai
ộ ố
ộ ố
chi uềchi uề
ệ
ệ
ề
ề
ả
ả
Duy t m ng hai chi u theo dòng
Duy t m ng hai chi u theo dòng

