Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị
Tải giáo án điện tử Chuyên đề học tập Tin học 11 - Khoa học máy tính (kết nối tri thức) Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị. Bộ giáo án chuyên đề được thiết kế sinh động, đẹp mắt. Thao tác tải về đơn giản, dễ dàng sử dụng và chỉnh sửa. Thầy, cô kéo xuống để xem chi tiết.
Xem: => Giáo án tin học 11 theo định hướng khoa học máy tính kết nối tri thức
Xem toàn bộ: Giáo án điện tử chuyên đề Tin học 11 - Khoa học máy tính Kết nối tri thức
CHÀO MỪNG CÁC EM ĐẾN VỚI
BÀI HỌC NGÀY HÔM NAY!
KHỞI ĐỘNG
Với hai bài toán trên em sẽ thực hiện như thế nào?
BÀI 7: THIẾT KẾ
THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ
NỘI DUNG BÀI HỌC
1
Bài toán lũy thừa
2
Bài toán tìm kiếm nhị phân mở rộng
PHẦN 1.
BÀI TOÁN LŨY THỪA
Hoạt động 1
Giải bài toán tính lũy thừa bằng chia để trị
Hãy thiết lập thuật toán và chương trình tính lũy thừa an với a là số bất kì khác 0, n là số nguyên không âm.
Vì an = a x an-1 nên có thể thiết lập ngay chương trình tính hàm lũy thừa đơn giản như sau:
Chương trình 1. Tính lũy thừa theo cách tự nhiên
1 def exp(a,n): 2 p = 1 3 for i in range(n): 4 P = p*a 5 return p |
Chương trình 2. Tính lũy thừa theo cách nhị phân nhanh (chia để trị).
1 def exp(a,n): 2 if n == 0: 3 return 1 4 else: 5 b = exp(a,n//2) 6 if n%2 == 0: 7 return b*b 8 else: 9 return a*b*b |
KẾT LUẬN
Hàm exp(a,n) trên được thiết lập theo kĩ thuật chia để trị có độ phức tạp thời gian O(logn).
Đọc thông tin và trả lời các câu hỏi sau đây:
- Câu 1: Mô tả các bước tính bằng tay phép tính lũy thừa 211 theo hai chương trình trên. Các nào nhanh hơn?
- Câu 2: Phép tính a21 sẽ cần dùng bao nhiêu phép nhân?
HƯỚNG DẪN THỰC HIỆN
1
- Tính tay 211
Tính theo phương pháp cũ. Cần thực hiện 10 lần phép nhân với 2.
- Tính theo phương pháp chia để trị mới
Bước 1. Tính 2 x 2 = 22
Bước 2. Tính 4 x 4 = 24
Bước 3. Tính 24 x 2 = 25
Bước 4. Tính 25 x 25 = 210
Bước 5. Tính 210 x 2 = 211
Vậy theo cách tính mới chỉ cần 5 phép nhân
2
- Tính a21
a21 = a x a10 x a10
Theo bài trên, tính a10 cần 4 phép nhân
Cần 4 + 2 = 6 phép nhân cho a21.
PHẦN 2. BÀI TOÁN TÌM KIẾM NHỊ PHÂN MỞ RỘNG
Hoạt động 2
Giải bài toán tìm kiếm nhị phân mở rộng bằng chia để trị
Cho trước dãy các số đã được sắp xếp tăng dần. Với giá K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất.
Để tìm được ra phần tử của dãy gần K nhất chúng ta cần thêm các tính toán phụ tại dòng 10.
Chương trình 1. Sử dụng tìm kiếm tuần tự
1 def valueClosest(A,K): 2 n = len(A) 3 if K <= A[0]: 4 return A[0] 5 elif K >= A[n – 1]: 6 return A[n – 1] 7 else: 8 value = A[0] 9 for i in range(n): 10 if abs(A[i] – K) < abs(value – K): 11 value = A[i] 12 return value |
8 value = A[0] 9 for i in range(n): 10 if abs(A[i] – K) < abs(value – K): 11 value = A[i] 12 return value |
Chương trình 2. Sử dụng tìm kiếm nhị phân
1 def valueClosest(A,left,right,K): 2 if left > right: 3 return 4 elif left == right: 5 return A[left] 6 elif left == right - 1 7 if abs(A[left] – K) < abs(A[right] – K): 8 return A[left] 9 else: 10 return A[left] 11 else: 12 mid = (left + right)//2 |
8 return A[left] 9 else: 10 return A[left] 11 else: 12 mid = (left + right)//2 13 If A[mid] == K: 14 Return A[mid] 15 elif K < A[mid]: 16 Return valueClosest(A,left,mid,K) 17 else: 18 Return valueClosest(A,mid,right,K) |
KẾT LUẬN
Thuật toán tìm kiếm nhị phân mở rộng có độ phức tạp thuật toán O(logn).
Đọc thông tin và trả lời các câu hỏi sau đây:
- Câu 1: Hãy giải thích kĩ hơn chương trình 2 ở trên tại các dòng 4 và 6.
- Câu 2: Nêu những điểm khác biệt của chương trình trên với chương trình tìm kiếm nhị phân đã biết.
HƯỚNG DẪN TRẢ LỜI
1
- Dòng 4 mô tả trường hợp A có một phần tử thì đáp số luôn là phần tử duy nhất này.
- Dòng 6 mô tả trường hợp A có hai phần tử, đáp án sẽ là phần tử nào gần K hơn về giá trị.
- Cách xử lí các trường hợp cơ sở khi A có 1 hoặc 2 phần tử.
- Sau mỗi bước lặp (hoặc sau mỗi lần gọi đệ quy), phạm vi tìm kiếm sẽ tìm tiếp ở một trong hai khoảng [mid, right] hay [left, mid], điều này khác biệt với tìm kiếm nhị phân là sau mỗi vòng lặp miền tìm kiếm sẽ là [left, mid – 1] hoặc [mid + 1, right].
2
Chương trình trên khác thuật toán tìm kiếm nhị phân như sau:
LUYỆN TẬP
--------------- Còn tiếp ---------------
Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II
Hệ thống có đầy đủ các tài liệu:
- Giáo án word (350k)
- Giáo án Powerpoint (400k)
- Trắc nghiệm theo cấu trúc mới (200k)
- Đề thi cấu trúc mới: ma trận, đáp án, thang điểm..(200k)
- Phiếu trắc nghiệm câu trả lời ngắn (200k)
- Trắc nghiệm đúng sai (250k)
- Lý thuyết bài học và kiến thức trọng tâm (200k)
- File word giải bài tập sgk (150k)
- Phiếu bài tập để học sinh luyện kiến thức (200k)
Nâng cấp lên VIP đê tải tất cả ở tài liệu trên
- Phí nâng cấp VIP: 800k
=> Chỉ gửi 450k. Tải về dùng thực tế. Nếu hài lòng, 1 ngày sau mới gửi phí còn lại
Cách nâng cấp:
- Bước 1: Chuyển phí vào STK: 1214136868686 - cty Fidutech - MB(QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận tài liệu
Xem toàn bộ: Giáo án điện tử chuyên đề Tin học 11 - Khoa học máy tính Kết nối tri thức
ĐẦY ĐỦ GIÁO ÁN CÁC BỘ SÁCH KHÁC
GIÁO ÁN WORD LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN POWERPOINT LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN CHUYÊN ĐỀ LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN DẠY THÊM 11 KẾT NỐI TRI THỨC
CÁCH ĐẶT MUA:
Liên hệ Zalo: Fidutech - nhấn vào đây