How to sum the Integers from 1 to N.

說明

題目為計算1 + 2 + 3 + ... + N的總和,這題看似很簡單,其實真的很簡單,只是可能會有不同要求,一般直覺會使用迴圈解,不過有時候也會要求遞迴解,考你簡單遞迴觀念。

迴圈解

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

遞迴解

int sum(int n)
{
    if(n < 1)
        return 0;
    return n + sum(n - 1);
}

數學解

然後不論是迴圈還是遞迴解,都是O(n)的時間複雜度,有時候還會要求寫出O(1)的版本,這時候就要拿出數學的思考邏輯了,這沒記錯的話應該是高中數學的範圍。公式如下:

4a5c1aab5ec9b1bfbc19272bcfa83da4  

寫成程式

int sum(int n)
{
    return n * (n + 1) / 2;
}

相關類題

Write a function to calculate 1*2+2*3+...+(n-1)*n

一樣是求合的問題,同樣使用迴圈或遞迴即可,如果能用數學證明出公式的話,也可以直接套公式。

迴圈解

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

遞迴解

int sum(int n)
{
    if(n < 2)
        return 0;
    return (n - 1) * n + sum(n - 1);
}

數學解

int sum(int n)
{
    return n * (n + 1) * (2 * n + 1) / 6 - n * (n + 1) / 2;
}

數學推導上網找就有了,這邊就不做說明。

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()