【解題】函數計算 - Comp

台北市95學年度高中資訊學科能力競賽 - 函數計算 (Comp)


問題描述

　　小明的數學老師出了一題函數計算的家庭作業，由於筆算的過程非常複雜，請你寫一個程式協助小明以及班上的其他同學進行驗算，以確定計算的結果是正確的。老師所出的題目是這樣的：給定一個整數 x，請求出函數 f 的值為何？




輸入格式(標準輸入)

　　直接從標準輸入(鍵盤)輸入一整數 x，-300 < x < 300。


輸出格式(標準輸出)

　　請將計算過後函數 f 的值直接輸出至標準輸出(螢幕)。


輸入範例1

3


輸出範例1

-1


輸入範例2

-2


輸出範例2

-4


輸入範例3

-21


輸出範例3

-1307


解題思考

　　乍看之下題目還滿簡單的，因此就直接照著題目的定義做吧。

　　然後接下來你會發現：大部分的測試資料程式都跑不動！這算是題目設計的小陷阱，假如就這樣照著題意實現，就會因為遞迴的呼叫，導致堆疊過多以致於溢位。

　　因此，在撰寫程式前，我們得先對題目做簡易的分析。

　　首先看到 f(x)，很明顯可以發現，其麻煩在於要比較 x 與 h(x) 的大小。因為 g(x) 的計算相對容易，在這裡，我選擇要簡化的是 x > h(x) 的情況。

　　又可以發現若且惟若 -3 < x < 2 或 x > 4 時，x > h(x) (可以自己手動計算看看)，因此我們從這個範圍的數字開始分析(我們先手動算出 f(-1) = 1, f(4) = -1)：

　　　f(0) = f(-1) - h(1) = 1 - h(1)
　　　f(1) = f(0) - h(1) = f(-1) - h(0) - h(1) = 1 - h(0) - h(1)

　　由上式整理可得，在 -3 < x < 2 時：

　　　f(x) = 1 - (h(0) + h(1) + ... + h(x))

　　　f(5) = f(4) - h(5) = -1 - h(5)
　　　f(6) = f(5) - h(6) = f(4) - h(5) - h(6) = -1 - h(5) - h(6)
　　　f(7) = f(6) - h(7) = f(5) - h(6) - h(7) = f(4) - h(5) - h(6) - h(7) = -1 - h(5) - h(6) - h(7)

　　同樣整理可得，在 x > 4 時：

　　　f(x) = -1 - (h(5) + h(6) + ... + h(x))

　　藉由這樣展開，就省去許多遞迴呼叫 f(x - 1) 的狀況(尤其在 x 相當大的情況)。(不過在這裡我可能還做複雜了，假如有誰有更好的方法，歡迎提出。)

　　接著，我們看到 h(y) 在 y 大於等於 2 的情況：

　　　h(2) = 2
　　　h(3) = 5
　　　h(4) = 5
　　　h(5) = -1
　　　h(6) = -1
　　　h(7) = 2

　　　h(8) = 2
　　　h(9) = 5
　　　h(10) = 5
　　　h(11) = -1
　　　h(12) = -1
　　　h(13) = 2

　　這裡，我們可以發現，h(y) 每六個數字為一個循環週期，因此，我們只要根據 y 除以 6 的餘數，就能夠判斷 h(y) 的結果了。

　　最後，g(z) 就照著題目的定義實現即可。


參考解答(C)

#include <stdio.h>
#include <stdlib.h>

int f(int), h(int), g(int);

int main(void)
{
    int x;

    printf("請輸入一個整數X:");
    scanf("%d", &x);
    printf("函數計算結果：%d\n", f(x));

    system("pause");
}

// f(x)的函數
int f(int x)
{
    int i, ret;
    if (x > h(x))
    {
        i = x < 5 ? 0 : 5;
        ret = x < 5 ? 1 : -1;

        for (; i <= x; i++)
        {
            ret -= h(i);
        }

        return ret;
    }
    else if (x < h(x))
    {
        return f(g(x)) - g(x);
    }
    else
    {
        return 1;
    }
}

// h(y)的函數
int h(int y)
{
    if (y < 2)
    {
        return -1;
    }
    else
    {
        switch(y % 6)
        {
            case 2:
            case 5:
                return 2;

            case 3:
            case 4:
                return 5;

            default:
                return -1;
        }
    }
}

// g(z)的函數
int g(int z)
{
    if(z <= 2)
    {
        return z * z - 1;
    }
    else
    {
        return 2;
    }
}