【解題】會議中心 - Room

台北市96學年度高中資訊學科能力競賽 - 會議中心 (Room)


問題描述

　　拼拼樂會議中心是一個N×N的超大型可分割式會議中心。每一個1×1的空間都可以用隔板隔開，因此該會議中心最多可以有n²個獨立的1×1會議室，如要較大的會議室，則需將隔板拿掉使得二或更多個相鄰的1×1空間可以合併使用。圖一的會議中心最多可分隔成169個1×1小會議室，最少則全部合併成為一個13×13的會議室。每間1×1會議室皆以其二維平面座標為編號。選定一個1×1會議室並給予編號(0, 0)，相鄰的上、下、左、右會議室編號則依序為(0, 1), (0, -1), (-1, 0), (0, 1)。

　　會議中心外租會議室時，必須按照下列規則，組成合乎需求的會議室。一開始先以編號為(0, 0)的空間供租用，如果空間不足，則依序向右方、上方、左方、下方的空間合併成為較大的會議室。每次擴充時，新加入的空間必須為正方形且該邊長必須與相鄰的擴充前會議室邊長相同，如此才能確保合併後的會議室一定是四方形。下圖為例，第一次擴充租用空間時，右邊編號為(1, 0)的會議室空間會被跟編號為(0, 0)的會議室合併。第二次擴充時，在(0, 0), (1, 0)上方的四個(2×2正方形)小會議室會被合併進來。第三次擴充時，在(0, 0)~(0, 3)左邊的9個 (3×3正方形)小會議室會被合併進來。第四次擴充時，在(-3, 0)~(1, 0)下方的25個 (5×5 正方形)小會議室會被合併進來。第五次擴充時，在(0, -5)~(0, 2)右方的64個 (8×8 正方形)小會議室會被合併進來。後續的擴充則依此類推。



　　現在，若給定一個n的值，請計算第n次擴充時的正方形會議室的邊長。


輸入檔格式(C:\room\input.txt)

　　輸入檔只有一個整數n，n≦45。


輸出檔格式 (C:\room\output.txt)

　　請輸出第n次擴充時的正方形會議室的邊長。


輸入檔範例1

2


輸出檔範例1

2


輸入檔範例2

5


輸出檔範例2

8


解題思考

　　這道題目說實在真是落落長。然而其中的重點其實只有一個：答案是一個斐波那契數列(Fibonacci sequence)！第一項是1、第二項是2、第三項是3、第四項是5、......。之後的每一項，都是其前兩項之和。

　　說到這裡，這題不用多加解釋了吧！


參考解答(C++)

#include <iostream>
#include <fstream>

using namespace std;

int main(void)
{
    ifstream in("C:/room/input.txt");
    ofstream out("C:/room/output.txt", ios_base::trunc);

    int n, i;
    unsigned long t[2];

    cout << "讀入資料 . . ." << endl;

    in >> n;
    in.close();

    cout << n << endl;

    for (i = 0; i < n + 2; i++)
    {
        t[i % 2] = i < 2 ? 1 : t[0] + t[1];
    }

    out << t[i % 2] << endl;
    out.close();

    cout << "邊長為 " << t[i % 2] << endl;
    cout << "輸出資料在 ouput.txt" << endl;

    system("pause");
}