Module: Tìm kiếm nhị phân cho một chức năng đơn điệu


Problem

1/5

Tìm kiếm nhị phân cho một chức năng đơn điệu

Theory Click to read/hide

Tìm kiếm nhị phân không chỉ được sử dụng để tìm các phần tử trong mảng mà còn để tìm nghiệm của các phương trình và giá trị của các hàm đơn điệu (tăng hoặc giảm).

Hãy cho chúng ta một hàm đơn điệu f và một số giá trị C của hàm này. Tìm giá trị của đối số x của hàm này sao cho \(f(x)=C\).
 
Ví dụ về hàm đơn điệu tăng:


Chúng tôi chọn các ranh giới như vậy trong đó giá trị của hàm chính xác lớn hơn và chính xác nhỏ hơn giá trị đã cho. Hãy chọn giá trị ở giữa phân khúc này. Nếu nó nhỏ hơn giá trị đã cho, thì chúng ta dịch chuyển đường viền bên trái vào giữa đoạn. Nếu không, chúng tôi sẽ dịch chuyển đường viền bên phải. Tiếp theo, chúng tôi lặp lại quá trình thu hẹp ranh giới. Nhưng có một vấn đề là khi nào thì ngừng tìm kiếm. Đọc thêm tại đây.
 
Ví dụ, xét bài toán tìm căn bậc hai của số x. Căn bậc hai của x (ký hiệu là \(\sqrt x\)) là một số y sao cho < span class="math-tex">\(y^2 = x\).
Hãy lập công thức bài toán như sau: với một số thực x (\(x >= 1\)) cho trước căn bậc hai với độ chính xác không nhỏ hơn 5 ký tự sau dấu chấm.
 


Chọn đường viền của đoạn để tìm kiếm

Vì chúng ta không thể kiểm tra toàn bộ vô số số nên chúng ta cần xác định ranh giới của việc tìm kiếm gốc. Đầu tiên, hãy tìm đường viền bên trái, chọn một điểm âm tùy ý (ví dụ: -1). Chúng tôi sẽ nhân đôi nó cho đến khi giá trị trong đó lớn hơn giá trị đã cho. Để tìm đúng biên ta chọn một điểm dương tùy ý (ví dụ: 1). Chúng tôi sẽ nhân đôi nó cho đến khi giá trị của hàm tại thời điểm này nhỏ hơn giá trị đã chỉ định.


Hoặc, nếu biết chính xác ranh giới tìm kiếm, chúng ta có thể lấy 1 làm ranh giới bên trái và chính số đó x.
Sau đó, ta chia đôi đoạn hiện tại, lấy bình phương ở giữa, nếu lớn hơn x thì thay mặt trên, ngược lại  dưới cùng.
 
Triển khai cuối cùng:

ở đâu,
eps - độ chính xác mà giải pháp phải được tìm kiếm,
x - số đã cho có căn bậc hai mà chúng ta đang tìm kiếm,
m - số mà kết quả sẽ được lưu trữ sau khi thực thi thuật toán.
 

Problem

Cho một số tự nhiên x. Tính căn bậc ba của một số.
 
Đầu vào
Số x – tự nhiên, không vượt quá \(10^6\).
 
Đầu ra
Chương trình sẽ hiển thị một số duy nhất: câu trả lời cho vấn đề với độ chính xác ít nhất là 6 chữ số thập phân.

 

Ví dụ
<đầu>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Đầu vào Đầu ra
1 2 1.259921
Write the program below 
#include <iostream>
using namespace std;

double Search_Binary(int x)
{           
	
}

int main()
{
	
	int x;
	cin >> x;
	
	double res = Search_Binary(x);
	printf("%.8lf", res);


}

     

Program check result

To check the solution of the problem, you need to register or log in!