NO IMAGE
問題描述
求1 2 3 … n的值。
輸入格式
輸入包括一個整數n。
輸出格式
輸出一行,包括一個整數,表示1 2 3 … n的值。
樣例輸入
4
樣例輸出
10
樣例輸入
100

說明:有一些試題會給出多組樣例輸入輸出以幫助你更好的做題。

一般在提交之前所有這些樣例都需要測試通過才行,但這不代表這幾組樣例資料都正確了你的程式就是完全正確的,潛在的錯誤可能仍然導致你的得分較低。

樣例輸出
5050
資料規模與約定
1 <= n <= 1,000,000,000。

說明:請注意這裡的資料規模。

本題直接的想法是直接使用一個迴圈來累加,然而,當資料規模很大時,這種“暴力”的方法往往會導致超時。此時你需要想想其他方法。你可以試一試,如果使用1000000000作為你的程式的輸入,你的程式是不是能在規定的上面規定的時限內執行出來。

本題另一個要值得注意的地方是答案的大小不在你的語言預設的整型(int)範圍內,如果使用整型來儲存結果,會導致結果錯誤。

如果你使用C 或C語言而且準備使用printf輸出結果,則你的格式字串應該寫成%I64d以輸出long long型別的整數。

下面使用迭代法解題:

#include <iostream>
using namespace std;
int main()
{
int n;
long long s=0;
cin >> n;
for (int i = 1; i <= n; i  )
{
s = s   i;
}
cout << s << endl;
return 0;
}

下面使用遞迴解決:

#include <iostream>
using namespace std;
long long S(int n)
{
if (n == 1)
return 1;
else
return S(n - 1)   n;
}
int main()
{
int n;
cin >> n;
cout << S(n) << endl;
cin >> n;
return 0;
}

但是均超時了