Câu 1. Sử dụng thuật toán sắp xếp nổi bọt, hãy nêu các bước để sắp xếp các số: 3, 5, 1, 9 theo thứ tự tăng dần? Câu 2. Sử dụng thuật toán tìm kiếm nhị phân, hãy mô tả các bước để tìm được vị trí của...

Cho dãy số sau 10,2,5,12,20,6,8,15,18 A,sắp xếp dãy số sau theo thứ tự tăng dần B,hãy liệt kê các bước tìm kiếm số 15 trong dãy số đã sắp xếp theo thuật toán tìm kiếm nhị phânGiúp em Vs ạ , mai em nộp...

#Tin học lớp 7

0

HM

hà my

13 tháng 12 2023

#Tin học lớp 7

1

TH

Trương Huy Hoàng

13 tháng 12 2023

#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!

Đúng(3)

ML

Minh Lệ

17 tháng 7 2023

Cho trước một đây số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dây các phần từ đã sắp xếp.

1

QT

Quoc Tran Anh Le

Giáo viên

23 tháng 8 2023

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.

Cho Dãy A gồmN=8.Dãy A gồm các số nguyênlà : 9 ,11, 3, 25, 1, 18,20, 2.Hãy sử dụng thuật toán sắp xếp tráo đổi( sắp xếp dãy A thành dãy không tăng)Cách làm: Làm theo thứ tự các bước:1.Xác định bài toán2.Ý tưởng3.Thuật toán( làm 1 trong 2 cách:Liệt kê và sơ đồ khối)4.Ápdụng làm dãy số trên theo các lần duyệt như trong sách giáo...

HP

Hiền Phạm

9 tháng 1 2022

#Tin học lớp 10

1

NL

Nguyễn Lê Phước Thịnh

9 tháng 1 2022

#include <bits/stdc++.h>

using namespace std;

long long a[8],n,i,j;

int main()

{

n=8;

for (i=1; i<=n; i++) cin>>a[i];

for (i=1; i<=n-1; i++)

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

if (a[i]<a[j]) swap(a[i],a[j]);

for (i=1; i<=n; i++) cout<<a[i]<<" ";

return 0;

}

Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt. Tất cả các thiết kế chương trình đó có điểm nào chung?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 như thế nào? Nêu quan điểm của riêng em và trao đổi với các...

ML

Minh Lệ

17 tháng 7 2023

1

TA

Thanh An

23 tháng 8 2023

- 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)

ML

Minh Lệ

17 tháng 7 2023

Mô tả các bước thuật toán sắp xếp nổi bọt của dãy A = [4, 3, 1, 2]

1

QT

Quoc Tran Anh Le

Giáo viên

23 tháng 8 2023

- Bắt đầu từ vị trí đầu tiên của danh sách (bên trái), so sánh các cặp số với nhau, nếu không đúng thứ tự nhỏ-lớn thì đảo vị trí.
- Sau khi chạy tới cuối danh sách, tiếp tục chạy lại từ vị trí đầu danh sách cho đến khi hoàn thành so sánh và đảo vị trí.

Cho dãy các số A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11].a) Viết chương trình mô tả thuật toán tìm kiếm phần tử C = 9 của dãy trên. Tính thời gian chính xác thực hiện công việc tìm kiếm này.b) Giả sử dây A ở trên đã được sắp xếp theo thứ tự tăng dần: A= [0,1,3,5,7,9,10,11,13, 16]. Viết chương trình tìm kiếm nhị phân để tìm kiếm phân tử C = 9, đo thời gian thực hiện thuật toán. So sánh với kết quả 1ìm kiếm ở câu...

ML

Minh Lệ

17 tháng 7 2023

1

NQ

Nguyễn Quốc Đạt

Giáo viên

22 tháng 10 2023

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.