8
給定各種貨幣對的數據集，如何有效計算數據集中未提供的對的隱含fx匯率？確定匯率的算法
例如，說我的數據庫/表看起來是這樣的（這個數據是捏造）：
GBP x USD = 1.5
USD x GBP = 0.64
GBP x EUR = 1.19
AUD x USD = 1.1
注意（英鎊，美元）= 1 /（美元，英鎊）！
我希望下面的結果：
print rate('GBP','USD')
> 1.5
print rate('USD','GBP')
> 0.64
print rate('GBP','EUR')
> 1.19
#now in the absence of an explicit pair, we imply one using the inverse
print rate('EUR','GBP')
> 0.84
這些都是簡單的情況下，它變得更有趣：
#this is the implied rate from (GBP,EUR) and (GBP,USD)
print rate('EUR','USD')
> 1.26
或更爲複雜的例子是找到使用3個最有效的翻譯或更多對：
print rate('EUR','AUD')
> 1.38
我認爲詳細的編程這個問題的一些方面。我可以想象有一個有效的或聰明的遞歸可以在這裏完成。唯一的要求是使用最少數量的配對來達到要求配對（這是爲了減少錯誤）。如果沒有給出明確的反轉，那麼反轉一對就不會付出代價。
動機
在理想的金融世界，貨幣市場是有效的。事實上，這是99％的事實。通常情況下，奇數貨幣對沒有被引用，或者它們很少被引用。如果存在明確的引用，我們必須在我們的任意計算中使用它。如果不是，我們必須暗示最精確的一對，儘可能多的小數位。此外，它們並不總是乘以1（實際上，它們從不乘以1）。這反映了市場上的買賣差價。因此，我們在雙向上保留儘可能多的配對，但希望能夠針對所有貨幣進行一般編碼。
我想我有一個體面的，蠻力的解決方案實施。它的工作原理，但我認爲這個問題很有趣，並想知道其他人是否認爲這很有趣/有挑戰性。我個人在Python中工作，但它比實現更像是一個練習，所以僞代碼是「足夠好」的。
這是ProLog中的一項非常簡單的任務:)。程序算法需要更多的思考。我的猜測是，你必須形成一個轉換樹，頂部節點是源貨幣，葉子 - 最後一個可能的貨幣，條件是每個貨幣只能出現一次。該算法然後將選擇獲得的最小合成匯率。 遞歸方法。 – AlexanderMP 2010-07-30 14:28:12