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

痛定思痛。 2022-06-03 04:20 192阅读 0赞

题目：用分治法求和  
这里我们举出一个例子，利用分治法求数组的和：  
比如: a\[10\] = \{1,2,3,4,5,6,7,8,9,10\} ,分治法的算法之前我们学数据结构的时候，有过应用，数据结构学过的归并排序，二分法，快速排序算法等里面用到的就是分治法的思想：  
如图：  
![Center][]

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

#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,9);
        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);
         }
     }

运行结果:  
![Center 1][]

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

[Center]: /images/20220603/6b29aae848f94f5c9d7a7d13779df7aa.png
[Center 1]: /images/20220603/fd234f4a43054df0855ca115d13d43c9.png