关于计算精度

    本文是Sam我总结的，在C++学习过程中常见的一些涉及计算精度的问题，可谓明察秋毫之作！

 

1. 计算过程使用高精度类型(如，double)，转型(如，最终结果转换为int)放在最后一步完成

 

举例：（最少乘法次数，C++）

/*
题目描述：

给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。
如24：2*2=22（第一次乘），22*22=24（第二次乘），所以最少共2次。
  211：2*2=22（第一次乘），22*22=24（第二次乘）24*24=28（第三次乘）28*22=210（第四次乘）210*21=211（第五次乘）所以最少共5次。

输入
第一行m表示有m(1<=m<=100)组测试数据；
每一组测试数据有一整数n（0<n<=10000）;
 
输出
输出每组测试数据所需次数s;

样例输入
3
2
3
4

样例输出
1
2
2

-----------------------------------------------------------------

解题方法：

每次寻找小于等于n的最大的2k的值，如11，先找23=8，然后以此类推。

则可以转换为二进制计算。

其算法类似于把一个十进制数转换为二进制。只要把最高位1转换的次数记下来，再加上这个二进制其它为1的位的个数。例如：
(14)10=(1110)2
最高位的1需要转换3次，所以计算14次方需要3+2(其它为1的位数）=5次。
(100)10=(1100100)2
最高位的1需要转换6次，所以计算100次方需要6+2（其它为1的位数）=8次。

此算法关键在于最高位1转换的次数。（2倍增长是速度最快！）只要算出最高位的1，则低位的1已经被全部算出。因为最高位的1是通过1+1=2 2+2=4 4+4=8 8+8=16……算出来的，则最高位转换次数算出后，其他为1的位只是在使用的时候加一次。（二分思想）
*/
#include <iostream>
#include <cmath>
using namespace std;

int countOne(int n){
    int cnt=0;
    while(n>0){
        n-=(n&(-n));
        cnt++;
    }
    return cnt;
}

int main(){

    int cases;
    cin>>cases;
    
    while(cases--){
        int n;
        cin>>n;
        
        //提高计算精度：
        //   计算全过程使用double，只最终进行一次int转型.
        //   尽量不要将中间结果转换成int
         
        cout<< log((double)n)/log(2.0) + countOne(n)-1 <<endl;  //当n=8时，输出3(正确) 
        
        //cout<< (int)( log((double)n)/log(2.0)) + countOne(n)-1<<endl;  //当n=8时，输出2(错误)
    }

    system("pause");
    return 0;
}

 

2.无穷迭代，判断是否收敛：引入最小误差项eps

 

举例：（泰勒级数计算正弦值，C++）

/*
  利用泰勒(Taylor)級數展開式，三角正弦函數sin(x)=x – ((x^3)/3!) + ((x^5)/5!) – ((x^7)/7!) + ((x^9)/9!) - ……
  設計一程式，輸入角度0-360度(必須轉換為弳度)，計算其sin值。
*/
#include <iostream>
using namespace std;

const double eps=1e-15; //最小误差项
const double pi=3.14159265358979323846;

int main(){
    double angle;    //角度
    double x;         //(对应)弧度 
    double ans1, ans2;      //ans1: 本次结果， ans2:上次结果
    double numerator;       //分子
    double denominator;     //分母
    
    cout<<"Please input the angle: ";
    cin>>angle;
    x=angle/180*pi;
    
    //写代码时，先写下面do...while()循环，再来写这三个初始化值，不易出错 
    ans1=x;
    numerator=x;
    denominator=1.0;
    
    int i=2;
    do{
        ans2=ans1;
        numerator*=-x*x;
        denominator*=( i*(i+1) );
        
        ans1=ans2+ numerator/denominator;
        
        i+=2;
    }while(ans1-ans2>eps || ans2-ans1>eps);
    
    //cout<<"res="<<ans1<<endl;
    printf("sin(%.2lf) = %.6lf\n",angle, ans1);
    
    system("pause");
    return 0;
}

 

3.double类型指定精度输出

 

举例：（见上例，C++）

double angle=...
double ans1=...

//小数点后w位的double类型输出: printf("%.wlf",d);
printf("sin(%.2lf) = %.6lf\n",angle, ans1);