aurain
技术文摘
posts - 137,  comments - 268,  trackbacks - 0

昨天被问到这个问题,我想了下,只想出了三种方法,不知道还有没有其它方法
1.sum = n(n+1)/2,等差数列求和
2.sum = 0;for(int i=1;i<=n;++i) sum += i;,普通的方法
3.int s(int n)
  {
     if (n == 1)
        return 1;
    else
       return n + s(n-1);
 }

递归的方式
posted on 2008-09-05 16:55 阅读(2667) 评论(19)  编辑 收藏 引用 所属分类: 算法与数据结构

FeedBack:
# re: 用至少三种方法实现1+2+...+n
2008-09-05 18:05 |
还有模板的方式  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-05 19:34 | cexer
template<int i>
struct sum
{
enum{ result=sum<i-1>::result }
}

template<>
struct sum<1>
{
enum {result = 1 };
}

result = sum<n>::result;
  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-05 19:37 | Bill Hsu
...
这位很有聊。。。  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-05 20:25 | bill
楼上的方法

template<>
struct sum<1>
{
enum {result = 1 };
}


下面的定义是什么意思啊?  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-05 20:33 | bill
template<int i>
struct sum
{
enum{ result=sum<i-1>::result + i; }
}

应该是这样  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-05 20:48 | 海边沫沫
呵呵,模板元编程其实也是递归的方式
还有宏定义也可以做到,也是递归的方式  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-06 01:19 | winsty
........
太有聊了啊  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-06 09:53 | haskell
模板元编程只能输入实际的数值,不能用变量。
这么简单的问题确实没啥说的,但如果是求n!。
NB方法就用得上了。微线程实现递归。^_^  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-06 16:43 | 11
微线程实现递归?? 楼上的能否介绍下??  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-07 10:24 | haskell
就是当n很大时,递归深度有限制,还不能用循环的时候。生成n个微线程,第一个线程处理一次计算后将结果交给第2个线程,如此下去,当然只能用pythonless,erlang这些并发语言写了。我只试过pythonless。  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-08 00:57 | slackcode
为什么不(a1+an) * n / 2 ?
这样不是最高效么  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-08 10:02 |
@slackcode
第一种方式就是这个方式  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-08 10:02 |
@haskell
呵呵,这个想法不错  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-08 20:46 | 陈梓瀚(vczh)
@haskell
尾递归等于循环,非尾递归也是什么语言都会囧的  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-09 09:52 | 李现民
对呀,模板方法,而且是在编译期就解决了,不过很诡异  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-09 10:52 | haskell
@陈梓瀚(vczh)
囧是啥意思?
我只是想利用多核,并发语言的优势而已。
不过在算法一层可能没多大用武之地。
我在想是否一个算法也能分解为更小的单元,可以方便利用多核,甚至是分布式的优势  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n[未登录]
2008-09-09 12:14 | 陈梓瀚(vczh)
目前似乎还没有不需要人指定就分解成多线程的可以用的实现。分析最方便的是haskell这类的语言。  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-09-13 04:47 | ricepig
class ClassA()
{
public:
static int a;
static int b;
void ClassA()
{
a++;
b+=a;
}
}

ClassA a[n];
cout<<a[0].b;  回复  更多评论
  
# re: 用至少三种方法实现1+2+...+n
2008-10-09 10:53 | hsen
既然多核的话,就用MapReduce的思想喽。Map:直接返回值,分组,根据CPU数分组,Reduce:两个求和,这样也能用多核来做。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(17)

随笔分类(138)

随笔档案(137)

网络开发

最新随笔

搜索

  •  

积分与排名

  • 积分 - 493571
  • 排名 - 36

最新随笔

最新评论

阅读排行榜

评论排行榜