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
92 0
|
25天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
4天前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
33 16
|
7天前
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
50 6
|
1月前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
25天前
|
安全 编译器 C语言
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
|
25天前
|
存储 程序员 C语言
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
2月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
85 19
|
2月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
79 13
|
2月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
68 5