Mẹo Hướng dẫn Xác định Input và Output của bài toán tìm kiếm tuần tự Chi Tiết
Bạn đang tìm kiếm từ khóa Xác định Input và Output của bài toán tìm kiếm tuần tự được Cập Nhật vào lúc : 2022-04-28 15:10:12 . Với phương châm chia sẻ Thủ Thuật Hướng dẫn trong nội dung bài viết một cách Chi Tiết 2022. Nếu sau khi tìm hiểu thêm tài liệu vẫn ko hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Ad lý giải và hướng dẫn lại nha.
Chào mừng những emđến với bài học kinh nghiệm tay nghề ngày ngày hôm nay Tìm kiếm là việc thường xẩy ra trong cuộcTìm kiếm là gì?sống, ví dụ điển hình cần tìm cuốn sách giáo khoaTin học 10 trên giá sách, cần tìm một học sinhtrong list một lớp học,... 2.Bài tốn tìm kiếmCho dãy số A gồm những số: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51Với k=2 trong dãy trên số hạng thứ mấy có mức giá trị bằng k? Chỉ số i cần tìm là bao nhiêu?Với k=6 trong dãy trên số hạng thứ mấy có mức giá trị bằng k? Chỉ số i cần tìm là bao nhiêu? Thuật tốn tìm kiếm tuần tự 3.Thuật tốn tìm kiếm tuần tựCho dãy A gồm N số nguyên rất khác nhau a1,a2,...,aN và một số trong những nguyên k. Cần biếtcó hay khơng chỉ số i (1≤ i≤ N) mà ai=k. Nếu có hãy cho biết thêm thêm chỉ số đó.Input:Dãy số A gồm N số nguyên rất khác nhau a 1, a2, .., aN và số nguyên k.Các em hãy xác lập Input và Output của bài toánOutput: Chỉ số mà a i=k hoặc thơng báo khơng có số hạng nào của A có mức giá trị bằng k. 3.Thuật tốn tìm kiếm tuần tựÝ tưởng:Tìm kiếm tuần tự được thực thi một cách tự nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trịsố hạng đang xét với khoá cho tới lúc hoặc gặp một số trong những hạng bằng khoá hoặc dãy đã được xét hết vàkhơng có mức giá trị nào bằng khố.Trong trường hợp thứ hai dãy A khơng có số hạng nào bằng khố. 3.Thuật tốn tìm kiếm tuần tựCách liệt kêB1: Nhập N, những số hạng a 1, a2, ..., aN và khoá k;B2: i 1;B3: Nếu ai=k thì thơng báo chỉ số i, rồi kết thúc;B4: i i+1;B5: Nếu i > N thì thơng báo dãy A khơng có số hạng nào có mức giá trị bằng k, rồi kết thúcB6: Quay lại bước 3. Thuật tốn dừng khi tìm thấy số hạng bằng khố hoặc khi xét hết dãy mà khơng có thành phần nàobằng khoá.Thuật toán sẽ dừng lúc nào? 3.Thuật tốn tìm kiếm tuần tựSơ đồ khối VD: Cho dãy số 7, 8, 3, 5, 6, 2.Sử dụng thuật toán tuần tự kiểm tra xem số 3 có ở trong dãy khơng và nằm ở vị trí vị trí nào? Có 2 dãy sau:Dãy A:5, 7, 9, 3, 1, 10Dãy B:1, 3, 5, 7, 9, 10VàCác em cho biết thêm thêm sự rất khác nhau của 2 dãy trên?Dãy B đã được sắp xếptheo thứ tự tăng dầnDãy B đã được sắp xếp thì cơ nên làm ra làm sao để tìm số 9 nhanh nhất có thể? Thuật tốn tìm kiếm nhị phân 4. Thuật tốn tìm kiếm nhị phânCho dãy A sắp xếp tăng dần gồm N số nguyên rất khác nhau a1,a2,...,aN và một số trong những ngun k. Cần biết cóhay khơng chỉ số i (1≤ i≤ N) mà ai=k. Nếu có hãy cho biết thêm thêm chỉ số đó.Input:Dãy số A sắp xếp tang dần gồm N số nguyên rất khác nhau a 1, a2, .., aN và số nguyên k.Các em hãy xác lập Input và Output của bài toánOutput: Chỉ số mà a i=k hoặc thơng báo khơng có số hạng nào của A có mức giá trị bằng k. 4. Thuật tốn tìm kiếm nhị phânÝ tưởng:Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khốvới số hạng được chọn. Để làm điều này, ta chọn số hạng aGiua ở "giữa dãy" để so sánh với k, trong số đó Giua=(N+1)/2.Khi đó, chỉ xẩy ra một trong ba trường hợp sau:- Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.- Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,...,aGiua–1 (phạm vi tìm kiếm mới bằng khoảng chừng một nửa phạm vi tìm kiếm trước đó). - Nếu aGiua < k thì thực thi tìm kiếm trên dãy aGiua+1, aGiua+2,..., aN. Quá trình trên sẽ tiến hành lặp lại một số trong những lần cho tới lúc hoặc đã tìm thấy khố k trong dãy A hoặc phạm vi tìmkiếm bằng rỗng. 4. Thuật tốn tìm kiếm nhị phân Cách liệt kêBước 1. Nhập N, những số hạng a1, a2,..., aN và khoá k;Bước 2. Dau ¬ 1, Cuoi ¬ N;Bước 3. Giua ¬ (Dau+Cuoi)/2;Bước 4. Nếu aGiua = k thì thơng báo chỉ số Giua, rồi kết thúc;Bước 5. Nếu aGiua > k thì đặt Cuoi = Giua – 1 rồi chuyển đến bước 7;Bước 6. Dau ¬ Giua + 1;Bước 7. Nếu Dau > Cuoi thì thơng báo dãy A khơng có số hạng có mức giá trị bằng k, rồi kết thúc;Bước 8. Quay lại bước 3. 4. Thuật tốn tìm kiếm nhị phânGhi chú: Tuỳ thuộc aGiua > k hoặc aGiua < k mà chỉ số đầu hoặc chỉ số cuối của dãy ởbước tìm kiếm tiếp theo sẽ thay đổi. Để thực thi điều này, trong thuật toán chỉ sử dụngcác biến nguyên tương ứng Dau và Cuoi có mức giá trị khởi tạo Dau = 1 và Cuoi = N. 4. Thuật tốn tìm kiếm nhị phân VD: Cho dãy số 1, 3, 5, 7, 9, 10.Sử dụng thuật tốn tìm kiếm nhị phân kiểm tra xem số 9 có ở trong dãy khơng và nằm ở vị trí vị trínào? Bài về nhàLàm bài 7 sách giáo khoa trang 44 và đọc trước thuật tốn tìm kiếm nhị phân Thank you
Nội dung chính- 1. Khái niệm bài toán
- 2. Khái niệm thuật toán
- 3. Một số ví dụ về thuật toán
Các vướng mắc tương tự
BÀI 4. BÀI TOÁN VÀ THUẬT TOÁN
1. Khái niệm bài toán
- Bài toán là một việc nào đó ta muốn máy tính thực thi. Ví dụ: Giải phương trình bậc 2, quản trị và vận hành nhân viên cấp dưới…
- Các bài toán được cấu trúc bởi 2 thành phần cơ bản:
- Input: những thông tin đã có.
- Output: Các thông tin cần tìm từ Output.
2. Khái niệm thuật toán
- Thuật toán để giải một bài toán là một dãy hữu hạn những thao tác được sắp xếp theo 1 trình tự xác lập sao cho sau khi thực thi dãy thao tác ấy, từ Input của bài toán, ta nhận ra Output cần tìm.
- Ví dụ: Tìm giá trị lớn số 1 của một dãy số nguyên.
=> Ta có 3 bước thực thi như sau:
* Xác định BT
- Input: Số nguyên dương N và dãy N số nguyên a1, a2, …, aN.
- Output: Giá trị lớn số 1 Max của dãy số.
* Ý tưởng
- Khởi tạo giá trị Max = a1.
- Lần lượt với i từ 2 đến N so sánh ai với Max, nếu ai>Max thì Max= ai.
* Thuật toán:
Cách liệt kê:
- B1: Nhập N và dãy a1,...,aN;
- B2: Max (leftarrow) a1, i (leftarrow) 2;
- B3: nếu i>N thì đưa giá trị Max rồi kết thúc;
- B4: Nếu ai>Max thì Max (leftarrow) ai;
- B5: i (leftarrow) i+1 rồi quay trở lại bước 3;
Cách lập sơ đồ khối:
- Thuật toán còn được diễn tả bằng sơ đồ khối.
- Quy định:
- Hình ô van: những thao tác nhập, xuất tài liệu.
- Hình thoi: Thao tác so sánh.
- Hình chữ nhật: Các phép toán.
- Mũi tên: trình tự thực thi những thao tác.
Ví dụ: Mô phỏng việc thực thi thuật toán với N=8 và dãy số: 5, 1, 4, 7, 6, 3, 15, 11
Ds
5
1
4
7
6
3
15
11
i
2
3
4
5
6
7
8
9
Max
5
5
5
7
7
7
15
15
=> Các tính chất của thuật toán:
- Tính dừng: Thuật toán phải kết thúc sau một số trong những hữu hạn lần thực thi những thao tác.
- Tính xác lập: Sau một số trong những lần thực thi thao tác, hoặc là kết thúc hoặc xác lập để thực thi bước tiếp theo.
- Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.
3. Một số ví dụ về thuật toán
Ví dụ 1: Kiểm tra tính nguyên tố của một số trong những nguyên dương.
- Xác định bài toán:
- Input: Số nguyên dương N.
- Output: “N là số nguyên tố” hoặc “N không là số nguyên tố”.
- Ý tưởng: Ta nhớ lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng 2 ước số rất khác nhau là một trong và chính nó. Do đó ta có:
- Nếu N = 1 thì N không là nguyên tố.
- Nếu 1 < N < 4 thì N là số nguyên tố.
- Nếu N (ge) 4 và không còn ước số trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.
- Thuật toán:
- B1: Nhập số nguyên dương N.
- B2: Nếu N = 1 thì thông báo N không là số nguyên tố rồi kết thúc.
- B3: Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc.
- B4: i (leftarrow) 2
- B5: Nếu N>[(sqrtN)](*) thì thông báo N là số nguyên tố rồi kết thúc.
- B6: Nếu N chia hết cho i thì thông báo N là số không nguyên tố rồi kết thúc.
- B7: i (leftarrow) i + 1 rồi quay trở lại bước 5.
Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2, a3, …,aN. Cần sắp xếp những số hạng để dãy A trở thành dãy không giảm (tức là số hạng trước không to nhiều hơn số hạng sau)
- Xác định bài toán:
- Input: Dãy A gồm N số nguyên
- Output: Dãy A được sắp xếp thành dãy không giảm.
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
- Ý tưởng: Với 2 số liền kề, nếu số trước to nhiều hơn số sau ta đổi chổ lẫn nhau. Việc đó lặp lai, lúc không hề sự đổi chổ nào nữa.
- Thuật toán
Cách liệt kê:
- B1: Nhập vào n và dãy số nguyên a1, . . . ,aN;
- B2: M (leftarrow) N;
- B3: Nếu M<2 thì in dãy đã sắp xếp rồi kết thúc;
- B4. M (leftarrow) M – 1; i (leftarrow) 0;
- B5: i (leftarrow) i + 1;
- B6: Nếu i > M thì quay trở lại bước 3;
- B7. Nếu ai > ai+1 thì tráo đổi lẫn nhau;
- B8: Quay lại bước 5;
Ví dụ 3: Bài toán tìm kiếm
Cho dãy A gồm N số nguyên rất khác nhau: a1…aN. và một số trong những nguyên k. Cần biết có hay là không riêng gì có số i mà ai=k. Nếu có hãy cho biết thêm thêm chỉ số đó.
Thuật toán tìm kiếm tuần tự:
- Xác định bài toán
- Input: dãy A gồm N số nguyên rất khác nhau: a1…aN và số nguyên k.
- Output: chỉ số i mà ai=k hoặc thông báo không còn số hạng nào của dãy A có mức giá trị là k.
- Ý tưởng: lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho tới lúc hoặc gặp một số trong những hạng bằng khoá hoặc dãy đã được xét hết và không còn mức giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không còn số hạng nào bằng khoá...
- Thuật toán
Liệt kê:
- B1: Nhập vào N, những số hạng a1, . . . ,aN và khóa k;
- B2: i(leftarrow)1;
- B3: Nếu ai=k thì thông báo chỉ số i rồi kết thúc;
- B4. i (leftarrow)i+1;
- B5: Nếu i>N thì thông báo dãy A không còn số hạng nào có mức giá trị bằng k rồi kết thúc;
- B6: Quay lại bước 3;
Dãy A có N = 7 khóa k = 10
Tìm chỉ số i để ai = k.
i
1
2
3
4
5
6
7
ai
7
12
4
6
11
10
8
Ghi chú: k = 10 → i = 6
Trong thuật toán trên, i là biến chỉ số và nhận giá trị nguyên lần lượt từ là 1 đến N + 1
Reply
3
0
Chia sẻ
Share Link Down Xác định Input và Output của bài toán tìm kiếm tuần tự miễn phí
Bạn vừa đọc nội dung bài viết Với Một số hướng dẫn một cách rõ ràng hơn về Video Xác định Input và Output của bài toán tìm kiếm tuần tự tiên tiến và phát triển nhất và Chia Sẻ Link Down Xác định Input và Output của bài toán tìm kiếm tuần tự miễn phí.