高中生程式解題系統:空間切割

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。
題目連結 http://zerojudge.tw/ShowProblem?problemid=a044

此題可用遞迴(Recursion)或是動態規畫(Dynamic Programming)方式來解,也可以用公式解:


遞迴版本程式碼:
#include <iostream>
#include <cmath>

using namespace std;

int numD( short n )
{
    if( n <= 3 )
        return pow(2.0, n);
    else
    {
        int k = n - 1;
        int c = (k * k + k + 2)/2;
        n = n -1;
        return numD(n) + c;
    }
}

int main()
{
    int n;
    int d;

    while( cin >> n )
    {
        d = numD(n);
        cout << d << endl;
    }

    return 0;
}

公式解程式碼:
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n;
    int d;

    while( cin >> n )
    {
        d = (n * (n * n + 5))/6 + 1;
        cout << d << endl;
    }

    return 0;
}

沒有留言: