- Các thuật toán và chương trình mà em đã biết đều là các thuật toán cơ bản trong lập trình và giải quyết các vấn đề thông thường. Các điểm chung của chúng bao gồm: Tính đơn giản, độ phức tạp thấp.

- Theo em, để thiết kế một thuật toán đúng giải một bái toàn cho trước cần trải qua các bước:

1. Xác định bài toán

2. Tìm cấu trúc dữ liệu biểu diễn thuật toán.

3. Tìm Thuật Toán.

4. Lập Trình (Programming)

5. Kiểm thử chương trình (Testing program)

6. Tối ưu chương trình (optimization program)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll a[]={10,2,5,12,20,6,8,15,18}; //mảng đã cho
    ll n=sizeof(a)/sizeof(a[0]); //độ dài mảng
    sort(a,a+n); //sắp xếp mảng
    //Thuật toán tìm kiếm nhị phân
    ll l=0, r=n-1;
    while(l<=r) {
        ll mid=(l+r)/2; //Tìm phần tử giữa left và right
        if(a[mid]<15) l=mid+1; //Vì từ đoạn [0,mid] thì phần tử nhỏ hơn 15 nên ta duyệt từ khoảng (mid,r]
        else r=mid-1; //vì thấy nên rút r để thu hẹp phạm vi
    }
    cout << l+1; //in ra kq (vì bắt đầu từ 0 đến n-1 nên phải tăng thêm để ra vị trí đúng)
}

(Bạn có thể dựa vào code mình để rút ra các bước)

Chúc bạn học tốt!

a)

import time

def linear_search(arr, x):

 """

 Tìm kiếm tuyến tính trong dãy arr để tìm giá trị x.

 Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.

 """

 n = len(arr)

 for i in range(n):

  if arr[i] == x:

   return i

 return -1

# Dãy số A

A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]

# Phần tử cần tìm kiếm

C = 9

# Bắt đầu đo thời gian

start_time = time.perf_counter()

# Tìm kiếm phần tử C trong dãy A

result = linear_search(A, C)

# Kết thúc đo thời gian

end_time = time.perf_counter()

if result != -1:

 print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")

else:

 print(f"Phần tử {C} không có trong dãy A.")

print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")

b)

import time

def binary_search(arr, x):

 """

 Tìm kiếm nhị phân trong dãy arr để tìm giá trị x.

 Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.

 """

 left, right = 0, len(arr) - 1

 while left <= right:

  mid = (left + right) // 2

  if arr[mid] == x:

   return mid

  elif arr[mid] < x:

   left = mid + 1

  else:

   right = mid - 1

 return -1

# Dãy số A đã được sắp xếp

A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]

# Phần tử cần tìm kiếm

C = 9

# Bắt đầu đo thời gian

start_time = time.perf_counter()

# Tìm kiếm phần tử C trong dãy A bằng thuật toán tìm kiếm nhị phân

result = binary_search(A, C)

# Kết thúc đo thời gian

end_time = time.perf_counter()

if result != -1:

 print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")

else:

 print(f"Phần tử {C} không có trong dãy A.")

print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")

-Thời gian thực hiện ở câu a là 8.99999,thời gian thực hiện ở câu b là 6,49999 giây.

Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.

Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.

a. Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:

Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:

- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5

- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.

b) Thuật toán tìm kiếm nhị phân

- Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

Thuật toán tuần tự

- Mô tả thuật toán phải cụ thể, rõ ràng, đầy đủ, đầu vào là gì, đầu ra là gì và chỉ rõ sự kết thúc thuật toán.

- Cần mô tả thuật toán cho tốt thì người máy hay máy tính mới hiểu đúng và thực hiện được.

- Nếu không, kết quả thực hiện thuật toán có thể không như mong đợi.

THAM KHẢO!

1.Thuật toán sắp xếp chèn (Insertion Sort):

def insertion_sort(arr):

  for i in range(1, len(arr)):

   key = arr[i]

   j = i - 1

   while j >= 0 and arr[j] > key:

    arr[j + 1] = arr[j]

    j -= 1

   arr[j + 1] = key

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = insertion_sort(A)

print("Dãy A sau khi sắp xếp chèn:", sorted_A)

2. Thuật toán sắp xếp chọn (Selection Sort):

def selection_sort(arr):

  for i in range(len(arr)):

   min_idx = i

   for j in range(i + 1, len(arr)):

    if arr[j] < arr[min_idx]:

     min_idx = j

   arr[i], arr[min_idx] = arr[min_idx], arr[i]

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = selection_sort(A)

print("Dãy A sau khi sắp xếp chọn:", sorted_A)

3.Thuật toán sắp xếp nổi bọt (Bubble Sort):

def bubble_sort(arr):

  n = len(arr)

  for i in range(n - 1):

   for j in range(n - 1 - i):

    if arr[j] > arr[j + 1]:

     arr[j], arr[j + 1] = arr[j + 1], arr[j]

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = bubble_sort(A)

print("Dãy A sau khi sắp xếp nổi bọt:", sorted_A)