Module: 単調関数の二分探索


Problem

1/5

単調関数の二分探索

Theory Click to read/hide

二分探索は、配列内の要素を見つけるだけでなく、方程式の根や単調 (増加または減少) 関数の値を見つけるためにも使用できます。

単調関数 f とこの関数の値 C を与えてみましょう。 \(f(x)=C\) となる、この関数の x 引数の値を見つけます。
 
単調増加関数の例:


関数の値が指定された値より正確に大きく、正確に小さいような境界を選択します。このセグメントの中央の値を選択しましょう。指定された値より小さい場合は、左の境界線をセグメントの中央に移動します。それ以外の場合は、右側の境界線を移動します。次に、境界を狭めるプロセスを繰り返します。しかし問題は、いつ検索をやめるかということです。続きを読む こちら。
 
たとえば、数値 x の平方根を求める問題を考えてみましょう。 x の平方根 (\(\sqrt x\) で示される) は、次のような数値 y です。 \(y^2 = x\).
次のように問題を定式化してみましょう。与えられた実数 x (\(x >= 1\)) に対して、ドット以降 5 文字以上の精度の平方根。
 


検索するセグメントの境界線を選択する

無限の数値全体をチェックすることはできないため、ルートの検索の境界を定義する必要があります。まず、左側の境界線を見つけて、任意の負の点 (例: -1) を選択します。その値が指定された値より大きくなるまで、それを 2 倍にします。正しい境界線を見つけるために、任意の正の点 (例: 1) を選択します。この時点の関数の値が指定された値より小さくなるまで
倍にしていきます。

または、検索の境界が正確にわかっている場合は、左側の境界として 1 を取得し、数値そのものを x とすることもできます。
その後、現在のセグメントを半分に分割し、中央を正方形にし、それが x より大きい場合は上面を置き換えます。それ以外の場合は、上面を置き換えます。下
に。  
最終実装:

どこ
で？ eps - 解を求める精度。
x - 平方根を求める指定された数値、
m - アルゴリズムの実行後に結果が保存される番号。
 

Problem

与えられた自然数 x。数値の立方根を計算します。
 
入力
数値 x –自然、\(10^6\) を超えない。
 
出力
プログラムは 1 つの数値を表示する必要があります。つまり、少なくとも小数点以下 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!