Module: tìm kiếm bậc ba


Problem

1/9

Tìm kiếm bậc ba: Bắt đầu (C++)

Theory Click to read/hide

Tìm kiếm bậc ba
Chúng ta cần tìm kiếm bậc ba để tìm giá trị lớn nhất hoặc giá trị nhỏ nhất của một hàm đơn thức trên đoạn [l, r]. Hàm số là đơn phương khi nó có một cực trị trên một đoạn.
Việc tìm kiếm các giá trị lớn nhất của một hàm thường được sử dụng cho các bài toán tối ưu hóa. Ví dụ: chúng ta cần tìm góc lớn nhất có thể có của một tam giác vuông mà tại đó diện tích sẽ lớn nhất.  Để làm điều này, chúng tôi sẽ xem xét các góc từ 0 đến 90 và trên phân khúc này, chúng tôi đang tìm kiếm một khu vực sẽ tăng trước rồi sau đó giảm, tức là. chức năng sẽ là đơn thức.
 
Cách thức hoạt động
Nguyên tắc hoạt động tương tự như tìm kiếm nhị phân, nhưng chúng ta có thể gặp trường hợp khi chia đoạn làm đôi, khi đoạn giữa của đoạn rơi chính xác vào điểm cực trị và & nbsp; chúng tôi sẽ không nhận được kết quả rõ ràng.
Do đó, để tránh trường hợp như vậy, cần phải chia đoạn không phải thành hai phần mà thành ba phần và chúng tôi loại bỏ phần không có cực trị, v.v., cho đến khi các ranh giới hội tụ về kết quả.

double f(hypo kép, alpha kép) {     alpha = (alpha *M_PI)/180;     return 0,5 * hypo * hypo * cos(alpha) * sin(alpha); } int main() {     gấp đôi l = 0;     gấp đôi r = 90;     nhân đôi EPS = 1e-6;     hypo gấp đôi = 100;     while (r - l >=EPS) {         nhân đôi m1 = l + (r - l)/3;         nhân đôi m2 = r - (r - l)/3;         if (f(hypo, m1) < f(hypo, m2)) {             l=m1;         }         khác {             r=m2;         }     }          ra<< ((l+r)/2);     trả về 0; }
Tìm kiếm bậc ba có thể được sửa đổi bằng cách sử dụng  phương pháp phần vàng, làm tăng tốc độ hội tụ lên khoảng 2 lần.
 
Nguồn
1)  tìm kiếm ternary và tỷ lệ vàng
2)  tìm kiếm bậc ba


 

Problem

Tìm giá trị nhỏ nhất của hàm \(y=x \cdot x - b \cdot x + 100\), trong đó hệ số b là được nhập từ bàn phím.
 
Ví dụ
<đầu>


Lưu ý
Hãy cẩn thận với những gì thuật toán của bạn đang tìm kiếm: tối đa hoặc tối thiểu.
 

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++
# Đầu vào Đầu ra
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!