問題描述

碰到了一個關于元組的算法問題

請大家?guī)兔纯?能不能給個答案,或者解決思路也行.

謝謝!

三元組(a,b,c)標識a幣種到b幣種的匯率為c，反向亦成立。輸入一堆這樣的三元組，再指定兩個幣種x y，問x->y的匯率是多少？請編程實現，并給出時間、空間復雜度。注意：x->y的匯率是唯一的。

問題解答

思路：三元組 -> 有向圖 -> 求任兩節(jié)點的路徑 -> 矩陣乘法或Floyd-Warshal。

比如獲取的外匯牌價是：

第一行表示，每1元人民幣可以兌換0.116英鎊。每個三元組(c1, c2, r)對應兩條帶權重的邊：c1 -> c2 weighted r和c2 -> c1 weighted 1/r。這些牌價實際上給出一個有向圖：

這里假設給出的三元組不會導出矛盾，且有向圖是聯通的（不會有折算不到的情況）。這個有向圖寫成帶權重的鄰接矩陣就是：

矩陣元素A[i,j]表示1單位i幣種可以兌換多少單位的j幣種。矩陣中的零代表目前匯率未知。

把矩陣A連乘可以逐步去除這些零元素。但是要把普通矩陣相乘中計算點積的加法替換成“取第一個大于零的數，若沒有則為零”的操作。例如：(1,2,3).(0,3,2) = first_positive(1*0, 2*3, 3*2) = 6。

用“匯率乘法”計算A的乘方，A^k表示最多經過k-1步折算得到的匯率表，一直算到A^k中沒有零停止。如果有n種貨幣，最多計算到A^(n-1)。

A^3：

觀察A^3的第一行，它是所有貨幣對人民幣的比價。任兩種貨幣的比價就是把它們對人民幣的比價的商。所以其實一開始用A的第一行參加計算就好：A[1] * A * ... * A (最多n-1次)，每次進行的是行向量和矩陣的乘法，直到行的所有元素非零結束。這個計算的復雜度是O(n3)。

調整一下求最短路徑算法Floyd-Warshal中的遞推關系，也可以用于本題的匯率折算。Floyd-Warshal的復雜度是Θ(n3)。所以用矩陣乘法可能會更快一些。

for k from 1 to rows(A) for i from 1 to rows(A)for j from 1 to rows(A) if A[i][j] = 0 then // 貨幣 i, j 通過貨幣 k 折算 A[i][j] <- A[i][k] * A[k][j] end if

兩種算法都需要存儲匯率矩陣，所以的空間復雜度都是Θ(n2)。

如果是提供三元組數組，生成一個計算 x->y 匯率的方式的最優(yōu)解: 有向圖最短路徑算法

如果是每次提供不同的三元組數組，只需要獲取一個結果就好: 有向圖尋路算法

元組可以作為 dict 的 key

>>> ls = [(’人民幣’, ’美元’), (’人民幣’, ’歐元’), (’人民幣’, ’英鎊’)]>>> 匯率表 = dict(zip(ls,(6.,7.,8.))){(’人民幣’, ’美元’): 6.0, (’人民幣’, ’英鎊’): 8.0, (’人民幣’, ’歐元’): 7.0}>>> import pprint>>> pprint.pprint(匯率表,width=10){(’人民幣’, ’歐元’): 7.0, (’人民幣’, ’美元’): 6.0, (’人民幣’, ’英鎊’): 8.0}>>> 匯率表[(’人民幣’, ’美元’)]6.0回答4：

上面的有些算法寫得好復雜，寫個簡單的：

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <unistd.h>typedef struct node{ char *str; /*拼接后的字符串*/ float value; /*匯率值*/}node_t;int main(int argc, char *argv[]){ /*用戶輸入的一序列匯率對應關系*/ static char const *buff[] = {'CNY','GBP','0.116','CNY','RUB','8.406','CNY','AUD','0.184','JPY','RUB','0.5072','USD','EUR', '0.9456'};int npairs = sizeof(buff)/sizeof(buff[0])/3; node_t * buf = calloc(1,npairs*sizeof(node_t)); if(NULL == buf){ printf('calloc is null !n');return(-1); } int i = 0; int j = 0; int len = 0; char tmp[16] = {’0’}; for(i=0;i<npairs*3; i+= 3){memset(tmp,’0’,sizeof(tmp));/*把兩個字符串進行拼接*/snprintf(tmp,16,'%s%s',buff[i],buff[i+1]);len = strlen(tmp);buf[j].str = calloc(1,sizeof(char)*(len+1));if(NULL != buf[j].str){ memmove(buf[j].str,tmp,len); buf[j].value = atof(buff[i+2]); j += 1;} } printf('please input the two node:n'); char input0[8] = {’0’}; char input1[8] = {’0’};scanf('%s%s',input0,input1); char data0[16] = {’0’}; char data1[16] = {’0’}; /*考慮正序和反序*/ snprintf(data0,16,'%s%s',input0,input1); snprintf(data1,16,'%s%s',input1,input0); for(i=0;i<j;++i){/*輪訓匹配*/if((0==strcmp(buf[i].str,data0))){ printf('%s->%s %f n',input0,input1,buf[i].value); break;}if( 0==strcmp(buf[i].str,data1) ){ printf('%s->%s %f n',input1,input0,buf[i].value); break;} } if(i==j){ printf('can not find the pair n');} /* add the free*/ return 0;}

測試結果如下：

[field@learn]$./test_hello please input the two node:CNY GBPCNY->GBP 0.116000 [field@learn]$./test_hello please input the two node:GBP CNYCNY->GBP 0.116000 [field@learn]$

這里利用的是幣種名字的唯一性，兩個幣種拼接在一起必然也是唯一的。