ề

ả

ộ

Bài 8 – M ng m t chi u (Dãy)

ộ

ậ

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 1

ộ B  môn K  thu t máy tính – Khoa  CNTT

ề ộ ề ả ệ  Khái ni m m ng m t chi u  Khai báo m ngả ả ấ  Nh p/xu t m ng ề ả  Các bài toán v  m ng m t chi u

ệ

ộ

ề ả 1. Khái ni m m ng m t chi u

ụ

ề ả ộ ổ ứ i d ng

5

7

1

9

A0 A1 A2 A3 A4

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 2

ộ B  môn K  thu t máy tính – Khoa  CNTT

ộ ả  M ng m t chi u là m t công c  cho  ữ ệ ướ ạ  ch c qu n lý d  li u d phép t “dãy”  Ví d :ụ ốA: Xét dãy s  sau đây: 4

ầ ử ủ

ả

Các ph n t

c a m ng

ồ

ư

ủ

ầ ử ấ ỳ ủ ườ ng

ề ề ầ ử ộ ả ,   M ng m t chi u bao g m nhi u ph n t ế ở ầ ử ượ ặ ỗ  đ c đ c tr ng b i hai y u  m i ph n t ầ ị ầ ử và v  trí c a ph n  ị ủ : ố Giá tr  c a ph n t t tử trong m ngả ộ  M t ph n t ệ ượ c kí hi u là  đ ả  b t k  c a m ng th A[i], trong đó:

ạ ươ

ọ Tin h c đ i c

ng 2

­ 3

ầ ử ả trong m ng

+ A là tên m ngả ủ ị + i là v  trí c a ph n t ỹ ậ ộ B  môn K  thu t máy tính – Khoa  CNTT

2. Khai báo m ngả

ộ ề ố ử ụ

ươ

ự ả ấ

ề

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 4

ộ B  môn K  thu t máy tính – Khoa  CNTT

ờ ề ả  Mu n s  d ng m ng m t chi u trong  ả ng trình thì ph i khai báo nó ch ự  Khai báo m ng th c ch t là s  khai báo  ể ữ ệ ế ồ đ ng th i nhi u bi n có cùng ki u d  li u  Có nhi u cách khai báo khác nhau

ề

ả

ộ

Các cách khai báo m ng m t chi u:

Cách 1:

ầ ử ố

ố

Ki uDLể

TênM ngả [S  ph n t

t

i đa

];

Ví d  1:ụ

ầ ử

ỗ

ầ

i đa 100 ph n t

, m i ph n

ả ộ ố

int  A[100];   ố M ng này có t  là m t s  nguyên ẽ ạ

ế

ử t Khai báo trên s  t o ra 100 bi n nguyên:

A[0], A[1], ... , A[99]

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 5

ộ B  môn K  thu t máy tính – Khoa  CNTT

Ví d  2:ụ

char  B[60];

ầ ử ỗ , m i

ể ự :

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 6

ộ B  môn K  thu t máy tính – Khoa  CNTT

ố ả M ng này có t i đa 60 ph n t ự ộ ầ ử  là m t kí t ph n t ế ẽ ạ Khai báo trên s  t o ra 60 bi n ki u kí t B[0], B[1], ... , B[59]

Cách 2:

ầ ử ố

ố

vector   

>  TênM ngả (S  ph n t

t

i đa

);

Ví d :ụ

ầ

ỗ

vector  < int >  A(100);   ầ ử i đa 100 ph n t

, m i ph n

ả ộ ố

ố M ng này có t  là m t s  nguyên ố ử ụ

ả

ở ầ

ươ

ế

ử t Chú ý: Mu n s  d ng cách khai báo này thì ph i  vi

t dòng sau đây

ng trình:

đ u ch #include  

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 7

ộ B  môn K  thu t máy tính – Khoa  CNTT

ậ

ấ

ả

3. Nh p/xu t m ng

ừ bàn phím:

ề ế

ậ ữ ệ ấ ự ầ ử ụ ặ

ầ ử .

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 8

ộ B  môn K  thu t máy tính – Khoa  CNTT

ầ ặ ầ ả  Nh p d  li u cho m ng t ậ ữ ệ Th c ch t là nh p d  li u cho nhi u bi n,  do đó c n s  d ng vòng l p. Ví d  1:ụ ố ộ ậ Nh p m t dãy s  nguyên có 8 ph n t C n l p 8 l n!

ệ

ậ

Các l nh nh p:

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 9

ộ B  môn K  thu t máy tính – Khoa  CNTT

int  A[8];  for (int i = 0; i < 8; i ++)  {   cout << "Nhap so thu " << i << " = " ;   cin >> A[i] ;  }

ể

ệ

ị

ấ Các l nh xu t (hi n th ):

ầ ử ố ừ ệ ậ Ví d  2:ụ Hi n dãy s  v a nh p (8 ph n t ) ra màn hình.

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 10

ộ B  môn K  thu t máy tính – Khoa  CNTT

cout << "Day vua nhap la: "; for (int i = 0; i < 8; i ++)  cout << A[i] << "  " ;

ươ

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 11

ng trình: Ch #include  using namespace std; main()  { int  A[8];     for (int i = 0; i < 8; i ++)      {       cout << "Nhap so thu " << i << " = " ;       cin >> A[i] ;      }    cout << "Day vua nhap la: ";    for (int i = 0; i < 8; i ++)  cout << A[i] << "  " ; ộ B  môn K  thu t máy tính – Khoa   } CNTT

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 12

Cách 2: #include  #include  using namespace std; main()  { vector  < int >  A(8);     for (int i = 0; i < 8; i ++)      {       cout << "Nhap so thu " << i << " = " ;       cin >> A[i] ;      }    cout << "Day vua nhap la: ";    for (int i = 0; i < 8; i ++)  cout << A[i] << "  " ; ộ B  môn K  thu t máy tính – Khoa   } CNTT

Bài t p:ậ

ậ ố ự

ầ ử N là   ( N ph n t  bàn phím).

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 13

ộ B  môn K  thu t máy tính – Khoa  CNTT

ộ ệ ộ  Nh p m t dãy s  th c có  ậ ừ ị ấ ỳ m t giá tr  b t k  nh p t ậ ừ Hi n dãy v a nh p ra màn hình.

ươ

ng trình:

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 14

ộ N i dung ch #include  using namespace std; main()  { float  A[100];  int N ;    cout << "Nhap N = ";  cin >> N ;    for (int i = 0; i < N; i ++)      {       cout << "Nhap so thu " << i << " = " ;       cin >> A[i] ;      }    cout << "Day vua nhap la: ";    for (int i = 0; i < N; i ++)  cout << A[i] << "  " ; ộ B  môn K  thu t máy tính – Khoa   } CNTT

ề ả

ề

ộ

4. Các bài toán v  m ng m t chi u

ế ố ượ ng, trung

ấ ấ ỏ

ầ ử ỗ ắ ế

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 15

ộ B  môn K  thu t máy tính – Khoa  CNTT

ổ  Bài toán tính t ng, đ m s  l bình c ngộ ị ị ớ  Bài toán tìm giá tr  l n nh t, nh  nh t, v   trí ph n tầ ử ớ  Thêm ­ b t ph n t ổ  Bài toán đ i ch , s p x p dãy ...

Ví d  1:ụ

ậ ố ự ừ N s  th c t bàn phím

ủ

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 16

ộ B  môn K  thu t máy tính – Khoa  CNTT

ệ ổ ệ ộ  Nh p m t dãy có  ổ ồ r i tính t ng c a chúng Hi n t ng và hi n dãy ra màn hình.

ổ

ậ

Thu t toán tính t ng?

ầ ổ

ộ ố ộ ỗ ằ ậ ượ c m t s  thì đem c ng

ổ + Ban đ u t ng S b ng 0 + M i khi nh p đ nó vào t ng S

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 17

ộ B  môn K  thu t máy tính – Khoa  CNTT

ặ ạ (L p l ầ i N l n)

ậ

ổ

ố Thu t toán tính t ng N s :

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 18

ộ B  môn K  thu t máy tính – Khoa  CNTT

S = 0;    cout << "Nhap N = ";  cin >> N ;    for (int i = 0; i < N; i ++)      {       cout << "Nhap so thu " << i << " = " ;       cin >> A[i] ;       S = S + A[i] ;      }    cout << " Tong S = " << S ;

Bài t p:ậ

ậ bàn phím

ố ự ừ ủ

ệ

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 19

ộ B  môn K  thu t máy tính – Khoa  CNTT

ộ N s  th c t  Nh p m t dãy có  ộ ồ r i tính trung bình c ng c a chúng ộ ệ Hi n trung bình c ng và hi n dãy ra màn  hình.

ậ ứ

ụ

Bài t p  ng d ng:

ư ủ ả ầ 1. Nh p l

ượ ư ồ ậ ượ  bàn phím r i tính l ng m a c a b y ngày trong tu n  ng m a trung bình. ừ t

ả ử ộ ọ 2. Gi ể ậ bàn phím r i

ể

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 20

ộ B  môn K  thu t máy tính – Khoa  CNTT

ọ N môn h c. Hãy   s  m t h c kì có  ồ ọ ừ nh p đi m các môn h c t ủ ọ tính đi m trung bình c a h c kì ệ ố ằ ạ (t m coi các môn có h  s  b ng nhau)

Ví d  2:ụ

ồ

ậ

bàn phím r i tính

N s  th c t

ố ự ừ ủ ng c a dãy.

ộ  Nh p m t dãy có  ầ ử ươ ổ t ng các ph n t  d ệ Hi n t ng và hi n dãy ra màn hình.

ệ ổ ậ Thu t toán: ầ ổ + Ban đ u t ng S b ng 0 + L n l

c a dãy v i 0:

ổ

ằ ầ ử ủ t so sánh các ph n t ầ ử [i] > 0 thì c ng Aộ

A

ầ ượ N uế  Ph n t

ớ [i] vào t ng S

if  (A[i] > 0 )   S = S + A[i];

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 21

ộ B  môn K  thu t máy tính – Khoa  CNTT

Bài t p:ậ

ố ậ N s  nguyên t

ồ ừ  bàn  ầ ử ẵ ủ  ch n c a

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 22

ộ B  môn K  thu t máy tính – Khoa  CNTT

ệ ổ ộ  Nh p m t dãy có  ổ phím r i tính t ng các ph n t dãy. ệ  Hi n t ng và hi n dãy ra màn hình.

Ví d  3:ụ

ồ

bàn phím r i

ố ầ ử ẵ ủ

ệ

ộ ố ượ ệ ố ượ

ừ  ch n c a dãy. c và hi n dãy ra màn

ng các ph n t ượ ế ng đ m đ

ứ ố ượ

ng: D

ầ ử ủ

ể

ế ế  D b ng 0 ầ ượ ừ  A

ằ  c a dãy: t t ng ph n t ầ ử [i] ch nẵ   thì tăng D lên 1

ậ  Nh p m t dãy có N s  nguyên t ế đ m s  l  Hi n s  l hình. ậ Thu t toán: ầ + C n khai báo thêm bi n ch a s  l ầ + Ban đ u bi n + Ki m tra l n l N uế  Ph n t ỹ ậ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 23

ộ B  môn K  thu t máy tính – Khoa           if  (A[i] % 2 == 0 )   D = D + 1; CNTT

Bài t p:ậ

ậ ộ 1. Nh p m t dãy có N kí t ự ừ  t bàn phím.

ế

ữ 'K'. ng và hi n dãy ra màn hình.

ệ ố Đ m xem trong dãy có bao nhiêu ch   ệ ố ượ  Hi n s  l ộ ậ 2. Nh p m t dãy có N s  nguyên t

ầ ử ẵ ộ bàn phím   ch n

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 24

ệ ộ

ừ ồ r i tính trung bình c ng các ph n t ủ c a dãy. ệ  Hi n trung bình c ng và hi n dãy ra màn  hình. ộ B  môn K  thu t máy tính – Khoa  CNTT

ậ ứ

ụ

Bài t p  ng d ng:

ể ế ủ N sinh viên trong

bàn phím. ế ớ t l p có bao nhiêu sinh viên

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 25

ộ B  môn K  thu t máy tính – Khoa  CNTT

ể ổ ậ  Nh p đi m t ng k t c a  ớ ừ l p t Hãy cho bi ạ ọ ổ đ t h c b ng ổ (đi m t ng k t ế ≥ 7)

bàn phím. Hãy

ấ

ố ự ừ  l n nh t trong dãy.

ị ớ

ứ

ấ

Ví d  4:ụ ộ ậ  Nh p m t dãy có N s  th c t ầ ử ớ tìm ph n t ậ Thu t toán: ế ầ + C n khai báo thêm bi n ch a giá tr  l n nh t:  Max

ầ ử ầ

ủ

ầ + Ban đ u bi n

ằ ế  Max b ng ph n t

đ u tiên c a

ầ ượ ừ

ầ ử ủ

c a dãy:

A[i]

t t ng ph n t ấ ầ ử [i] > Max  thì l y luôn Max = ỹ

ậ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 26

dãy ể + Ki m tra l n l  N uế  Ph n t  A ộ B  môn K  thu t máy tính – Khoa           if  (A[i] > Max )   Max = A[i]; CNTT

4   2   7   5   1

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 27

ộ B  môn K  thu t máy tính – Khoa  CNTT

Ví d :ụ ộ + Cho m t dãy:       + Ban đ u ầ Max = A[0] = 4 ... + Max = A[2] = 7 ...

Bài t p:ậ

ậ ộ 1. Nh p m t dãy có bàn

phím. Hãy tìm ph n t

ậ

ừ ố N s  nguyên t ấ ầ ử ỏ  nh  nh t trong dãy. ố ự ừ  bàn phím.  N s  th c t ủ ị ấ  l n nh t và v  trí c a nó

ừ ộ 2. Nh p m t dãy có  ầ ử ớ Hãy tìm ph n t trong dãy. ộ ậ 3. Nh p m t dãy có bàn

ấ ả t c

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 28

ộ B  môn K  thu t máy tính – Khoa  CNTT

ị ố N s  nguyên t ấ ầ ử ớ  l n nh t và t phím. Hãy tìm ph n t ủ các v  trí c a nó trong dãy.

ậ ứ

ụ

Bài t p  ng d ng:

ậ ượ bàn

ừ ư ớ ấ

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 29

ộ B  môn K  thu t máy tính – Khoa  CNTT

ư Nh p l phím. Hãy xác đ nh ngày có m a l n nh t,  ượ l ư ủ N ngày t ng m a c a  ị ằ ng m a đó b ng bao nhiêu?

Ví d  5:ụ

ậ

ố ự ừ  bàn phím.  ủ ầ ử ầ ỏ ộ  Nh p m t dãy có N s  th c t Hãy xoá b  ph n t đ u tiên c a dãy.

ầ 4   2   5   1   7

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 30

ộ B  môn K  thu t máy tính – Khoa  CNTT

Ví d :ụ + Dãy ban đ u:       + Dãy sau khi xoá: 2   5   1   7

ậ

ầ ử Thu t toán xoá ph n t ?

ớ

ầ ử

Gán A[0] = A[1] A[1] = A[2] A[2] = A[3] A[3] = A[4] ... A[N­2] = A[N­1] ả N = N ­1   //Gi m b t 1 ph n t

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 31

ộ B  môn K  thu t máy tính – Khoa  CNTT

Bài t p:ậ

ậ ừ

phím. Hãy xoá b  ph n t

ậ ố N s  nguyên t ầ ử ứ ố ự ừ N s  th c t

ỏ ầ ử ố cu i cùng c a dãy.

ậ ố ự ừ

ỏ bàn  ủ  th  hai c a dãy.  bàn phím.  ủ  bàn phím.  k nh p ậ N s  th c t ủ ầ ử ứ k c a dãy ( th

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 32

ộ B  môn K  thu t máy tính – Khoa  CNTT

ộ 1. Nh p m t dãy có  ỏ ộ 2. Nh p m t dãy có  Hãy xoá b  ph n t ộ 3. Nh p m t dãy có  Hãy xoá b  ph n t ừ t bàn phím).

Ví d  6:ụ

ậ

ầ ử ầ ổ ố ự ừ  đ u tiên và ph n t bàn phím.  ầ ử

ỗ ủ ộ  Nh p m t dãy có N s  th c t Hãy đ i ch  ph n t cu i cùng c a dãy.

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 33

ộ B  môn K  thu t máy tính – Khoa  CNTT

ầ ổ ố Ví d :ụ + Dãy ban đ u:       + Dãy sau đ i ch : 4   2   5   1   7 ỗ 7   2   5   1   4

ổ

ỗ

ậ

Thu t toán đ i ch ?

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 34

ộ B  môn K  thu t máy tính – Khoa  CNTT

Bài t p:ậ

ộ ậ

ố ầ ử ầ ỗ ừ  bàn   đ u tiên và

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 35

ộ B  môn K  thu t máy tính – Khoa  CNTT

Nh p m t dãy có N s  nguyên t ổ phím. Hãy đ i ch  ph n t ầ ử ở ữ   ph n t gi a dãy.

Ví d  7:ụ

ộ ậ bàn phím.

ố ự ừ ề ế ắ ầ Nh p m t dãy có N s  th c t Hãy s p x p dãy theo chi u tăng d n.

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 36

ộ B  môn K  thu t máy tính – Khoa  CNTT

ầ ắ Ví d :ụ + Dãy ban đ u:       + Dãy sau s p x p: 4   2   5   1   7 ế 1   2   4   5   7

ắ ế

ậ

Thu t toán s p x p?

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 37

ộ B  môn K  thu t máy tính – Khoa  CNTT

Bài t p: ậ

ộ ậ

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 38

ộ B  môn K  thu t máy tính – Khoa  CNTT

ố ự ừ  bàn phím.  ầ ả ề ế ắ Nh p m t dãy có N s  th c t Hãy s p x p dãy theo chi u gi m d n.

ụ

ủ

ậ

ắ

ng d ng c a thu t toán s p

Ứ x pế

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 39

ộ B  môn K  thu t máy tính – Khoa  CNTT

ạ ữ ệ  Phân lo i d  li u ữ ệ ế  Tìm ki m d  li u  ...

Ví d  8:ụ

ộ ậ bàn

ầ ử ẵ ừ  ch n trong dãy

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 40

ộ B  môn K  thu t máy tính – Khoa  CNTT

ớ ộ ố  Nh p m t dãy A có N s  nguyên t phím. Hãy tách các ph n t thành m t dãy m i (dãy B).

ậ

Thu t toán tách dãy?

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 41

ộ B  môn K  thu t máy tính – Khoa  CNTT

Bài t p:ậ

ộ ậ

ố ự ừ  d bàn  ng trong

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 42

ộ B  môn K  thu t máy tính – Khoa  CNTT

Nh p m t dãy A có N s  th c t ầ ử ươ phím. Hãy tách các ph n t ớ ộ dãy thành m t dãy m i (dãy B).

Ví d  9:ụ

Xét hàm s  ố y = 2x2 + 3x + 1  trong đo n  ạ [a, b]

ậ ừ

bàn phím).

ầ

ằ

ậ ừ

(N nh p t

(a, b nh p t Chia đo n ạ [a, b] làm N ph n b ng nhau

bàn phím).

ạ

ị ủ

ầ i các đ u mút.

ị

x[1], x[2],..., x[N+1] y[1], y[2],..., y[N+1] ầ

Hãy tính giá tr  c a hàm t G i ý:ợ ầ 1. Xác đ nh các đ u mút:  ươ ứ ng  ng:  2. Tính các y t ặ (dùng vòng l p N+1 l n)

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 43

ộ B  môn K  thu t máy tính – Khoa  CNTT

Bài t p:ậ

ạ [a, b]

(cid:0)

y

12 (cid:0)

ậ ừ

x ố  Xét hàm s                            trong đo n    bàn phím).

ầ

ằ

(N nh p ậ

(a, b nh p t Chia đo n ạ [a, b] làm N ph n b ng nhau

ừ

t

bàn phím).

ị ủ

ạ

Hãy tính giá tr  c a hàm t

ầ i các đ u mút.

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 44

ộ B  môn K  thu t máy tính – Khoa  CNTT

Ứ

ụ ng d ng:

ẽ ể

ế

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 45

ộ B  môn K  thu t máy tính – Khoa  CNTT

ồ ồ ị  V  bi u đ , đ  th ỷ ợ i:  Trong Thu  l ế ấ ạ + Tính bi n d ng k t c u ấ ứ + Tính  ng su t + Tính mô men ...

EOL

ậ

ỹ

ạ ươ

ọ Tin h c đ i c

ng 2

­ 46

ộ B  môn K  thu t máy tính – Khoa  CNTT