Câu hỏi về chèn phần tử trong mảng 1 chiều
Em đang học tới bài mảng 1 chiều trên cpp.daynhauhoc.com và có 1 câu hỏi: “Các bạn thử giải thích trong đoạn code thực hiện đẩy các phần tử đứng sau vị trí insert_position này lui sau một vị trí, tại sao mình cho chỉ số bắt đầu từ (N - 2) nhé.”. Em đã thử trừ 1 số khác như 1, 3, 5, 6… và em thấy N - 1 gần như không khác gì N - 2. Vậy mục đích N - 2 có ý gì khác không? Em vẫn chưa tìm ra được nguyên nhân tại sao nên là N - 2
#include
#include
#include
using namespace std;
#define MAX_SIZE 100
int main()
{
//initialize array
int32_t arr[MAX_SIZE];
int32_t N = 5;
for (int32_t index = 0; index <= N - 1; index++) {
arr[index] = index + 1;
}
//input insert_value and insert_position from keyboard
int32_t insert_value, insert_position;
cout << "Enter insert_value: "; cin >> insert_value;
cout << "Enter insert_position: "; cin >> insert_position;
//inserting
N++;
for (int32_t i = N - 2; i >= insert_position; i--) {
int32_t after_i = i + 1;
arr[after_i] = arr[i];
}
arr[insert_position] = insert_value;
//output array
for (int32_t index = 0; index <= N - 1; index++)
cout << arr[index] << " ";
cout << endl;
system("pause");
return 0;
}
Các bạn thử giải thích trong đoạn code thực hiện đẩy các phần tử đứng sau vị trí insert_position này lui sau một vị trí, tại sao mình cho chỉ số bắt đầu từ (N - 2) nhé.
// why (N - 2)?
for (int32_t i = N - 2; i >= insert_position; i–) {
int32_t after_i = i + 1;
arr[after_i] = arr[i];
}
Lúc dùng N - 1 thì mình sẽ tạo ra phần tử thừa ở vị trí N => N - 2 vừa giảm được 1 bước lặp vừa bỏ bớt đi được phần tử thừa, với lại phần tử thừa cũng có một số nguy hại của nó. Mình chỉ nghĩ ra như vậy :v.
Đương nhiên phải là N - 2 bởi vì trong phần insert
Bạn có thể thấy là
after = i + 1.Ví dụ mảng ban đầu có 5 phần tử, sau khi thêm 1 ta sẽ cho
N++=> N = 6. Nếu chạy từN - 1có nghĩa là giá trịi = 5=>after = 6. Nhưng bạn thấy đó, làm gì có phần tử nào cóindexlà 6 trong khi mảng chỉ có 6 phần tử? Vì index bắt đầu bằng 0. Thế nên phải làN - 2Em mới đầu nghĩa rằng N - 1 chính là chỉ số cuối cùng trong mảng, nên khi mình tạo i = N - 1 có nghĩa là mình gắn i là chỉ số cuối cùng sau đó từ chỉ số cuối cùng đó mình di chuyển vô vị trí mình cần chèn vào.
Em mới đầu nghĩa rằng N - 1 chính là chỉ số cuối cùng trong mảng, nên khi mình tạo i = N - 1 có nghĩa là mình gắn i là chỉ số cuối cùng sau đó từ chỉ số cuối cùng đó mình di chuyển vô vị trí mình cần chèn vào.
Coi kĩ, viết ra giấy. Đừng vội chạy code. Bạn đang bị phụ thuộc vào máy.
Từ hôm qua giờ em viết ra giấy hơn 10 tờ rồi ý, mà công nhận khả năng toán em kém thật, cứ lo để ý thuật toán mà quên phần “index = 6 không tồn tại”. Tại em cũng lên coi thuật toán bài này và thấy cũng có người chọn N - 1 chứ không phải N - 2. Mà em thì cứ nghĩ N - 1 dễ hiểu hơn vì đơn N - 1 là chỉ số cuối mảng