Giáo án ppt chuyên đề KHMT 11 kết nối: Bài 7 Thiết kế thuật toán theo kĩ thuật chia để trị

Giáo án ppt chuyên đề Tin học khoa học máy tính 11 kết nối tri thức: Bài 7 Thiết kế thuật toán theo kĩ thuật chia để trị. Bài giảng thiết kế hiện đại, sáng tạo giúp tiết học thêm phần thú vị, giúp giáo viên tiết kiệm thời gian nhưng vẫn có thể ứng dụng công nghệ vào công tác giảng dạy.

Bài khác

Nội dung chi tiết

... Còn nữa ...

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

Đầy đủ Giáo án ppt chuyên đề tin học khoa học máy tính 11 kết nối tri thức

Tài liệu cùng môn học

Tài liệu khác

Xem thêm nội dung

CHUYÊN ĐỀ 1. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY

CHUYÊN ĐỀ 2. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ

CHUYÊN ĐỀ 3. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT