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

野性酷女 2022-06-03 04:19 187阅读 0赞

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

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

/*******************************************************
        > File Name: Separate.c  
        > Author:chendiyang  
        > School:WUST_CST_1501班  
        > Myblog:www.chendsir.com  
        > Mail:1441353519@qq.com   
        > 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);
         }
     }

运行结果:  
![这里写图片描述][SouthEast 1]

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

[SouthEast]: /images/20220603/cf980a3030be42039a93bfe2e67d286a.png
[SouthEast 1]: /images/20220603/83e4c3423fbe43e7bf2703a0dfe9d8db.png