CTDL và giải thuật - Hoán đổi phần tử nhỏ nhất đầu tiên và phần tử lớn nhất cuối cùng

Nhập vào một số nguyên dương n, tiếp theo là n số nguyên lần lượt là các phần tử trong dãy a.

Hãy hoán đổi phần tử nhỏ nhất đầu tiên và phần tử lớn nhất cuối cùng trong dãy đó. In dãy sau khi hoán đổi ra màn hình, phía sau mỗi phần tử có đúng một khoảng trắng.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    5
    1 2 3 4 5

    5 2 3 4 1

    Với a = [1, 2, 3, 4, 5] thì kết quả mong muốn là:
    "5 2 3 4 1 ".
     
  • Test mẫu 2:
     
    Input Output

    6
    1 1 4 4 3 3

    4 1 4 1 3 3

    Với a = [1, 1, 4, 4, 3, 3] thì kết quả mong muốn là:
    "4 1 4 1 3 3 ".

Hướng dẫn bài tập.

Với bài tập này chúng ta cần làm hai việc đó là: tìm phần tử nhỏ nhất đầu tiên và phần tử lớn nhất cuối cùng của dãy.

Lưu ý là khi nói đến tìm phần tử thì chúng ta phải tìm chỉ số của phần tử đó.

Code mẫu tìm vị trí của phần tử nhỏ nhất đầu tiên:

int searchMin(int a[], int n){
	int k = 0;
	for (int i = 1; i < n; i++){
		if (a[k] > a[i]){
			k = i;
		}
	}
	return k;
}

Code mẫu tìm vị trí của phần tử lớn nhất cuối cùng.

int searchMax(int a[], int n){
	int k = 0;
	for (int i = 1; i < n; i++){
		if (a[k] <= a[i]){
			k = i;
		}
	}
	return k;
}

Cách hoán đổi hai giá trị a và b:

Để hoán đổi hai phần tử này cho nhau ta hãy xem bài toán bên dưới.

Có hai ly nước, ly màu vàng chưa nước màu đỏ, ly màu đỏ chưa nước màu vàng, hay hoán đổi nước trong hai ly cho nhau (ly mà vàng chưa nước màu vàng, lý màu đỏ chưa nước màu đỏ).

Việc này thật khó khăn nếu bạn chỉ có 2 cái ly, vì hai ly đều đang chứa nước (giống như hai biến đều đang chưa giữ liệu).

Việc cần làm là cần thêm một ly thứ 3 (một biến khác dùng làm biến trung gian).

Thực hiện hoán đổi giá trị bằng 3 bước sau:

Bước 1: Đổ nước từ ly màu vàng sang ly trung gian (temp = a).

Bước 2: Đổ nước từ ly màu đỏ sang ly vàng (a = b).

Bước 3: Đổ nược từ ly trung gian qua ly màu đỏ (b = temp).

Code mẫu hàm hoán đổi vị trí:

int swap(int a, int b){
	int temp = a;
	a = b;
	b = temp;
}

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int searchMin(int a[], int n){
	int k = 0;
	for (int i = 1; i < n; i++){
		if (a[k] > a[i]){
			k = i;
		}
	}
	return k;
}
int searchMax(int a[], int n){
	int k = 0;
	for (int i = 1; i < n; i++){
		if (a[k] <= a[i]){
			k = i;
		}
	}
	return k;
}
void prinArray(int a[], int n){
	for (int i = 0; i < n; i++){
		cout << a[i] << " ";
	}
}
int a[100001];
int main(){
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	int csMin = searchMin(a, n);
	int csMax = searchMax(a, n);
	swap(a[csMin], a[csMax]);
	prinArray(a, n);
	
	return 0;
}