读书人

递归算法的

发布时间: 2012-02-25 10:01:48 作者: rapoo

递归算法的求助!
这个程序是实现10个数的一个数组递归进行求和!

有没有更好的算法,能在主程序里面输出总和S! 请各位大虾指教!在此谢了!

#include "iostream.h "
void sum(int [],int);
int main()
{
const int size = 10;
int a [size] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37};
sum(a,size);
cout < <endl;
return 0;
}
void sum(int b[], int siz)
{ static int s=0;
if( siz> 0)
{
sum(&b[1],siz-1);
s=s+b[0];
cout < <s < <endl;
}
}


[解决办法]
#include <iostream>
using namespace std;

int sum(int*,int);
int main()
{
const int size = 10;
int a [size] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

cout < <sum(a,size) < <endl;
system( "pause ");
return 0;
}
int sum(int *b, int size)
{
if(size==1)
return b[0];
else
return b[0]+sum(b+1,size-1);
}

[解决办法]
#include <iostream.h>
int sum(int*,int);
int main()
{
const int size = 10;
int a [size] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

cout < <sum(a,size) < <endl;
system( "pause ");
return 0;
}
int sum(int *b, int size)
{
if(size==1)
return b[0];
else
return b[0]+sum(b+1,size-1);
}

[解决办法]
转........

利用模板元编程技术解开循环

模板元编程技术最早的实际应用之一是用于数值计算中的解循环。举个例子,对一个数组进行求和的常见方法是:
// sumarray.h

template <typename T>
inline T sum_array(int Dim, T* a)
{
T result = T();
for (int i = 0; i < Dim; ++i)
{
result += a[i];
}
return result;
}
这当然可行,但我们也可以利用模板元编程技术来解开循环:
// sumarray2.h

// 原始模板
template <int Dim, typename T>
class Sumarray
{
public:
static T result(T* a)
{
return a[0] + Sumarray <Dim-1, T> ::result(a+1);
}
};

// 作为终结准则的局部特化版
template <typename T>
class Sumarray <1, T>
{
public:
static T result(T* a)
{
return a[0];
}
};

用法如下:

// sumarraytest2.cpp

#include <iostream>
#include "sumarray2.h "

int main()
{
int a[6] = {1, 2, 3, 4, 5, 6};
std::cout < < " Sumarray <6> (a) = " < < Sumarray <6, int> ::result(a);
}
当我们计算Sumarray <6, int> ::result(a)时,实例化过程如下:
Sumarray <6, int> ::result(a)
= a[0] + Sumvector <5, int> ::result(a+1)
= a[0] + a[1] + Sumvector <4, int> ::result(a+2)
= a[0] + a[1] + a[2] + Sumvector <3, int> ::result(a+3)
= a[0] + a[1] + a[2] + a[3] + Sumvector <2, int> ::result(a+4)
= a[0] + a[1] + a[2] + a[3] + a[4] + Sumvector <1, int> ::result(a+5)
= a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
可见,循环被展开为a[0] + a[1] + a[2] + a[3] + a[4] + a[5]。这种直截了当的展开运算几乎总是比循环来得更有效率。
也许拿一个有着600万个元素的数组来例证循环开解的优势可能更有说服力。生成这样的数组很容易,有兴趣,你不妨测试、对比一下。




[解决办法]
int sum(int *b, int size){
return size> 0 ? (b[0]+sum(b+1,size-1)) : 0;
}
楼上的用模板只能是常数

读书人网 >C++

热点推荐