陈许.ppt

?上午第 2例题确实不能二分答案。?给定零件和 S,设求出最小费用的绝对值为 R。?若 R>=S ,则存在大于等于 S的解。?若 R<S ,则不存在恰好等于 S的解。上午例题补充说明浮点误差与误差复杂度清华大学陈许旻引言浮点数存储原理舍入与浮点误差四则运算的误差更一般的误差分析方法算法中的误差避免浮点误差与误差复杂度?好不容易想到了一个计算几何算法?画图推公式费了好大劲?经过长时间的调试?终于得到了这样的结果你是否遇到过……浮点数给我们造成了哪些不便呢? double eps = 1e-8; bool equal(double a, double b){ return fabs (a - b) < eps ; } bool greater(double a, double b){ return a > b + eps ; }代码更加复杂?如果结果是 1,输出“ Yes ”,否则输出“ No ”。?计算结果: ?: 1e-4 ?输出: No ?结果: Wrong Answer ?将误差放大成错误?要求:保留 2位小数?答案 A: 输出: ?答案 B: 输出: ?实际差值≤ 3e-8 ?导致结果:在 1e-2 的范围内错误难以控制的精度要求?如果有多个满足要求的点,输出 x最小的,如果 x相等,输出 y最小的。答案保留 2位小数。?算得两个点(, ) 和(, ) ?我们该保留哪一个呢? ?引起的后果?A的精度比 B的低, 可能导致答案不同?A的精度比 B的高,也可能导致答案不同?必须两个人精度完全相同才能保证答案相同难以定义的取舍引言浮点数存储原理舍入与浮点误差四则运算的误差更一般的误差分析方法算法中的误差避免浮点误差与误差复杂度