Module: 二进制搜索单调函数


Problem

1/5

二进制搜索单调函数

Theory Click to read/hide

二分查找不仅可以用于查找数组中的元素，还可以用于查找方程的根和单调（递增或递减）函数的值。

给我们一个单调函数 f 和这个函数的一些值 C。找到此函数的 x 参数的值，例如 \(f(x)=C\)。
 
递增单调函数的例子：


我们选择函数值恰好大于和恰好小于给定值的边界。让我们选择该段中间的值。如果它小于给定的，那么我们将左边界移动到线段的中间。否则，我们将移动右边界。接下来，我们重复缩小边界的过程。但是有个问题就是什么时候停止搜索。阅读更多 此处。
 
例如，考虑求数字x 的平方根的问题。 x 的平方根（由 \(\sqrt x\) 表示）是一个数字 y 使得\(y^2 = x\).
让我们将问题表述如下：对于给定的实数 x (\(x >= 1\)) 找到平方根，精度不少于点后 5 个字符。
 


选择段的边界进行搜索

由于我们无法检查整个无穷大的数字，因此我们需要定义搜索根的边界。首先，让我们找到左边界，选择任意负点（例如：-1）。我们将它加倍，直到它里面的值大于给定的值。为了找到正确的边界，我们选择任意一个正点（例如：1）。我们将它加倍，直到此时函数的值小于指定值。


或者，如果我们确切地知道搜索的边界，我们可以将 1 作为左边界，并将数字本身设为 x。
之后，我们将当前段一分为二，中间平方，如果大于x，则替换上面，否则 底部。
 
最终实施：

在哪里，
eps - 必须寻求解决方案的准确性，
x - 给定的数字，我们正在寻找其平方根，
m - 算法执行后存储结果的数字。
 

Problem

给定一个自然数x。计算一个数的立方根。
 
输入
数字 x –自然，不超过\(10^6\).
 
输出
程序应该显示一个数字：问题的答案至少精确到小数点后 6 位。

 

例子
<头> <日># <正文>

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++
输入 输出
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!