前往
大廳
主題

ZeroJudge - b120: 函數計算 (Comp) 解題心得

Not In My Back Yard | 2020-12-17 00:00:05 | 巴幣 0 | 人氣 225

題目連結:


題目大意:
定義以下三個函數:

輸入有多列,每列給定一整數 x (-300 ≦ x ≦ 300),根據以上定義試問 f(x) 之值為何?



範例輸入:
3
-2
-21


範例輸出:
-1
-4
-1307


解題思維:
為了方便,以下所有函數的代入值皆以 x 代替。

g(x) 沒有什麼特別的,所以我們略過。

而我們如果真的去求值,可以看到從 x = 0 、 1 、 2 、 …… 開始,h(x) 會每六個作為一循環,而該循環節的內容為 -1 、 -1 、 2 、 5 、 5 、 2;而 x ≦ -1 的狀況就是維持定義的樣子。



而 f(x) 就比較複雜了一點:
先討論 x ≧ -1 時的情況:
x = h(x) 的狀況只會發生在 x = -1 以及 x = 2 的時候,因此 f(-1) = f(2) = 1;
x < h(x) 只會發生在 x = 3 、 4 (記住現在只討論 x ≧ -1 的狀況),而此時 f(3) = f(4) = f(2) - 2 = -1;
剩下的 x 值皆 > h(x),因此直接按照 f(x) = f(x - 1) - h(x) 依序求值。

再來是 x < -1 的狀況,此時 x 必定 < h(x) ,而且 g(x) 之值必不為 2。因此此時 f(x) = f(g(x)) - g(x)。

為了避免重複求值,我們需要將 f(x) 之值建表。而為此我們就需要先建出 x = -1 ~ 90000 之間的 f(x) 值。接著才能求 x = -300 ~ -2 之間的 f(x) 之值(可以看到 x = -300 時,g(x) = 89999,所以必得先求 f(89999) 之值才能求得 f(-300))。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作