Tham khảo:

Viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong báo học:

void Insertion_Sort(int a[], int n){

int pos, i;

int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử

for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp

x = a[i]; pos = i-1;

//tìm vị trí chèn x

while((pos>=0)&&(a[pos]>x)){

                //kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới

a[pos+1] = a[pos];

pos--;

}

a[pos+1] = x;//chèn x vào danh sách

}

}

void main()

{

int a[5] = {8, 4, 1, 6, 5};

Insertion_Sort(a, 5);

cout<<"Mang sau khi sap xep:"<<endl;

for(int i=0;i<5;i++){

cout<<a[i]<<" ";

}

system("pause");

Tham khảo:

Sắp xếp nổi bọt

=> Ưu điểm:

• Là thuật toán cơ bản, dễ hiểu, phù hợp cho người bắt đầu học về sắp xếp

• Đoạn code ngắn gọn, dễ nhớ.

Sắp xếp chèn tuyến tính

=> Ưu điểm:

Thao tác thực hiện đơn giản, dễ hiểu.

Thể hiện sự hiệu quả cao đối với các số liệu nhỏ.

Tại các tình huống thực tế, Insertion Sort tỏ ra hiệu quả hơn so với các thuật toán có độ phức tạp khác (ví dụ Bubble sort).

Rất phù hợp đối với các số liệu đã được sắp xếp theo thứ tự sẵn.

Tính ổn định, không làm thay đổi nhiều thứ tự các nguyên tố gốc.

Cách sắp xếp có tính phương pháp, tuân theo nguyên tắc cụ thể, dễ nhớ và sử dụng.

Tham khảo:

Tìm kiếm là một vấn đề phổ biến trong lập trình, đặc biệt là trong các ứng dụng liên quan đến quản lý dữ liệu. Dưới đây là một số ví dụ về bài toán tìm kiếm trong thực tế:

- Tìm kiếm sản phẩm trong cơ sở dữ liệu của một trang thương mại điện tử.

- Tìm kiếm thông tin liên hệ của một người trong danh sách khách hàng của một doanh nghiệp.

- Tìm kiếm một file hoặc thư mục trong hệ thống tệp của máy tính.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu y tế để tìm kiếm bệnh nhân cần điều trị.

- Tìm kiếm các bản ghi trong cơ sở dữ liệu của một trang tuyển dụng để tìm kiếm ứng viên phù hợp.

Tham khảo:

#Trả về chỉ số của x trong arr nếu tồn tại, nếu không có sẽ trả về -1

def binary_search(arr, low, high, x):

    #Trường hợp cơ sở

    if high >= low:

        mid = (high + low) // 2

        #Nếu phần tử có tồn tại ở phần giữa của mảng

        if arr[mid] == x:

            return mid

        #Nếu phần tử nhỏ hơn mid, nó sẽ nằm ở phía bên trái của mảng điểm gốc là tử phần tử mid

        elif arr[mid] > x:

            return binary_search(arr, low, mid - 1, x)

        #Nếu không, phần tử sẽ nằm bên phải

        else:

            return binary_search(arr, mid + 1, high, x)

    else:

        #Phần tử không tồn tại trong tập hợp

        return -1

#Khởi tạo tập hợp

arr = [ 2, 3, 4, 10, 40 ]

x = 10

#Gọi hàm

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:

    print("Phần tử cần tìm có chỉ số là ", str(result))

else:

    print("Phần tử cần tìm không có trong mảng.")

Tham khảo:

a. Viết chương trình phython thực hiện tìm kiếm tuần tự

def search(arr, n, x):

    for i in range (0, n):

        if (arr[i] == x):

            return i;

    return -1;

# Driver Code

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

    print("Element is not present in array")

else:

    print("Element is present at index", result);

b. Viết phiên bản tìm kiếm tuần tự thứ hai, dùng vòng lặp for thay cho vòng lặp while (hoặc ngược lại).

def search(arr, n, x):

    for i in range (0, n):

        if (arr[i] == x):

            return i;

    return -1;

# Driver Code

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

    print("Element is not present in array")

else:

    print("Element is present at index", result);

c. Viết phiên bản tìm kiếm tuần tự có thêm hai tham số đầu vào lo và hi tương tự như của hàm index. So sánh kết quả với phương thức index của phython.

def search(arr, n, x):

    for i in range (0, n):

        if (arr[i] == x):

            return i;

    return -1;

# Driver Code

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

    print("Element is not present in array")

else:

    print("Element is present at index", result);

Tham khảo:

a) Gợi ý

Bước 1: Ta khai báo một mảng tĩnh số nguyên có 100 ô nhớ int a[100].

Bước 2: Ta khai báo số nguyên int n là số lượng phần tử có trong mảng với điều kiện n>1 hoặc n<100 nếu không thỏa mãn thì yêu cầu nhập lại n.

Bước 3: Ta khỏi tạo hàm void Nhap(int a[], int n) dùng để nhập dữ liệu từ bàn phím cho mảng. Trong hàm ta sử dụng vòng for bắt đầu từ int i =0 và kết thúc khi i

Bước 4: Ta khởi tạo hàm void Xuat(int a[], int n) dùng để hiển thị dữ liệu từ mảng ra màn hình. Trong hàm ta sử dụng vòng for bắt đầu từ int i =0 và kết thúc khi i

Bước 5: Ta khởi tạo hàm int TimKiem(int a[], int n) dùng để tìm kiếm phần tử; ta khai báo biến int x là số cần tìm và nhập vào giá trị của x; tiếp theo sử dụng vòng lặp for bắt đầu từ int i =0 và kết thúc khi i

Bước 6: Trong hàm main ta gọi hàm Nhap(a,n), Xuat(a,n) để hiển thị mảng gốc ta gọi thêm hàm TimKiem(a,n) rồi chạy chương trình.

b) Sắp xếp một dãy số giảm dần

#include

int main(){

int a[100];

int n;

printf("\nNhap so luong phan tu n = ");

do{

scanf("%d", &n);

if(n <= 0){

printf("\nNhap lai n = ");

}

}while(n <= 0);

for(int i = 0; i < n; i++){

printf("\nNhap a[%d] = ",i);

scanf("%d", &a[i]);

}

// Sap xep dung thuat toan sap xep chon

int tg;

for(int i = 0; i < n - 1; i++){

for(int j = i + 1; j < n; j++){

if(a[i] < a[j]){

// Hoan vi 2 so a[i] va a[j]

tg = a[i];

a[i] = a[j];

a[j] = tg;

}

}

}

printf("\nMang da sap xep la: ");

for(int i = 0; i < n; i++){

printf("%5d", a[i]);

}

}