Module: جستجوی دودویی برای یک تابع یکنواخت


Problem

1/5

جستجوی دودویی برای یک تابع یکنواخت

Theory Click to read/hide

جستجوی باینری نه تنها برای یافتن عناصر در یک آرایه، بلکه برای یافتن ریشه معادلات و مقادیر توابع یکنواخت (افزایش یا کاهش) نیز قابل استفاده است.

اجازه دهید یک تابع یکنواخت f و مقداری C از این تابع به ما داده شود. مقدار آرگومان x این تابع را پیدا کنید، به گونه‌ای که \(f(x)=C\).
 
مثالی از یک تابع یکنواخت فزاینده:


ما چنین مرزهایی را انتخاب می کنیم که مقدار تابع دقیقاً بزرگتر و دقیقاً کمتر از مقدار داده شده باشد. بیایید مقدار را در وسط این بخش انتخاب کنیم. اگر کمتر از مقدار داده شده باشد، حاشیه سمت چپ را به وسط قطعه منتقل می کنیم. در غیر این صورت مرز سمت راست را جابه جا می کنیم. در مرحله بعد، روند باریک کردن مرزها را تکرار می کنیم. اما یک مشکل این است که چه زمانی باید جستجو را متوقف کرد. بیشتر بخوانید اینجا.
 
به عنوان مثال، مشکل یافتن جذر عدد x را در نظر بگیرید. جذر x (که با \(\sqrt x\) مشخص می شود) عددی است y به طوری که < span class="math-tex">\(y^2 = x\).
بیایید مسئله را به صورت زیر فرمول بندی کنیم: برای یک عدد واقعی داده شده x (\(x >= 1\)) ریشه مربع با دقت کمتر از 5 کاراکتر بعد از نقطه.
 


انتخاب حاشیه بخش برای جستجو

از آنجایی که نمی توانیم بی نهایت اعداد را بررسی کنیم، باید مرزهای جستجوی ریشه را مشخص کنیم. ابتدا، بیایید حاشیه سمت چپ را پیدا کنیم، یک نقطه منفی دلخواه را انتخاب کنیم (به عنوان مثال: -1). آن را دو برابر می کنیم تا زمانی که مقدار آن از مقدار داده شده بیشتر شود. برای یافتن مرز مناسب، یک نقطه مثبت دلخواه را انتخاب می کنیم (مثلاً: 1). ما آن را دو برابر می کنیم تا مقدار تابع در این نقطه از مقدار مشخص شده کمتر شود.


یا اگر دقیقاً مرزهای جستجو را بدانیم، می توانیم 1 را به عنوان مرز سمت چپ و خود عدد را x در نظر بگیریم.
بعد از آن، قطعه فعلی را به دو نیم تقسیم می کنیم، وسط را مربع می کنیم و اگر بزرگتر از x بود، وجه بالایی را جایگزین می کنیم، در غیر این صورت  پایین.
 
اجرای نهایی:

کجا،
eps - دقتی که باید برای آن راه حل جستجو کرد،
x - عدد داده شده ای که به دنبال جذر آن هستیم،
m - عددی که نتیجه پس از اجرای الگوریتم در آن ذخیره می شود.
 

Problem

با توجه به یک عدد طبیعی x. ریشه مکعب یک عدد را محاسبه کنید.
 
ورودی
شماره x – طبیعی، از \(10^6\) تجاوز نمی کند.
 
خروجی
برنامه باید یک عدد را نمایش دهد: پاسخ به مسئله با دقت حداقل 6 رقم اعشار.

 

نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 2 1.259921

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++
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!