Module: Monoton bir fonksiyon için ikili arama


Problem

1/5

Monoton bir fonksiyon için ikili arama

Theory Click to read/hide

Binary arama sadece bir dizideki elemanları bulmak için değil, denklemlerin köklerini ve monoton (artan veya azalan) fonksiyonların değerlerini bulmak için de kullanılabilir.

Bize monoton bir f işlevi ve bu işleve ait bir C değeri verilsin. Bu işlevin x bağımsız değişkeninin değerini bulun, öyle ki \(f(x)=C\).
 
Artan monoton fonksiyon örneği:


Fonksiyonun değerinin verilen değerden tam olarak büyük ve tam olarak küçük olduğu sınırları seçiyoruz. Bu segmentin ortasındaki değeri seçelim. Verilenden küçükse, sol kenarlığı segmentin ortasına kaydırırız. Aksi takdirde, sağ sınırı kaydıracağız. Ardından, sınırları daraltma işlemini tekrarlıyoruz. Ancak bir sorun var ki, aramayı ne zaman durduracağız. Daha fazlasını okuyun buraya.
 
Örneğin, x sayısının karekökünü bulma problemini ele alalım. x'in karekökü (\(\sqrt x\) ile gösterilir) bir y sayısıdır, öyle ki < span class="math-tex">\(y^2 = x\).
Problemi şu şekilde formüle edelim: verilen bir x (\(x >= 1\)) gerçek sayısı için noktadan sonra en az 5 karakter hassasiyetle karekök.
 


Arama için segmentin sınırını seçme

Sayıların sonsuzluğunun tamamını kontrol edemediğimiz için, kök aramanın sınırlarını tanımlamamız gerekir. İlk olarak, sol sınırı bulalım, keyfi bir negatif nokta seçelim (örneğin: -1). İçindeki değer verilen değerden büyük olana kadar ikiye katlayacağız. Doğru sınırı bulmak için keyfi bir pozitif nokta seçiyoruz (örneğin: 1). Fonksiyonun bu noktadaki değeri belirtilen değerden küçük olana kadar ikiye katlayacağız.


Veya aramanın sınırlarını tam olarak biliyorsak, sol sınır olarak 1'i ve sayının kendisini x olarak alabiliriz.
Bundan sonra, mevcut parçayı ikiye böleriz, ortanın karesini alırız ve x'ten büyükse üst yüzü değiştiririz, aksi takdirde  alt.
 
Son uygulama:

nerede,
eps - aranan çözümün doğruluğu,
x - karekökünü aradığımız verilen sayı,
m - algoritma çalıştırıldıktan sonra sonucun depolanacağı sayı.
 

Problem

Bir doğal sayı olarak verilen x. Bir sayının küp kökünü hesaplayın.
 
Giriş
Sayı x – doğal, \(10^6\) değerini aşmamalıdır.
 
Çıktı
Program tek bir sayı göstermelidir: sorunun cevabı en az 6 ondalık basamak doğruluğu ile.

 

Örnekler

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++
# Girdi Çıktı
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!