新手發問,一個遞迴的問題:1+(1+2)+(1+2+3)+....+(1+2+3+...+100)

一個遞迴的問題,1+(1+2)+(1+2+3)+....+(1+2+3+...+100)
請問如何用C/C++編寫這個遞迴問題.

謝謝各位

51 个解决方案

#1

总结出公式来即可。

#2

#include <iostream>
using namespace std;

int nbang(int n){
	if(n == 1 || n == 0){
		return 1;
	}
	else{
		return nbang(n - 1) + n;
	}
}

int main(){
	cout << "5! = " << nbang(100) << endl;
}

#3

不就是一个双重循环么？这么简单得题目要自己搞出来，否则学不会编程得

#4

//随便写了一个，希望能给你点思路，2楼那个就不要看了
#include <iostream>
using namespace std;

int function(int n){
	if(n <= 0){ //<---结束条件 
		return 0;
	}
	else{
		return function(n - 1) + n;
	}
}

int main(){
	cout << function(100) << endl;
}

#5

哦？好像没有看清题目哈～错了错了～抱歉～

#6

引用 2 楼 NirvanaVirus 的回复:

C/C++ code#include <iostream>
using namespace std;

int nbang(int n){
    if(n == 1 || n == 0){
        return 1;
    }
    else{
        return nbang(n - 1) + n;
    }
}

int main(){
    cout << "5! = " << nbang(100) << endl;
}

你这个不对吧，
你计算的结果为1+2+3+...+100=5050

#7

100*1+99*2+98*3 +  .... + 1*100;

#8

#include<iostream>

using namespace std; 
int n;
int f(int p)
{
	static int sum=1;
	if(p==1) return 1;
	int tmp=f(p-1)+p;
	sum+=tmp;
	if(p!=n) return tmp;
	else return sum;
}

int main() 
{ 
	int i,sum=0,tmp=0;
	n=100;
	//不使用递归
	for(i=1;i<=n;i++)
	{
		tmp+=i;
		sum+=tmp;
	}
	cout<<sum<<endl;
	//使用递归
	cout<<f(n)<<endl;
	return 0; 
} 
/*
output:
171700
171700
*/

#9

#include<iostream>
using namespace std;
int main()
{
int i=0;
int j=1;
int sum=0;
for(i;i<101;i++){
   sum+=j*(101-j);   //1加了100次，2加了99次，3加了98次。类推。
   j++;
}
cout<<sum<<endl;
return 0;
}

用递归算的话又重复计算，大O太大。

#10

记得这种数列是有公式计算的，高中的东西，忘记的差不多了，7楼的还可以将乘法次数减半

#11

#include <iostream>
using namespace std;
//1+(1+2)+(1+2+3)+....+(1+2+3+...+100)
long fun(int n)//为项的数目例如1+(1+2)+(1+2+3)是3项，n==3
{
    if (n<=0)
        return 0;
    long sum=0;
    long elem = 1;//存放每一项，默认是第一项的值
    int tmp = 0; //计数，要计算的项数

    while (tmp!=n)
    {
        sum += elem;
        tmp++;
        elem += (tmp+1);//计算下一项的值

    }
    return sum;
}
int main()
{
    cout<<fun(4);
}

运行结果：
171700
Process returned 0 (0x0)   execution time : 0.046 s
Press any key to continue.

这个没必要用递归，尽管递归简单！！

#12

顶楼上的

#13

#include <iostream>
using namespace std;

int AddN( int n)
{
int sum = 0;
for (int i=1;i<=n;i++)
{
    sum=sum+i;
}
return sum;
}

int Sum(int n)
{
int sum = 0;
for (int i=1;i<=n;i++)
{
    sum=sum + AddN(i);
}
        return sum;
}

int main(){
cout << Sum(100)<<endl;
}
干么要递归呢？直接计算不好么。

#14

int main()
{
    cout<<fun(4);
}
呵呵，不好意思，我上面的代码错了，应为：
int main()
{
    cout<<fun(100);
}

#15

...
对i*(i+1)/2求和,i=1...n.
=1/2*(1*(1+1)+2*(2+1)...n*(n+1))
=1/2*(2*1+2*2...n*n+1+2...n)
=1/2*(n*(n+1)*(2n+1)/6+n*(n+1)/2)

直接输出
(n*(n+1)*(2*n+1)/6+n*(n+1)/2)/2
就地了...

#16

#include <iostream>
using namespace std;
void main()
{
    int tmp =0, sum = 0;
    for(int i = 1; i <= 100; ++i)
    {
		tmp += i;
        sum += tmp;
    }
    cout<<"The sum is :"<<sum<<endl;

	cout<<Sum(100);
}

#17

#include <iostream>
using namespace std;

int function(int n)

{
  if(n<=0)
    {
     return 0;
    }
  else
  {
  return function(n - 1) + n;
  }
}
int ww(int x)
{ 
int n;
int xx=0;
for(n=x;n>=0;--n)
xx=xx+ function(n);
return xx;
}


int main(){
    cout << ww(100) << endl;
    
}

#18

#include <iostream>
using namespace std;

int sum(int n);
long total(int num);

int main()
{
int iTest;
cout<<"Please input an integer:"<<endl;
cin>>iTest;

cout<<total(iTest);

return 0;
}

int sum(int n)
{
int sum=0;
for(int i=1; i<=n; i++)
sum += i;
return sum;
}

long total(int num) //递归
{
if(num==1)
return 1;
return total(num-1)+sum(num);
}

#19

上面的多些了一个输出

#include <iostream>
using namespace std;
void main()
{
    int tmp =0, sum = 0;
    for(int i = 1; i <= 100; ++i)
    {
        tmp += i;
        sum += tmp;
    }
    cout<<"The sum is :"<<sum<<endl;
}

#20

这么多人都写出来了，呵呵，这个题还是用递归实现比较方便

#21

引用 7 楼 akirya 的回复:

100*1+99*2+98*3 +  .... + 1*100; 

很清楚

#22

这么简单要什么递归？

int sum =0;
int ii,jj;
for(ii=1; ii <= 100; ii++ ) {
     for(jj=1; jj <= ii; jj ++)
     {
          sum += jj;
      }
}

一开始这么简单得题目都不自己思考，是很难学好编程得，要是我，宁愿花几天去思考出来，也不来网站问

引用 20 楼 duanhuicen 的回复:

这么多人都写出来了，呵呵，这个题还是用递归实现比较方便

#23

#include <iostream>

using namespace std;

int add2(int m)
{
if(m<= 0) return 0;
else return add2(m-1) + m;
}


int add1(int n)
{
if(n<= 0) return 0;
else  return (add1(n-1) + add2(n)) ;
}

void main()
{
cout<<add1(100)<<endl;
system("pause");
}
算法和 zy0118 一样的！

#24

记住：在实现时，递归应该是最后没有办法才使用得方法，只要有一线希望不用递归，尽量不要用

引用 20 楼 duanhuicen 的回复:

这么多人都写出来了，呵呵，这个题还是用递归实现比较方便

#25

公式吧：

Sum ( Sum ( i , i = { 1, n } ), n = { 1, 100 } );

#26

引用 21 楼 hairetz 的回复:

引用 7 楼 akirya 的回复:
100*1+99*2+98*3 +  .... + 1*100; 

很清楚

的确很清楚！实现代码如下：

#define N 100
int main(void)
{
	int sum = 0;
	for(int i = 1; i <= N; i++)
	{
		sum += i * (N + 1 - i);
	}

	cout << sum << endl;

	return 0;
}

这种实现够简单了吧？

#27

引用 24 楼 arong1234 的回复:

记住：在实现时，递归应该是最后没有办法才使用得方法，只要有一线希望不用递归，尽量不要用 

引用 20 楼 duanhuicen 的回复:
这么多人都写出来了，呵呵，这个题还是用递归实现比较方便 

如果程序设计语言没有循环,只有递归呢?

#28

我觉得能用公式就用公式吧.

#29

有点想用递归

#30

#include<iostream>
using namespace std;
int main()
{int sum(int,int arry[]);
int s[1000],h;
h=sum(100,s);
cout<<h<<endl;
return 0;
}
int sum(int n,int arry[])
{int num(int);
int i,he=0;
for(i=1;i<=n;i++)
{arry[i]=num(i+1);
he=he+num(i);}
return he;
}
int num(int m)
{int a;
if(m==0)a=0;
else a=m+num(m-1);
return a;
}

#31

#include <iostream>
using namespace std;
void main()
{
    int tmp =0, sum = 0;
    for(int i = 1; i <= 100; ++i)
    {
        tmp += i;
        sum += tmp;
    }
    cout<<"The sum is :"<<sum<<endl;
}

一个一个的加。

#32

#include<iostream>
using namespace std;
int main()
{
	int n=0;
	int i;
	int s=0;
	for(i=1;i<=100;i++)
	{
		n=n+i;					//累计1+2+3……
		s=s+n;					//累计1+（1+2）+……
	}
	cout<<s<<endl;
	return 0;
}

#33

用 简单公式 线性增长比递归好

#34

友情up

#35

先给出递归定义 f(n) = n+ f(n-1);
根据这个定义来写递归函数。

#36

补充：定义写的不完整
n = 1时 f(1) = 1;
n > 1时 f(n) = n+ f(n-1); 

#37

引用 26 楼 pathuang68 的回复:

引用 21 楼 hairetz 的回复:
引用 7 楼 akirya 的回复: 
100*1+99*2+98*3 +  .... + 1*100; 

很清楚 


的确很清楚！实现代码如下： 

C/C++ code
#define N 100
int main(void)
{
    int sum = 0;
    for(int i = 1; i <= N; i++)
    {
        sum += i * (N + 1 - i);
    }

    cout << sum << endl;

    return 0;
}



这种实现够简单了吧？

够简单

#38

int Count(int max)
{    
    int times = max + 1;//循环从1开始到 max + 1
    int quotiety = times;//乘系数
    int result = 0;
    
    for (int i = 1; i < times; i++)
    {
        quotiety--;
        result += i * quotiety;
    }
    
    return result;
}

#39

数学方法。直接输出
(n*(n+1)*(2n+1)/6+n(n+1)/2)/2
其中n=100

#40

#include <iostream>
using namespace std;
int main()
{
int i,b=0,c=0;
for(i=1;i<=100;i++)
{
b=b+i;
c=c+b; //累加
}
cout<<"1+(1+2)+(1+2+3)+....+(1+2+3+...+100)="<<c<<endl;
return 0;
}

#41

#include<iostream>
#include<string>
using namespace std;

template<int N>
struct Sum
{
	enum{temp=Sum<N-1>::temp+N};
	enum{result=temp+Sum<N-1>::result};
};
template<>
struct Sum<1>
{
	enum{temp=1};
	enum{result=1};
};
int main()
{
	cout<<Sum<100>::result<<endl;
	system("pause");
}

#42

引用 35 楼 ZWHLOVEPRO 的回复:

先给出递归定义 f(n) = n+ f(n-1); 
根据这个定义来写递归函数。

没有必要使用递归

#43

UP

#44

没有一个语言设计者不是高手，因此按你这种想法设计的人是不存在的。顺序结构、分支结构和循环结构自19世纪90年代或者更早以后，就是一种深入人心的设计理念，没有人做相反的假设

引用 27 楼 baihacker 的回复:

引用 24 楼 arong1234 的回复:
记住：在实现时，递归应该是最后没有办法才使用得方法，只要有一线希望不用递归，尽量不要用 

引用 20 楼 duanhuicen 的回复: 
这么多人都写出来了，呵呵，这个题还是用递归实现比较方便 


如果程序设计语言没有循环,只有递归呢?

#45

还是用公式更快一些，这类多项式和的问题，总能转化为高1次的多项式公式直接计算。

递归也是个办法，不过由于递归应该是在栈上分配空间，递归层数过多的话是会溢出的。
因此有时才需要用数据结构的栈模拟递归。

对于这样的题，用公式直接算空间时间都是O(1)，用循环的话，空间O(1)，时间O(n)，用递归则一般都是O(n)。

#46

void main()
{
int temp = 0;
int iSum = 0;
for(int i=1; i<=100; i++)
{
int jTemp = 0;
for(int j=0; j<i; j++)
jTemp = jTemp + j;

temp = jTemp + i;
iSum = temp + iSum;
}
cout<<iSum<<endl;
cout<<sort(100)<<endl;
system("pause");
}

#47

#include <iostream>
using namespace std;
long fun(int n)
{
     long sum=0;
     if(n<=1)
     {
             return 1;
     }
     else
     {
         for(int elem=n;elem>=1;elem--)//执行(1+2+3+....n)
         {
                 sum+=elem;
         }
         return fun(n-1)+sum;//输出1+(1+2)+(1+2+3)+.....(1+2+3+n)
     }
}
int main()
{
    cout<<fun(100);
}
    
                    
     
     
     

#48

#include <iostream>
using namespace std;
long fun(int n)
{
     long sum=0;
     if(n<=1){return 1;}
     for(int elem=n;elem>=1;elem--){sum+=elem;}
     return fun(n-1)+sum;
}
int main()
{
    cout<<fun(100);
}
    

#49

引用 26 楼 pathuang68 的回复:

引用 21 楼 hairetz 的回复:
引用 7 楼 akirya 的回复: 
100*1+99*2+98*3 +  .... + 1*100; 

很清楚 


的确很清楚！实现代码如下： 

C/C++ code
#define N 100
int main(void)
{
    int sum = 0;
    for(int i = 1; i <= N; i++)
    {
        sum += i * (N + 1 - i);
    }

    cout << sum << endl;

    return 0;
}



这种实现够简单了吧？

这种最好了，简单又不用递归

#50

#include <iostream.h>

int main()
{
int sum = 0;
int sum_tmp = 0;
int j = 1;
for(int i = 1;i < 101 ; i++ )
{
j = i;
while( j > 0 )
sum += j--;
}
cout<<"sum = "<< sum <<endl;
return 0;
}
运行结果：sum = 171700