C++二分有关溢出的问题

简介: C++二分有关溢出的问题

当我们使用二分


中间值m = (l+r)/2的时候,当l+r比较大的时候,往往会溢出;


伺机了解到一种方法 即一条避免溢出的恒等式


m= [(l+r)/2] = [(r-l)/2]+l ,


这里非常感谢🐟鱼佬的教导(数竞选手果然非同凡响)


3a562b5a286f41b68c49a3b7c0061b53.png


如果是简单的说明,不妨设(r-l)/2=x>=0 (是带有小数的实数)


那么l = n;


那么m= [(l+r)/2] = [(r-l)/2]+l 等效于 m =[n+x] = n+[x],其中n是正整数


很显然,如果一个正整数加上一个带有小数的实数再取整,等效于n直接加上x的取整


比如[7+3.84]=[10.84]=10 = 7+[3.84] =7+3 =10;


如果要从严格的数学推理证明,请看下面(再次感谢🐟佬耐心指点)


欲证[n+x] = n+[x],n∈Z且n>=0,x>=0;


不妨令①x = [x]+{x},说明:[x]代表向下取整的整数部分,{x}代表去掉整数部分的小数部分


对①式,把x用n+x代入,即n+x = [n+x]+{n+x}


即[n+x] = n+x-{n+x}


又因为欲证[n+x] = n+[x]


即证x-{n-x} = [x] ,由于n是整数,x是带有小数的正数,那么{n+x}即取n+x的小数部分,很显然,就是x的小数部分即{x},那么即{n-x} = {x}


即证x - {x} = [x],显然,证毕。


学习数学要多做习题,边做边思索。先知其然,然后知其所以然。——苏步青


相关文章
|
C++
C++ 各种无符号整型能够在溢出之前计算出斐波那契数列的最大项数是几?答案是24、47、93
C++ 各种无符号整型能够在溢出之前计算出斐波那契数列的最大项数是几?答案是24、47、93
61 0
|
2天前
|
C++
【C++】日期类Date(详解)②
- `-=`通过复用`+=`实现,`Date operator-(int day)`则通过创建副本并调用`-=`。 - 前置`++`和后置`++`同样使用重载,类似地,前置`--`和后置`--`也复用了`+=`和`-=1`。 - 比较运算符重载如`>`, `==`, `<`, `<=`, `!=`,通常只需实现两个,其他可通过复合逻辑得出。 - `Date`减`Date`返回天数,通过迭代较小日期直到与较大日期相等,记录步数和符号。 ``` 这是236个字符的摘要,符合240字符以内的要求,涵盖了日期类中运算符重载的主要实现。
|
4天前
|
存储 编译器 C语言
【C++航海王:追寻罗杰的编程之路】类与对象你学会了吗?(上)
【C++航海王:追寻罗杰的编程之路】类与对象你学会了吗?(上)
10 2
|
4天前
|
C++
C++职工管理系统(类继承、文件、指针操作、中文乱码解决)
C++职工管理系统(类继承、文件、指针操作、中文乱码解决)
7 0
C++职工管理系统(类继承、文件、指针操作、中文乱码解决)
|
4天前
|
存储 编译器 C++
【C++ 初阶路】--- 类和对象(下)
【C++ 初阶路】--- 类和对象(下)
7 1
|
4天前
|
存储 编译器 C语言
【C++初阶路】--- 类和对象(中)
【C++初阶路】--- 类和对象(中)
10 1
|
2天前
|
存储 编译器 C++
【C++】类和对象④(再谈构造函数:初始化列表,隐式类型转换,缺省值
C++中的隐式类型转换在变量赋值和函数调用中常见,如`double`转`int`。取引用时,须用`const`以防修改临时变量,如`const int& b = a;`。类可以有隐式单参构造,使`A aa2 = 1;`合法,但`explicit`关键字可阻止这种转换。C++11起,成员变量可设默认值,如`int _b1 = 1;`。博客探讨构造函数、初始化列表及编译器优化,关注更多C++特性。
|
2天前
|
编译器 C++
【C++】类和对象④(类的默认成员函数:取地址及const取地址重载 )
本文探讨了C++中类的成员函数,特别是取地址及const取地址操作符重载,通常无需重载,但展示了如何自定义以适应特定需求。接着讨论了构造函数的重要性,尤其是使用初始化列表来高效地初始化类的成员,包括对象成员、引用和const成员。初始化列表确保在对象创建时正确赋值,并遵循特定的执行顺序。
|
2天前
|
C语言 C++
【C++】日期类Date(详解)③
该文介绍了C++中直接相减法计算两个日期之间差值的方法,包括确定max和min、按年计算天数、日期矫正及计算差值。同时,文章讲解了const成员函数,用于不修改类成员的函数,并给出了`GetMonthDay`和`CheckDate`的const版本。此外,讨论了流插入和流提取的重载,需在类外部定义以符合内置类型输入输出习惯,并介绍了友元机制,允许非成员函数访问类的私有成员。全文旨在深化对运算符重载、const成员和流操作的理解。
|
2天前
|
定位技术 C语言 C++
C++】日期类Date(详解)①
这篇教程讲解了如何使用C++实现一个日期类`Date`,涵盖操作符重载、拷贝构造、赋值运算符及友元函数。类包含年、月、日私有成员,提供合法性检查、获取某月天数、日期加减运算、比较运算符等功能。示例代码包括`GetMonthDay`、`CheckDate`、构造函数、拷贝构造函数、赋值运算符和相关运算符重载的实现。