P3382 【模板】三分法

这篇具有很好参考价值的文章主要介绍了P3382 【模板】三分法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

三分其实是每次取L,R的终点mid,把mid左边一点点的函数值和右边一点点的函数值比较,舍弃一边的区间,这样不断缩小区间直到满足精度要求(一般eps取0.1*精度),但我们都喜欢取三等分点,其实只要是左边一点点和右边一点点就行了。

多项式求值还有个秦九韶算法,可以把2n+1次乘法n次加法简化为n次乘法和n次加法

浅记录一下吧~(当个笔记来用)

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;//其实一般精度*0.1=1e-6就可以了
int n;
double L,R;
double a[15];
//普通的求多项式
/*double F(double x)
{
 double f=0;
 for(int i=n;i>=0;i--)
 {
  double t=1;
  for(int j=1;j<=i;j++)
  t*=x;
  f+=a[i]*t;
 }
 return f;
}*/
//秦九韶算法从里到外逐层计算一次多项式的值
double F(double x)
{
 double sum=0;
 for(int i=n;i>=0;i--)
 sum=sum*x+a[i];
 return sum; 
}
int main()
{
 cin>>n>>L>>R;
 for(int i=n;i>=0;i--) cin>>a[i];
 while(fabs(L-R)>=eps)
 {
  double mid=(L+R)/2;
  if(F(mid+eps)>F(mid-eps)) L=mid;//舍弃左区间
  else R=mid;//舍弃右区间
 }
 printf("%.5lf",R);
 return 0;
}

over~文章来源地址https://www.toymoban.com/news/detail-606492.html

到了这里,关于P3382 【模板】三分法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 国内 RISC-V 产学研基地成立,Intel、Arm、RISC-V 将三分天下?

    作者 | 伍杏玲 出品 | CSDN(ID:CSDNnews) 在IT界,CPU芯片和操作系统是网信领域最基础的核心技术。但在芯片领域,技术和资本的门槛较高,应用范围最广的指令集架构需获得专利授权才能使用,如x86、Arm等。而投入研发的资金,以14nm工艺为例,需上亿元的研发费用。 如何降

    2024年01月17日
    浏览(50)
  • 一、基础算法9:区间合并 模板题+算法模板(区间合并)

    原题链接 https://www.acwing.com/problem/content/805/ 题目 803 . 区间合并 给定 n 个区间 [li,ri] ,要求合并所有有交集的区间。 注意如果在端点处相交,也算有交集。 输出合并完成后的区间个数。 例如:[1,3] 和 [2,6] 可以合并为一个区间 [1,6] 。 输入格式 第一行包含整数 n 。 接下来 n

    2024年02月04日
    浏览(33)
  • 算法基础课——基础算法(模板整理)

     快速排序 快速排序 第K个数 归并排序   归并排序 逆序对的数量 二分   数的范围 数的三次方根 高精度   高精度加法 Python一行就可以解决 高精度减法 高精度乘法 高精度除法 前缀和与差分 前缀和 子矩阵的和 差分 差分矩阵 双指针算法 最长连续不重复子序列 数组元素的目

    2024年02月12日
    浏览(42)
  • macOS Monterey 12.6.5 (21G531) OC 0.9.1 / Cl 5151 / PE 三分区原版黑苹果镜像

     苹果近期发布了 macOS Big Sur 11.7.6 和 macOS Monterey 12.6.5 更新,本次更新重点修复了标记为 CVE-2023-28206 的漏洞,在 macOS 13.3.1 更新中已修复,推荐大家安装升级。 macOS Monterey 12.6.5 (21G531) 三分区原版黑苹果镜像 或文末置顶评论前往官网下载         本次更新重点修复了标记为

    2024年02月02日
    浏览(46)
  • [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新)

    [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板( 持续更新..... ) 目录 一、算法基础 1.Huffuman树 2.Sine之舞 3.数列排序 4.数列排序 5.特殊回文数 6.回文数 7.特殊的数字 8.杨辉三角形 9.高精度加法 10.Fibonacci数列 11.报时助手 12.回形取数 13.矩阵乘法 二、算法提高 1.印章

    2023年04月08日
    浏览(47)
  • 差分算法及模板详解

    ⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法

    2023年04月09日
    浏览(52)
  • 【算法-动态规划】通用模板

    目录 一、动态规划是什么? 二、通用思路 2-1、状态的定义 2-2、状态转移方程 2-3、遍历顺序 2-4、初始化 2-5、结果输出 2-6、优化 2-6-1 空间的优化 2-6-2 递归实现VS迭代实现(数组存储) 动态规划(DP),即将问题不断转化为子问题,再通过子问题的求解,解决问题。 如下:

    2024年01月16日
    浏览(36)
  • 算法模板(4):动态规划(2)

    没有上司的舞会 树上最大独立集问题 Ural 大学有 N N N 名职员,编号为 1 ∼ N 1 sim N 1 ∼ N 。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数 H i H_i H i ​ 给出,其中 1 ≤ i ≤ N 1 le i le N 1 ≤ i ≤ N 。现在要召开一场周年

    2024年02月09日
    浏览(33)
  • 【基础算法练习】二分模板

    704. 二分查找,这道题目是最经典的二分查找,使用于任何模板(如果你学的模板连这道题都套不上,那大概是模板有问题) 34. 在排序数组中查找元素的第一个和最后一个位置,一个合格的二分模板,需要能够应对这道题目的两种二分情况,我待会儿也会以这道题作为例题

    2024年01月25日
    浏览(41)
  • 算法竞赛常用模板库

    本文使用 CC BY-NC-SA 4.0 许可 。 本文包含了笔者常用的 OI 算法、数据结构的模板。 不保证算法最优 ,但能通过相应的模板题(如果有会挂出)。 如有错误请在评论区指出(虽然大抵没人看就是了)。 码风是笔者的 个人习惯 (能看懂就好喵)。 代码会省略快读 Read() 。 持续

    2024年04月08日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包