减治法之一维数组求和（减一治）

减治法之一维数组求和（减一治）

【减治法的设计思想】

        减治法（reduce and conquer method)将原问题分解为若干个子问题，并且原问题（规模为n)的解与子问题（规模通常是n/2或n-1)的解之间存在某种确定的关系，这种关系通常表现为：

（1）原问题的解只存在于其中一个较小规模的子问题中；

（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。

【问题描述】利用减治法对一维数组求和

输入：待求和数列a[]和求和区间[L,R]

输出：a[L]～a[R]的和

【算法描述】

输入：待求和数列a[]和求和区间[L,R]

输出：a[L]～a[R]的和

1.如果L==R，表明求和区间只有一个数据，返回该数据，算法结束；

2.递归调用TheSUM(a[] , L,  R-1)得到a[L]～a[R-1]的和lsum

3.返回lsum+a[R],算法结束；

【算法实现】

#include

int TheSUM(int a[], int L, int R)
{
	if (L == R) return a[L];            //L==R表明只有一个数据
	int lsum=TheSUM(a, L, R-1);         //递归调用求和
	return lsum + a[R];
}

int main()
{
	int a[100];
	int L,R;
	int n;
	printf("请输入数字个数：");
	scanf("%d", &n);
	printf("请输入待求和区间：");
	scanf("%d %d", &L,&R);
	printf("请输入待求和数组：");
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}

	int sum = TheSUM(a, L, R);
	printf("%d", sum);
}

【实例说明】

 

PS:如有错误，还请指正，谢谢！