Module: بحث ثنائي عن وظيفة رتيبة


Problem

1/5

بحث ثنائي عن وظيفة رتيبة

Theory Click to read/hide

يمكن استخدام البحث الثنائي ليس فقط للعثور على العناصر في المصفوفة ، ولكن أيضًا للعثور على جذور المعادلات وقيم الدوال الرتيبة (المتزايدة أو المتناقصة).

دعونا نحصل على وظيفة رتيبة f وبعض القيمة C لهذه الوظيفة. ابحث عن قيمة وسيطة x لهذه الدالة ، مثل \ (f (x) = C \) .
نبسب ؛
مثال على دالة رتيبة متزايدة:

نختار مثل هذه الحدود حيث تكون قيمة الوظيفة أكبر تمامًا وأقل تمامًا من القيمة المحددة. دعنا نختار القيمة في منتصف هذا المقطع. إذا كان أقل من الحد المعطى ، فإننا نحول الحد الأيسر إلى منتصف المقطع. خلاف ذلك ، سنقوم بتغيير الحد الأيمن. بعد ذلك ، نكرر عملية تضييق الحدود. ولكن هناك مشكلة عندما تتوقف عن البحث. قراءة المزيد & nbsp؛ هنا .
نبسب ؛
على سبيل المثال ، ضع في اعتبارك مشكلة إيجاد الجذر التربيعي للرقم x . الجذر التربيعي لـ x (يُشار إليه بـ \ (\ sqrt x \) ) هو رقم y بحيث \ (y ^ 2 = x \) .
لنقم بصياغة المشكلة على النحو التالي: للحصول على رقم حقيقي معين x ( \ (x & gt؛ = 1 \) ) ابحث عن جذر تربيعي بدقة لا تقل عن 5 أحرف بعد النقطة.
نبسب ؛


تحديد حد المقطع للبحث

نظرًا لأنه لا يمكننا التحقق من اللانهاية الكاملة للأرقام ، فنحن بحاجة إلى تحديد حدود البحث عن الجذر. أولاً ، لنجد الحد الأيسر ، حدد نقطة سلبية عشوائية (على سبيل المثال: -1). سنضاعفها حتى تصبح القيمة فيها أكبر من القيمة المعطاة. للعثور على الحد الصحيح ، نختار نقطة إيجابية عشوائية (على سبيل المثال: 1). سنضاعفها حتى تصبح قيمة الوظيفة في هذه المرحلة أقل من القيمة المحددة.


أو ، إذا عرفنا حدود البحث بالضبط ، فيمكننا أخذ 1 كحد أيسر والرقم نفسه x .
بعد ذلك ، نقسم المقطع الحالي إلى النصف ، ونقوم بتربيع الجزء الأوسط ، وإذا كان أكبر من x ، فقم باستبدال الوجه العلوي ، وإلا & nbsp؛ أسفل.
نبسب ؛
التنفيذ النهائي:

حيث ،
eps - الدقة التي يجب البحث عنها في الحل ،
x - رقم معطى جذره التربيعي ،
m - الرقم الذي سيتم فيه تخزين النتيجة بعد تنفيذ الخوارزمية.
نبسب ؛

Problem

إعطاء رقم طبيعي x . احسب الجذر التكعيبي لعدد.
& nbsp؛
إدخال
الرقم x & ndash؛ طبيعي ، لا يتجاوز \ (10 ​​^ 6 \) .
& nbsp؛
الإخراج
يجب أن يعرض البرنامج رقمًا واحدًا: الإجابة على المشكلة بدقة لا تقل عن 6 منازل عشرية.

نبسب ؛

أمثلة <الجسم>
# إدخال الإخراج
1 2 1.259921