用减而治之和分而治之的思想分别实现数组求和(C++实现)

用减而治之和分而治之的思想分别实现数组求和(C++实现)

减而治之(Decrease-and-conquer)

为求解一个大规模的问题,可以

将其划分为两个子问题,其一平凡,另一规模缩减
分别求解子问题
由子问题的解,得到原问题的解

int sum(int A[],int n){
    return
        n < 1 ?
            0 :sum(A,n - 1) + A [n - 1];
}

分而治之(Decrease-and-conquer)

为求解一个大规模的问题,可以

将其划分为若干个(通常两个)子问题,规模大体相当
分别求解子问题
由子问题的解,得到原问题的解

int sum(int A[],int lo,int hi){
    if ( lo + 1 >= hi) return A[lo];
    int mi = (lo + hi) >> 1;
    return sum(A , lo , mi) + sum(A , mi , hi);
}
2+
Rhett Peng

软件工程大三在读学生,用个人网站记录学习动态

说点什么

avatar