三分-程序员宅基地

技术标签: # 知识点  --------其他--------  

【例题引入】

例题传送门三分法

题目大意:给出一个N次函数,保证在范围 [ l,r ] 内存在一点x,使得 [ l,x ] 上单调增[ x,r ] 上单调减。试求出x的值。(洛谷 3382)

这道题,若没学三分,第一个想法应该是用二分,但是二分出来的答案不好判断是否合法(至少本蒟蒻不知道怎么判断)

这个时候我们想到三分,三分法一般适用于求单峰函数极值的一些东西

 

【基本思想】

其实三分和二分的做法差不多,只不过二分是找 [ l,r ] 间的中点,三分是找 [ l,r ] 间的三等分点

那么 m1 = l + ( r - l ) / 3 , m2 = r - ( r - l ) / 3

我们将两个点中更优的点叫做好点(若计算单峰函数的最大值,则函数值更大的那个点就为好点;若计算单峰函数的最小值,则函数值更小的那个点就为好点),另一个叫做坏点,如下图:

上图中,我们用 m1 代替 mid,m2 代替 mmid

很显然,m1 是好点,m2 是坏点

又因为在 [ l,r ] 中这是单峰函数,所以最优点和好点应在坏点同侧(可以自己画图理解),那缩小范围的时候就把 r 改成 m2 ,即我们的求解区间从 [ l,r ] 变为 [ l,m2 ] ,不断缩小范围直到求出解

 

【代码】

(其实三分不是一种常用的算法,大家了解一下就行了)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps=1e-12;
int n;
double a[15],w[15];
double f(double x)
{
	int i;
	double pow=1,ans=0;
	for(i=n+1;i>=1;--i)
	{
		ans+=a[i]*pow;
		pow*=x;
	}
	return ans;
}
int main()
{
	int i;
	double l,r,m1,m2;
	scanf("%d",&n);
	scanf("%lf%lf",&l,&r);
	for(i=1;i<=n+1;++i)
	  scanf("%lf",&a[i]);
	while(r-l>=eps)
	{
		m1=l+(r-l)/3;
		m2=r-(r-l)/3;
		if(f(m2)-f(m1)>=eps)
		  l=m1;
		else
		  r=m2;
	}
	printf("%.5lf",l);
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/forever_dreams/article/details/81093369

智能推荐

mac 给 iPhone 充电一直闪跳_15年的苹果笔记本充电灯老是闪-程序员宅基地

文章浏览阅读7.1k次。当前macOS系统是10.14.5 iPhoneXR系统是12.2 用的是原装的数据线 连接调试和充电一直闪跳 解决方案打开mac终端 输入 sudo killall -STOP -c usbd本文作者http://blog.csdn.net/qiqi_lj..._15年的苹果笔记本充电灯老是闪

局部动态地图(LDM)的介绍-程序员宅基地

文章浏览阅读7.5k次,点赞2次,收藏6次。局部动态地图(Local dynamic map :LDM)简介局部动态地图(Local Dynamic Map)最早在欧洲的C-ITS项目SAFESPOT中提出,它是ITS框架中的重要组成部分。下面分别从ITS系统简介、LDM组成和LDM应用三大部分来对LDM进行一个简单的介绍。1、ITS系统简介智能交通系统(ITS)包含了很多涉及到汽车、火车、轮船、飞机等各种交通工具,概述如下图所..._ldm

mysql-administrator的安装与使用(图文)_mysql administrator-程序员宅基地

文章浏览阅读1w次,点赞2次,收藏17次。 在D盘建立一个mysql-software的目录,把刚才下载的 mysql-administrator-1.0.19-win-noinstall.zip 复制到这个子目录中,解压,得到一个 MySQL Administrator 1.0 的目录。同样如此操作 mysql-query-browser-1.1.5-win-noin..._mysql administrator

w2_fin,谢谢!-程序员宅基地

文章浏览阅读185次。# -*- coding: utf-8 -*-"""Created on Tue Aug 25 10:29:02 2020@author: 19749"""from PyQt5.QtWidgets import *from PyQt5.QtCore import *from PyQt5.QtGui import *from datetime import datetimeimport pandas as pdclass data: def data11(self):

vue中使用CSS预处理器-程序员宅基地

文章浏览阅读3.1k次。常见的stylus、sass、LESSvue中常用的是stylus,因为来源于node.js,与JS关系密切,语法灵活、方便易用。使用stylus可以使用变量、函数、循环来编写CSS样式文件。stylus使用方法:npm install stylus编辑器中按照stylus插件初次使用stylus命令 vue init webpack stylus----cd stylus...

依托学生表(student)、选课表(sc)、课程表(course),对SQL常见的查询关键词:所有、平均、同一、同时、最多、最高等进行详解。_设有学生情况表s(学生编号,姓名)、选课表sc(学生编号、课程编号),要查询所有-程序员宅基地

文章浏览阅读1.7k次,点赞2次,收藏12次。依托学生表(student)、选课表(sc)、课程表(course),对SQL常见的查询关键词:所有、平均、同一、同时、最多、最高等进行详解。1. 查询语句基本结构:select 列名1| 表名1.列名 | 表名1.* | 聚合函数1 [,列名2 | 表名2.列名 | 表名2.* | 聚合函数2, ...]from 表名1 | 子查询表1 [, 表名2 | 子查询表2, ...][where 条件1 [and | or 条件2, ...][group by 列名 [having 聚合函数条件1 _设有学生情况表s(学生编号,姓名)、选课表sc(学生编号、课程编号),要查询所有

随便推点

Windows中CreateProcess函数用法(转)_windows.createprocess-程序员宅基地

文章浏览阅读835次。1.函数说明:WIN32API函数CreateProcess用来创建一个新的进程和它的主线程,这个新进程运行指定的可执行文件。2.函数原型:BOOL CreateProcess( LPCTSTR lpApplicationName,_windows.createprocess

BAT招聘PHP程序员,曾经问过的10个PHP面试问题_bat面试php试题-程序员宅基地

文章浏览阅读466次。PHP程序员的面试,尤其是初面,最看重的就是基础,基础,还是基础。下面列举出10个问题,涉及的面比较广,但都是一个程序员应当也应该知道的东东。【1】PHP的整型溢出问题是怎样的?PHP的整型数的字长和平台有关,对于32位的操作系统,最大的整型是有二十多亿,其实就是2的31次方,最小为-2的31次方,PHP不支持无符号的整数。 如果一个数超出了integer范围,将会被自动解释为fl_bat面试php试题

Web开发前端、后端与全栈的区别是什么?_动态网站开发技术和web全栈有啥区别-程序员宅基地

文章浏览阅读7.8k次,点赞2次,收藏26次。刚入门Web开发者总会听到前端开发、后端开发、全栈开发等岗位描述及相关介绍说明。很多人不清楚前端、后端、全栈到底指的是什么?对应岗位需求是什么?本文主要从三者概念、技术内容要求等角度对前端、后端及全栈进行简单说明。web开发1、前端开发(Front-End Development)在基于浏览器的Web页面开发中,前端开发主要是指创建Web应用与使用者的交互体验效果与人机交互页面..._动态网站开发技术和web全栈有啥区别

MySQL frm、MYD、MYI数据文件恢复_myd myi-程序员宅基地

文章浏览阅读1.8k次。.frm、.MYI、.MYD 文件分别是 MySQL 的 MyISAM存储引擎存储的表结构、索引、数据文件。_myd myi

iOS开发-毛玻璃效果-程序员宅基地

文章浏览阅读104次。直接上代码!!!!!!UIImageView *backImageView = [[UIImageView alloc] initWithFrame:self.view.bounds]; backImageView.image = [UIImage imageNamed:@"picture.jpg"]; [self.view addS..._ios开发 uiimageview毛玻璃效果

Python: Can't start new thread解决方案(设置线程上限)-程序员宅基地

文章浏览阅读3.1w次,点赞3次,收藏15次。背景:在编写一个爬虫的时候,检查用多线程来检测结果有效性的时候,线程启动过多报错:thread.error: can't start new thread方案:使用Thread中的event,并进行上锁设置来解决。原因:这个是由于每台计算机能进行的并行是有上限的,经过测试本机的上限为1023个左右(win7 64位,i3 2核4线程),可以进行设置提高上限,但我觉得此处没有必要..._can't start new thread