2.Vector (Mảng động)

 

Đặt vấn đề.

Trong cuộc thi đường lên đỉnh Olympia có phần thi giải ô chữ.Ô chữ của chúng ta hôm nay được nằm trên m hàng (1 ≤m). Mỗi hàng gồm n chữ cái (n của mỗi hàng có thể thay đổi các giá trị khác nhau, nhưng sao cho (1 ≤ m*n≤106).

Rơ ràng trong bài toán này, khi ta chỉ được học về mảng: nếu ta khai báo char a[1001][1001] th́ mảng trên sẽ khai báo thiếu phần tử  (v́ điều kiện m*n ≤106, chẳng hạn m = 103, n =103 th́ mảng a[1001][1001] nó sẽ không chứa được phần tử  a[10000][100].Nếu ta khai báo như sau:

 

char a[1000001][1000001];

Khai báo như vậy th́ mảng chúng ta cỡ 1012 phần tử , như vậy sẽ bị tràn bộ nhớ (v́ mảng nên khai báo tầm tối đa khoảng 4.108 phần tử; nếu là 4.108 phần tử  th́ cũng chỉ được khai báo 1 mảng có số phần tử  đó).

Do đó, chúng ta cần một cấu trúc dữ liệu khác để có thể lưu trữ mà không bị tràn bộ nhớ. Đó chính là cấu trúc vector (mảng động). Lúc này chúng ta sẽ tạo ra vector 2 chiều và số phần tử  của nó luôn luôn thỏa măn m*n≤106.

 

 

Khái niệm.

Vector trong C++ là một mảng động có khả năng tự động thay đổi kích thước khi một phần tử được chèn hoặc xóa tùy thuộc vào như câu của tác vụ, với việc lưu trữ của chúng sẽ được vùng chứa tự động xử lư. Các phần tử vector được đặt trong bộ nhớ liền kề để chúng có thể được truy cập và duyệt qua bằng cách sử dựng iterator (con trỏ) hoặc bằng chỉ số. Như vậy nó sẽ có ưu điểm hơn mảng ở chỗ: Ta không cần phải khai báo kích thước giống như mảng v́ vector có thể tự động nâng kích thước lên.

Nếu ta thêm 1 phân tử vào vector đă đầy rồi, th́ nó sẽ tự động tǎng kích thước của nó lên để dành chỗ cho giá trị mới này.

Cú pháp:               vector<kiểu_dữ_liêu>tên_vector;

Ví dụ cho từng cách khởi tạo cụ thể:

* Với vector 1 chiều.

-Tạo một vector rỗng với kiểu dữ liệu int: vector <int> v1;

- Tạo một vector ban đầu có 4 phần tử là 10,2,10,5

vector <int> v2={10,2,10,5};

Ta có thể tổng quát tạo một vector có n phần tử có giá trị là x như sau:

vector <kiểu_dự_liệu> tên_vector (n,x);

  VD:  Nhập xuất.

 

Truy cập vào phần tử của vector bằng con trỏ iterator

 

 

 

 

 

* Với vector 2 chiều:

-Tạo một vector rỗng với kiểu dữ liệu int: vector <<vector<int> > v1;

- Khai báo vector với kích thước bạn đầu là 3*4:

   vector <vector <int>>v2(3,4);

-Khai báo vector 3*4 với các phần tử bằng 1:

vector<vector<int>>v3(3,vector <int> (4,1));

 

https://www.geeksforgeeks.org/2d-vector-in-cpp-with-user-defined-size/

 

 

 

 

 

 

 

 

VECTOR 1 CHIỀU

Một số hàm thành viên:

 

 

 

BÀI TẬP

 

 

Câu 1.DEMSO.CPP

 

     Trong một đăy số, Tí rất thích số ở giữa. Do đó, anh Bờm đă đố Tí rằng hăy nhập vào một số lượng số bất ḱ (số lượng các số luôn là số lẻ), t́m số ở chính giữa của đăy dó.

Dữ liệu:

 Vào từ file DEMSO.INP

   gồm nhiều ḍng, mỗi ḍng là một số thể hiện một số của đăy, các số thuộc phạm vi từ [0,105].

   Số lượng số không vụợt quá 106

Kết quả: Ghi ra file DEMSO.OUT là số nằm ở chính giữa.

ví dụ

DEMSO.INP

DEMSO.OUT

1

2

8

6

9

8

 

 

                     

Câu 2.KHACNHAU.CPP

    Cho một đăy số, mỗi số nằm trong đoạn từ 0 đến 109..

    Hăy đếm xem có bao nhiêu số khác nhau trong đăy số đă cho.

Dữ liệu Vào: từ fle KHACNHAU.INP gồm 1 ḍng là 1 dāy các số. Số trong dăy không quá 106 số.

Kết quả: 

Ghi ra file KHACNHAU.OUT là kết quả của bài toán

Ví dụ:

 

KHACNHAU.INP

KHACNHAU.OUT

1 5 3 4 2 4 5 7 8

7

 

 

Câu 3. CANHNHAU.CPP

     Trong một khu phố, có rất nhiều ngôi nhà, giữa 2 ngôi nhà bất ḱ chi có tối đa 1 con đường đi trực tiếp 2 chiều. Ở 1 ngôi nhà có thể có đường đi nói trực tiếp đến chính nó. Hai ngôi nhà cạnh nhau là 2 ngôi nhà khác nhau được nối với nhau bằng một con đường.

Tuy nhiên, trong một  vụ hỏa hoạn, danh sách các ngôi nhà kề với nhau đă bị thiệu rụi, chỉ c̣n lại danh sách các con đường nối giữa 2 ngôi nhà. Từ danh sách này, các bạn hăy khôi phục lại xem với mỗi ngôi nhà th́ cạnh với những ngôi nhà nào khác.

Dữ liệu: Vào từ file CANHNHAU.INP gồm:

+ Ḍng đầu gôm 2 số nguyên N và M lần lượt tương ứng là số ngôi nhà và số con đường 2 chiều (0≤N,M≤103)

- M ḍng tiếp theo mỗi ḍng gồm 2 chỉ số u, v: là con đường nối trực tiếp giữa 2 ngôi nhà u, v.

Kết quả: Ghi ra file CANHNHAU.OUT là N ḍng, ḍng thứ i gồm những ngôi nhà cạnh với ngôi nhà i. Kết thúc mỗi ḍng là một số 0. (Nếu ḍng có nhiều số th́ các số cách nhau bởi 1 dấu cách trống)

Ví dụ:

 

CANHNHAU.INP

CANHNHAU.OUT

5 6

3 5

5 2

3 4

4 1

1 2

5 1

4 2 5 0

5 1 0

5 4 0

3 1 0

3 2 1 0

 

 



Câu 4. LIENTHONG.CPP

    Một đất nước X có N khu dân cư và giữa các khu dân cư có M con đường 1 chiều nối trực tiếp giữa 2 khu dân cư. Hiện nay t́nh h́nh covid 19 đang diễn biến hết sức phức tạp, đất nước X lên phương án để chia N khu dân cư trên thành K nhóm (để dễ kiểm soát dịch bệnh) sao cho trong mỗi nhóm th́ một khu dân cư bất kỳ phải đi đến được các khu dân cu c̣n lại trong nhóm đó. Các bạn hăy giúp đất nước X t́m K, sao cho K nhỏ nhất

Dữ liệu: Vào từ file LIENTHONG.INP gồm:

+ Ḍng đầu tiên gồm 2 số nguyên dương N, M (N≤ 100; M≤200)

+ M ḍng sau, mỗi ḍng gồm 2 số u, v chỉ đường đi 1 chiều từ khu dân cư u đến khu dân cư v

Kết quả: Ghi ra file LIENTHONG.OUT số K là kết quả của bài toán

Ví dụ:

 

LIENTHONG.INP

LIENTHONG.OUT

6 7

1 3

2 1

5 3

3 2

4 6

6 5

6 4

3

 

 

 

 

 Giải thích: Chia làm 3 nhóm:

+ Nhóm 1 gồm các khu dân cu:1,2,3;

+Nhóm 2 gồm các khu dân cu:4,6;

+Nhóm 3 gồm các khu dân cư:5;

 

 

 

 

Câu 5.SEQDIV.CPP

Cho 2 số nguyên dương n và k.Hăy đếm số lượng dāy ai, a2 ,., an sao cho:

+Các số ai nằm trong đoạn từ 1 đến k.

+ar chia hét cho art học ai+chia hét cho ai (chi dựrgc phép 1 trong 2 kiên này xay ra,không được xay ra dong thoi).

Dú liêu: Vào tir file SEQDIV .INP gôm 2 số n vàk(n≤102;k≤2*101)

Kết quả:  Ghi ra file SEQDIV.OUT là số lượng dāy số thỏa mǎn. Kết quàliy phần dự cho 109+7

 

Ví dụ:

SEQDIV.INP

SEQDIV.OUT

4 3

8

 

Giải thích8 đăy thoa măn là(1,2,1,2);(1,2,1,3);(1,3,1,2);(1,3,1,3); (2,1,2,1);(2,1,3,1);(3,1,2,1);(3,1,3,1).