Module: البحث الثلاثي


Problem

1/9

البحث الثلاثي: البداية (C ++)

Theory Click to read/hide

البحث الثلاثي نحتاج إلى بحث ثلاثي للعثور على الحد الأقصى أو الأدنى للدالة أحادية الوسائط في المقطع & nbsp؛ [l، r] . تكون الوظيفة أحادية الوسائط عندما يكون لها طرف طرفي واحد على قطعة.
غالبًا ما يتم استخدام البحث عن القيم القصوى للدالة لمشاكل التحسين. على سبيل المثال ، نحتاج إلى إيجاد أقصى زاوية ممكنة لمثلث قائم الزاوية ، حيث ستكون المنطقة الأكبر. & nbsp؛ للقيام بذلك ، سننتقل عبر الزوايا من 0 إلى 90 ، وفي هذا الجزء نبحث عن منطقة ستزداد أولاً ثم تنخفض ، أي ستكون الوظيفة أحادية الوسائط.
نبسب ؛
كيف يعمل يشبه مبدأ العملية البحث الثنائي ، ولكن قد تكون لدينا حالة عند تقسيم المقطع إلى النصف ، عندما يقع منتصف المقطع بالضبط على الطرف الأقصى ، و & nbsp؛ لن نحصل على نتيجة واضحة.
لذلك ، لتجنب مثل هذه الحالة ، من الضروري تقسيم المقطع ليس إلى جزأين ، ولكن إلى ثلاثة أجزاء ، ونتجاهل الجزء الذي لا يوجد فيه أقصى حد ، وما إلى ذلك ، حتى تتلاقى الحدود على النتيجة.

f مزدوج (hypo مزدوج ، ألفا مزدوج) { نبسب ؛ نبسب ؛ نبسب ؛ alpha = (alpha * M_PI) / 180 ؛ نبسب ؛ نبسب ؛ على & nbsp ؛ إرجاع 0.5 * hypo * hypo * cos (alpha) * sin (alpha) ؛ } انت مين() { نبسب ؛ نبسب ؛ نبسب ؛ مزدوج ل = 0 ؛ نبسب ؛ نبسب ؛ نبسب ؛ مزدوج ص = 90 ؛ نبسب ؛ نبسب ؛ نبسب ؛ EPS مزدوج = 1e-6 ؛ نبسب ؛ نبسب ؛ نبسب ؛ hypo مزدوج = 100 ؛ نبسب ؛ نبسب ؛ & nbsp؛ while (r - l & gt؛ = EPS) { نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ نبسب ؛ مزدوج m1 = l + (r - l) / 3 ؛ نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ نبسب ؛ مزدوج m2 = r - (r - l) / 3 ؛ نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ & nbsp؛ if (f (hypo، m1) & lt؛ f (hypo، m2)) { نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ نبسب ؛ l = m1 ؛ نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ ونبسب ؛} نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ ونبسب ؛ وإلا { نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ نبسب ؛ ص = م 2 ؛ نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ ونبسب ؛} نبسب ؛ نبسب ؛ ونبسب ؛} نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ على & nbsp؛ خارج & lt؛ & lt؛ ((l + r) / 2) ؛ نبسب ؛ نبسب ؛ نبسب ؛ العودة 0 ؛ }
يمكن تعديل البحث الثلاثي باستخدام & nbsp؛ طريقة المقطع الذهبي ، مما يزيد من معدل التقارب بمقدار ضعفين.
نبسب ؛
المصادر 1) نبسب ؛ البحث الثلاثي والنسبة الذهبية
2) & nbsp؛ & nbsp؛ بحث ثلاثي


نبسب ؛

Problem

ابحث عن الحد الأدنى للدالة \ (y = x \ cdot x - b \ cdot x + 100 \) ، حيث يكون المعامل b هو دخلت من لوحة المفاتيح.
نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1 10 5


ملاحظة كن حذرًا مما تبحث عنه الخوارزمية: الحد الأقصى أم الحد الأدنى.
نبسب ؛

time 1000 ms
memory 256 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>	
#include"math.h"	
using namespace std;

double f( double x, int b) {
// здесь должна быть ваша функция                     
}


int main() {
	double l = -100;
	double r = 100;
	double EPS = 1e-6; 
	int b;
	cin >> b;                
	cout << ((l + r) / 2);
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!