b537 - 分數運算-1

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個分數 a/b，要求找出 k 值，使得 f(k) = a/b。其中 f(1) = 1，對於 k >= 2，若 k 為偶數則 f(k) = 1 + f(k/2)，k 為奇數則 f(k) = 1/f(k-1)。輸入有多組測試資料，每組包含兩個正整數 a 和 b，輸出對應的 k 值。

解題思路

題目定義了一個遞迴函數 f(k)。當 k 為偶數時，f(k) 的值取決於 f(k/2)；當 k 為奇數時，f(k) 的值是 f(k-1) 的倒數。題目要求我們找到 k，使得 f(k) 等於給定的分數 a/b。

程式碼使用遞迴函數 getK(a, b) 來計算 k 值。函數首先檢查 b 是否小於 a。如果是，則計算 shift = a / b，並遞迴地計算 getK(b, a)，然後將結果加上 1，並左移 shift 位。如果 b 不小於 a，則檢查 a 是否等於 b。如果是，則返回 1。否則，遞迴地計算 getK(b, a) 並加上 1。

這個遞迴函數有效地模擬了 f(k) 的計算過程，並通過反向推導來找到對應的 k 值。

複雜度分析

• 時間複雜度: O(log(max(a, b)))
• 空間複雜度: O(log(max(a, b)))

程式碼

#include <stdio.h>
long long getK(int a, int b){
    if (b < a){
        int shift = a / b;
        a %= b;
        return a ? (getK(b, a) + 1) << shift : 1LL << (shift - 1);
    }
    return a == b ? 1 : getK(b, a) + 1;
}
int main(){
    int a, b;
    while (scanf(" %d %d", &a, &b) == 2)
        printf("%lld\n", getK(a, b));
    return 0;
}