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
85 0
|
1月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
51 2
|
1月前
|
存储 编译器 C++
【c++】类和对象(下)(取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象)
本文介绍了C++中类和对象的高级特性,包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项,帮助读者深入了解C++面向对象编程的核心机制。
105 5
|
1月前
|
存储 编译器 C++
【c++】类和对象(中)(构造函数、析构函数、拷贝构造、赋值重载)
本文深入探讨了C++类的默认成员函数,包括构造函数、析构函数、拷贝构造函数和赋值重载。构造函数用于对象的初始化,析构函数用于对象销毁时的资源清理,拷贝构造函数用于对象的拷贝,赋值重载用于已存在对象的赋值。文章详细介绍了每个函数的特点、使用方法及注意事项,并提供了代码示例。这些默认成员函数确保了资源的正确管理和对象状态的维护。
94 4
|
1月前
|
存储 编译器 Linux
【c++】类和对象(上)(类的定义格式、访问限定符、类域、类的实例化、对象的内存大小、this指针)
本文介绍了C++中的类和对象,包括类的概念、定义格式、访问限定符、类域、对象的创建及内存大小、以及this指针。通过示例代码详细解释了类的定义、成员函数和成员变量的作用,以及如何使用访问限定符控制成员的访问权限。此外,还讨论了对象的内存分配规则和this指针的使用场景,帮助读者深入理解面向对象编程的核心概念。
112 4
|
2月前
|
存储 编译器 对象存储
【C++打怪之路Lv5】-- 类和对象(下)
【C++打怪之路Lv5】-- 类和对象(下)
32 4
|
2月前
|
编译器 C语言 C++
【C++打怪之路Lv4】-- 类和对象(中)
【C++打怪之路Lv4】-- 类和对象(中)
32 4
|
2月前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
29 1
|
2月前
|
存储 编译器 C++
【C++类和对象(下)】——我与C++的不解之缘(五)
【C++类和对象(下)】——我与C++的不解之缘(五)
|
2月前
|
编译器 C++
【C++类和对象(中)】—— 我与C++的不解之缘(四)
【C++类和对象(中)】—— 我与C++的不解之缘(四)