解答：2 + input * (input - 1)

推想過程：

1個圓可切割成圓內、圓外兩區域

所以f(1) = 2

2個圓除了各自區域外，加上兩圓相接區域以及兩圓以外的區域共4個區域

f(2) = 4

之後最右邊每多一個圓就會將最左邊的圓多切1區域

除了最左邊的圓以外都會多出2區域

所有圓以外的區域則會被多切出1區域

f(n) = f(n - 1) + 1 + (n - 2) * 2 + 1

     = f(n - 1) + (n - 1) * 2

接下來以f(5)來推導會看的較清楚

f(5) = f(4) + 4 * 2

     = f(3) + 3 * 2 + 4 * 2

     = f(2) + 2 * 2 + 3 * 2 + 4 * 2

     = f(1) + 1 * 2 + 2 * 2 + 3 * 2 + 4 * 2

     = 2 + (1 + 2 + 3 + 4) * 2

     = 2 + (((1 + 4) * 4) / 2) * 2

     = 2 + (1 + 4) * 4

     = 2 + 5 * (5 - 1)

把f(5)替換回f(n)

就可得知

f(n) = 2 + n * (n - 1)

單純分享思考過程喔

解答：2 + input * (input - 1)

 

推想過程：

1個圓可切割成圓內、圓外兩區域

所以f(1) = 2

2個圓除了各自區域外，加上兩圓相接區域以及兩圓以外的區域共4個區域

f(2) = 4

之後最右邊每多一個圓就會將最左邊的圓多切1區域

除了最左邊的圓以外都會多出2區域

所有圓以外的區域則會被多切出1區域

f(n) = f(n - 1) + 1 + (n - 2) * 2 + 1

     = f(n - 1) + (n - 1) * 2

 

接下來以f(5)來推導會看的較清楚

f(5) = f(4) + 4 * 2

     = f(3) + 3 * 2 + 4 * 2

     = f(2) + 2 * 2 + 3 * 2 + 4 * 2

     = f(1) + 1 * 2 + 2 * 2 + 3 * 2 + 4 * 2

     = 2 + (1 + 2 + 3 + 4) * 2

     = 2 + (((1 + 4) * 4) / 2) * 2

     = 2 + (1 + 4) * 4

     = 2 + 5 * (5 - 1)

把f(5)替換回f(n)

就可得知

f(n) = 2 + n * (n - 1)

 

單純分享思考過程喔

這個想法就是遞迴了： 找到遞迴関係式（recurrent relation）
再來就是推導出它解
然而，要用程式求解的話，應該要實現遞迴関係式，而不是去代公式喔～

//題目：https://zerojudge.tw/ShowProblem?problemid=a042
//https://zerojudge.tw/ShowThread?postid=28403&reply=0

#include <iostream>
using namespace std;

int an(int n) {
    if (n == 1)
        return 2;
    else {
        return ((n - 1) * 2 + an(n - 1));        
    }
}

int main(int argc, char** argv) {
    int n = 0;
 
    while ((cin >> n)) { //EOF = ^z = -1    
        cout << an(n) << endl;
    }

    return 0;
}