Câu hỏi:

11/05/2023 443

Trong bài học này em sẽ thiết kế lời giải cho hai bài toán sau:

1. Bài toán tính luỹ thừa exp(a, n) = $a^{n}$ với a là số bất kì (khác 0), n là số nguyên không âm, ở đây $a^{n}$ được hiểu là tích của n lần giá trị a an = a × a × ... × a (n lần).

2. Ban giám hiệu nhà trường cần tìm một bạn lớp em có chiều cao đúng bằng 1,7 m hoặc gần với chiều cao đó nhất để tham gia tập đội hình thể thao.

Với hai bài toán trên em sẽ thực hiện như thế nào?

Xem lời giải

Câu hỏi trong đề: Giải SGK Chuyên đề Tin học 11 Bài 7. Thiết kế thuật toán theo kĩ thuật chia để trị !!

Giao bài

Quảng cáo

Trả lời:

Giải bởi Vietjack

1. Để tính luỹ thừa của một số a với một số nguyên không âm n, em có thể sử dụng thuật toán đệ quy như sau:

Trong bài học này em sẽ thiết kế lời giải cho hai bài toán sau: (ảnh 1)

2. Để tìm một bạn lớp có chiều cao gần với 1,7 m nhất, em có thể sử dụng một thuật toán tìm kiếm đơn giản như thuật toán tìm kiếm tuần tự hoặc tìm kiếm nhị phân. Tuy nhiên, để áp dụng thuật toán tìm kiếm nhị phân, em cần phải sắp xếp danh sách chiều cao của các bạn lớp trước.

Ví dụ, nếu danh sách chiều cao của các bạn lớp được lưu trữ trong một mảng a, em có thể sử dụng thuật toán tìm kiếm tuần tự như sau:

Trong bài học này em sẽ thiết kế lời giải cho hai bài toán sau: (ảnh 2)

Đang tải chế độ Học...

Hot: 1000+ đề thi cuối kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay

Dành cho bạn Hot

Lớp 11 Toán

112 người thi tuần này

Trắc nghiệm Đường thẳng và mặt phẳng song song lớp 11 (có đúng sai, trả lời ngắn)

20 câu 1.2 K lượt thi Thi ngay →

Lớp 11 Vật lý

205 người thi tuần này

Trắc nghiệm Mô tả sóng lớp 11 (có đáp án)

10 câu 6.3 K lượt thi Thi ngay →

Lớp 11 Hóa học

141 người thi tuần này

Trắc nghiệm Nitrogen lớp 11 (có đáp án - phần 1)

15 câu 4.2 K lượt thi Thi ngay →

Lớp 11 Tiếng Anh

143 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 11 Global Success có đáp án

50 câu 1.2 K lượt thi Thi ngay →

Lớp 11 Sinh học

161 người thi tuần này

15 câu Trắc nghiệm Sinh học 11 Kết nối tri thức Bài 8 có đáp án

15 câu 3.2 K lượt thi Thi ngay →

Lớp 11 Lịch sử

1,314 người thi tuần này

25 câu Trắc nghiệm Lịch Sử 11 Kết nối tri thức Bài 1 có đáp án

25 câu 20.4 K lượt thi Thi ngay →

Lớp 11 Tin học

745 người thi tuần này

15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 1 có đáp án

15 câu 9.8 K lượt thi Thi ngay →

Lớp 11 Giáo dục Kinh tế và Pháp luật

158 người thi tuần này

16 câu Trắc nghiệm Kinh tế pháp luật 11 Kết nối tri thức Bài 2 có đáp án

16 câu 3.9 K lượt thi Thi ngay →

CÂU HỎI HOT CÙNG CHỦ ĐỀ

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 2 và 4.

Xem đáp án

Lời giải

Giải thích kĩ hơn chương trình 2 trên tại các dòng 2 và 4:

- Dòng 2: nếu left == right tức là mảng có 1 phần tử

- Dòng 4: Nếu left == right - 1 tức là mảng có 2 phần tử

Câu 2

Mô tả các bước tính bằng tay phép tính luỹ thừa theo hai chương trình trên. Cách nào nhanh hơn?

Xem đáp án

Lời giải

Vì $a^{n} = a \times a^{n - 1}$

1. Tính bình thường:

- Để tính $2^{11}$ bằng phương pháp bình thường, ta sẽ lặp lại việc nhân 2 với chính nó 21 lần (tức là 2* 2*...*2, lặp lại 21 lần).

Tuy nhiên, việc tính toán này sẽ rất tốn thời gian và không hiệu quả khi giá trị của số mũ lớn hơn.

2. Chia để trị:

Bước 1: Chia bài toán thành các bài toán con

Chia 11 cho 2, ta được kết quả là 5 và số dư là 1: 11 = 2 * 5 + 1

Bước 2: Giải quyết các bài toán con

Ta cần tính 2^5 để giải quyết bài toán con này. Tiếp tục áp dụng phương pháp chia để trị trên bài toán con này:

Chia 5 cho 2, ta được kết quả là 2 và số dư là 1: 5 = 2 * 2 + 1

Tiếp tục giải bài toán con tiếp theo:

Chia 2 cho 2, ta được kết quả là 1 và số dư là 0: 2 = 2 * 1 + 0

Bây giờ ta đã giải quyết được tất cả các bài toán con.

Bước 3: Tính toán kết quả

Từ bài toán con cuối cùng, ta có được: 2^1 = 2

Từ bài toán con thứ hai, ta có được: 2^2 = (2^1)^2 = 2^2 = 4

Từ bài toán con đầu tiên, ta có được: 2^5 = (2^2)^2 * 2 = 4^2 * 2 = 16 * 2 = 32

Vậy: 2^11 = 2^5 * 2^5 * 2 = 32 * 32 * 2 = 1024

Do đó, 2^11 = 1024.

Câu 3