昨天被問到這個問題，我想了下，只想出了三種方法，不知道還有沒有其它方法
1.sum = n(n+1)/2,等差數(shù)列求和
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
水 閱讀(2717)
評論(19) 編輯 收藏 引用 所屬分類:
算法與數(shù)據(jù)結構
FeedBack:
# re: 用至少三種方法實現(xiàn)1+2+...+n
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-05 19:34 |
template<int i>
struct sum
{
enum{ result=sum<i-1>::result }
}
template<>
struct sum<1>
{
enum {result = 1 };
}
result = sum<n>::result;
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-05 20:25 |
樓上的方法
template<>
struct sum<1>
{
enum {result = 1 };
}
下面的定義是什么意思啊？
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-05 20:33 |
template<int i>
struct sum
{
enum{ result=sum<i-1>::result + i; }
}
應該是這樣
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-05 20:48 |
呵呵，模板元編程其實也是遞歸的方式
還有宏定義也可以做到，也是遞歸的方式
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-06 09:53 |
模板元編程只能輸入實際的數(shù)值，不能用變量。
這么簡單的問題確實沒啥說的，但如果是求n！。
NB方法就用得上了。微線程實現(xiàn)遞歸。^_^
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-06 16:43 |
微線程實現(xiàn)遞歸?? 樓上的能否介紹下？？
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-07 10:24 |
就是當n很大時，遞歸深度有限制，還不能用循環(huán)的時候。生成n個微線程，第一個線程處理一次計算后將結果交給第2個線程，如此下去，當然只能用pythonless，erlang這些并發(fā)語言寫了。我只試過pythonless。
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-08 00:57 |
為什么不(a1+an) * n / 2 ?
這樣不是最高效么
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-08 10:02 |
@slackcode
第一種方式就是這個方式
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-08 20:46 |
@haskell
尾遞歸等于循環(huán)，非尾遞歸也是什么語言都會囧的
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-09 09:52 |
對呀，模板方法，而且是在編譯期就解決了，不過很詭異
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-09 10:52 |
@陳梓瀚(vczh)
囧是啥意思？
我只是想利用多核，并發(fā)語言的優(yōu)勢而已。
不過在算法一層可能沒多大用武之地。
我在想是否一個算法也能分解為更小的單元，可以方便利用多核，甚至是分布式的優(yōu)勢
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n[未登錄]
2008-09-09 12:14 |
目前似乎還沒有不需要人指定就分解成多線程的可以用的實現(xiàn)。分析最方便的是haskell這類的語言。
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-09-13 04:47 |
class ClassA()
{
public:
static int a;
static int b;
void ClassA()
{
a++;
b+=a;
}
}
ClassA a[n];
cout<<a[0].b;
回復 更多評論
# re: 用至少三種方法實現(xiàn)1+2+...+n
2008-10-09 10:53 |
既然多核的話，就用MapReduce的思想嘍。Map：直接返回值，分組，根據(jù)CPU數(shù)分組，Reduce：兩個求和，這樣也能用多核來做。
回復 更多評論