分治法求和-算法设计实验2

题目：用分治法求和
这里我们举出一个例子，利用分治法求数组的和：
比如: a[10] = {1,2,3,4,5,6,7,8,9,10} ,分治法的算法之前我们学数据结构的时候，有过应用，数据结构学过的归并排序，二分法，快速排序算法等里面用到的就是分治法的思想(顺便说一句,专业英语中分治法的英文是:divide and conquer)：
如图：

把一个大问题，分解成若干个小问题，这里把一个大的数组分解成若干个小数组，再合并把值返回。
下面看程序代码:

/*******************************************************
    > File Name: Separate.c  
    > Author:chendiyang  
    > School:WUST_CST_1501班  
    > Myblog:www.chendsir.com  
    > Mail:[e-mail]   
    > Created Time: 2017年12月18日 星期一 15时19分21秒 
********************************************************/     
#include<stdio.h>
#include<stdlib.h> 
int add(int *a,int left,int right);

int main()
{

    int i,n;
    int *array;
    printf("请输入数组的大小：");
    scanf("%d", &n);
    array = (int*) malloc(sizeof(int) * n);
    printf("请输入数据（用空格分隔）：");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }
    int sum=add(array,0,n-1);
    printf("%d\n",sum);

    return 0;
 } 

 int add(int *a,int left,int right)
 {
    int mid;
    if(left==right)
    {
        return a[left];
     }
     else if (left == right-1)
     {
        return a[left]+a[right];
     }
     else
     {
        mid=(left+right)/2;
        return add(a,left,mid)+add(a,mid+1,right);
     }
 }

运行结果:

题目还是比较简单的，但是利用分治法来求和在效率上明显很低，用一个循环一次遍历就可以实现求和了，而且效率比这个高。当然，这里只是出于老师实验要求的题目，能把实验分混到手就行了。