• 發現自己幾乎沒在用這 blog，決定多發一些廢文
    今天寫這題還覺得蠻有趣的，特發文以志之
  • problem link

  • 題目：
    \(k \in N, f(k) = \begin{cases} 1 &\text{if $k$ = 1} \\ \frac 1 {f(k - 1)} &\text{if $k$ is odd} \\ 1 + f(\frac k 2) &\text{if $k$ is even} \end{cases}\)
    給定 \(\{ a \in N, b \in N \mid 1 \le a, b \le 60 \}\)，求 \(\{ k \in N \mid f(k) = \frac a b \}\)

  • 解法：
    從前從前有個肥宅跟我說過，解數列問題時，最重要的是觀察
    我們先照題目敘述建個表觀察看看吧！
    建表 code，輸出為 LaTeX

    \[\begin{array}{c|c} k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline f(k) & 1 & 2 & \frac 1 2 & 3 & \frac 1 3 & \frac 3 2 & \frac 2 3 & 4 & \frac 1 4 & \frac 4 3 \\ \end{array}\]

    觀察 \(f(k)\) 可發現

    \[k > 1, \begin{cases} f(k) > 1 &\text{if $k$ is even} \\ 1 > f(k) > 0 &\text{if $k$ is odd} \end{cases}\]

    證明如下：

    \[\begin{array}{l} \text{Proof} \\ \text{1. }f(1) = 1 > 0 \\ \text{2. if }f(k) > 0 \\ f(2k) = 1 + f(k) > 1 \\ 0 < \frac 1 {f(2k)} < 1 \\ f(2k + 1) = \frac 1 {f(2k)} \\ 0 < f(2k + 1) < 1 \\ \Rightarrow \forall k \in \Bbb{N}, k > 1,\\ \begin{cases} f(k) > 1 &\text{if $k$ is even} \\ 1 > f(k) > 0 &\text{if $k$ is odd} \end{cases} \end{array}\]

    因此，對於給定的 \(f(k)\) 值，可與 1 比較大小來判斷其為偶數項或奇數項

    又，由定義移項可得

    \[\begin{cases} f(k - 1) = 1 / f(k), &\text{if $k$ is odd} \\ f(\frac k 2) = f(k) - 1 &\text{if $k$ is even} \\ \end{cases}\]

    由上述兩個性質可設計出 \(f(k)\) 的反函數 \(f^{-1}(x) \)

    \[f^{-1}(x) = \begin{cases} 1, &\text{if $x$ = 1} \\ 2 \times f^{-1}(x - 1), &\text{if $x$ > 1} \\ 1 + f^{-1}(1 / x), &\text{if $x$ < 1} \\ \end{cases}\]

  • 實作時，我一開始用 C++ 寫了個分數 class，寫的落落長
    後來仔細思考一下，發覺 \(f^{-1}(x)\) 其實可以化簡

    \(f^{-1}(x) = \begin{cases} 1, &\text{if $x$ = 1} \\ 2^{x - 1}, &\text{if $x$ > 1 $\land$ $x$ $\in$ N} \\ 2^{\lfloor x \rfloor} \times f^{-1}(x - \lfloor x \rfloor), &\text{if $x$ > 1 $\land$ $x$ $\notin$ N} \\ 1 + f^{-1}(1 / x), &\text{if $x$ < 1} \\ \end{cases}\)

    並且發現，這函數遞迴的方式跟 gcd 差不多嘛！
    因此，其時間複雜度 = \(\gcd\) 的時間複雜度 = \(O(\log \min(a, b))\)
    使其 worst case 的測資為費式數列相鄰的兩項