Đáp án và lời giải
Giải chuyên đề Tin 11 Cánh diều Bài 2. Kỹ thuật đệ quy trong chia để trị có đáp án
Câu 1
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Bước 1. So sánh x với phần tử năm ở vị trí giữa dãy số. gọi là phân tử giữa.
Bước 2. Nếu x bằng với giá trị phân tử giữa. đưa ra vị trí phần tử tìm được.
Bước 3. Nếu x lớn hơn giá trị phân tử giữa. giá trị x chỉ có thể nằm ở nửa bên phải phân tử giữa của dãy số (nửa có giá trị lớn hơn). Quay lại Bước 1, tiếp tục áp dụng thuật toán đối với nửa dãy số bên phải này.
Bước 4. Nếu x nhỏ hơn giá trị phân từ giữa, giá trị x chỉ có thể năm ở nửa bên trái phân tử giữa của dãy số (nứa có giá trị nhỏ hơn). Quay lại Bước 1 tiếp tục áp dụng thuật toán đối với nửa dãy số bên trái này.
Câu 2
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Câu 3
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Có 2 trường hợp:
1) an = an2 X an2, nếu n chẵn
2) an = a X an−1, nếu n lẻ và n > 1
=> Lưu lại kết quả bài toán con trong mỗi lần gọi đệ quy để tránh gọi quy lặp lại cho các bài toán con đã tính
Câu 4
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
using namespace std;
int tim(int *a,int left,int right,int x)
{
int m;
if(left>right) return 0;
m=(left+right)/2;
if(a[m]==x) return m;
if(xa[m]) return tim(a,left,m-1,x);
return tim(a,m+1,right,x);
}
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int x;
cout<<"tim so: ";cin>>x;
if(int z=tim(a,0,9,x)) cout<<"tim thay tai vi tri: "<z<<"\n";
else cout<<"khong tim thay\n";
}
Câu 5
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Câu 6
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý