Module: üçlü arama


Problem

1/9

Üçlü Arama: Başlangıç ​​(C++)

Theory Click to read/hide

Üçlü arama
Segment [l, r] üzerindeki tek modlu bir fonksiyonun maksimumunu veya minimumunu bulmak için üçlü aramaya ihtiyacımız var. Bir fonksiyon, bir segmentte bir ekstremuma sahip olduğunda tek modludur.
Bir fonksiyonun maksimum değerlerinin aranması genellikle optimizasyon problemlerinde kullanılır. Örneğin, bir dik üçgende, alanın en büyük olacağı maksimum olası açıyı bulmamız gerekiyor.  Bunun için 0 ile 90 arasındaki açılardan geçeceğiz ve bu segmentte önce artacak sonra azalacak bir alan arıyoruz yani. işlev tek modlu olacaktır.
 
Nasıl çalışır
Çalışma prensibi ikili aramaya benzer, ancak segmenti ikiye böldüğümüzde, segmentin ortası tam olarak uç noktaya düştüğünde ve & nbsp; net bir sonuç alamayacağız.
Bu nedenle böyle bir durumu önlemek için segmenti ikiye değil üçe bölmek gerekir ve uç vb. Olmayan kısmı sınırlar sonuçta birleşene kadar atıyoruz.
çift ​​f( çift hipo, çift alfa) {     alfa = (alfa *M_PI)/180;     dönüş 0,5 * hipo * hipo * cos(alfa) * sin(alfa); } int ana() {     çift l = 0;     çift r = 90;     çift EPS = 1e-6;     çift hipo = 100;     while (r - l >=EPS) {         çift m1 = l + (r - l) / 3;         çift m2 = r - (r - l) / 3;         if (f(hipo, m1) < f(hipo, m2)) {             l=m1;         }         başka {             r=m2;         }     }          çıkış<< ((l + r) / 2);     0 döndür; }
Üçlü arama  altın bölüm yöntemi, bu da yakınsama oranını yaklaşık 2 kat artırır.
 
Kaynaklar
1)  üçlü arama ve altın oran
2)  üçlü arama


 

Problem

b katsayısının olduğu \(y=x \cdot x - b \cdot x + 100\) işlevinin minimum değerini bulun klavyeden girilir.< br />  
Örnekler


Not
Algoritmanızın ne aradığına dikkat edin: maksimum veya minimum.
 

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