瑞の資訊備忘錄

一、目的：近來使用電腦在金融企業進行爭議的交易程序即是利用極小的價格波動來進行獲利已經被

             許多華爾街公司所禁止。計算機程式倫理是一個新興的領域並且包含許多棘手的問題。

             (連結UVa online原文題庫)

 

二、問題說明：

     套匯是指將一個國家的貨幣透過與其他國貨幣之間極小的差異進行交易並使其獲得利益。

     因此如何寫一個程式根據給定的交易表並依照上述的規則，計算出可獲得利益的套匯交易流程。

     例如：  1美金等於0.7英鎊 1英鎊等於9.5法朗 1法朗等於0.16美元

              1 x 0.7 x 0.95 x 0.16 = 1.064  - 1 = .064 (profit)

 

三、輸入與輸出說明：

      在輸入資料時首先指定貨幣的數量(n)接著依序輸入各貨幣對其他(n-1)貨幣的匯率值。

      矩陣的對角資料表示第 i 種貨幣的對換單位預設為1.0且不包含在輸入資料中。輸出套

      匯過程時每個數值之間間隔一個空白。

      整個套匯交易有下列限制：

      1、以最少交易次數為主，只要獲利大於0.01即可結束並輸出交易流程。

      2、當輸入的交易表無套匯可獲利大於0.01時則輸出no arbitrage sequence exists。

      3、任何的貨幣都可當起始貨幣，但最後套匯結算的貨幣必須與起始貨幣相同。    

     EX:  Sample Input                                Sample Output

           3                                                    1 2 1    

           1.2 .89                          =>             1 2 4 1

           .88 5.1                                            no arbitrage sequenc exists

           1.1 0.15

           4

           3.1 0.0023 0.35

           0.21 0.00353 8.13

           200 180.559  10.339

           2.11 0.089 0.06111

           2

           2.0

           0.45

 

四、演算法說明：

該問題類似求圖形理論中最短路徑的問題，由於題目是求A貨幣轉換至其他貨幣後再換回A貨幣的

        程過，因此該問題適合使用弗洛伊德算法(Floyd-Warshall Algorithm)來解決。

4-1、建立三個arbitrage Matrix分別用來表示三種不同狀能的arbitrage資料：

4-1.1、輸入時的原始Arbitrage資料。

                4-1.2、每個貨幣經過(N-1)次的貨幣交換後的Arbitrage資料。 

                4-1.3、每個貨幣在第N次交換後的Arbitrage資料。

4-2、建立一個convert Matrix用來表示任兩個貨幣之間是否存在第三方貨幣可讓其匯率值增加。

        4-3、計算任兩個貨幣間的匯率在經過其他貨幣交換後其值是否大於原先兩者貨幣的匯率值；

         若是則儲存新的匯率值並記錄交換的其第三方的貨幣種類。

4-4、判斷是否有任何的貨幣交換回原始貨幣時其獲利大於0.01。

 

Run time of UVa online web : 0.028 ~ 0.032 sec

Download :   UVa104_Arbitrage.tar.gz

Result：