84669 人學習
152542 人學習
20005 人學習
5487 人學習
7821 人學習
359900 人學習
3350 人學習
180660 人學習
48569 人學習
18603 人學習
40936 人學習
1549 人學習
1183 人學習
32909 人學習
碰到了一个关于元组的算法问题
请大家帮忙看看,能不能给个答案,或者解决思路也行.
谢谢!
三元组(a,b,c)标识a币种到b币种的汇率为c,反向亦成立。 输入一堆这样的三元组,再指定两个币种x y,问x->y的汇率是多少? 请编程实现,并给出时间、空间复杂度。 注意:x->y的汇率是唯一的。
光阴似箭催人老,日月如移越少年。
思路:三元組 -> 有向圖 -> 求任兩節點的路徑 -> 矩陣乘法或Floyd-Warshal。
例如取得的外匯牌價是:
第一行表示,每1元人民幣可以兌換0.116英鎊。每個三元組(c1, c2, r)对应两条带权重的边:c1 -> c2 weighted r和c2 -> c1 weighted 1/r。這些牌價實際上給出一個有向圖:
(c1, c2, r)
c1 -> c2 weighted r
c2 -> c1 weighted 1/r
這裡假設給出的三元組不會導出矛盾,且有向圖是聯通的(不會有折算不到的情況)。這個有向圖寫成帶權重的鄰接矩陣就是:
矩陣元素A[i,j]表示1单位i币种可以兑换多少单位的j幣種。矩陣中的零代表目前匯率未知。
A[i,j]
i
j
把矩陣A连乘可以逐步去除这些零元素。但是要把普通矩阵相乘中计算点积的加法替换成“取第一个大于零的数,若没有则为零”的操作。例如:(1,2,3).(0,3,2) = first_positive(1*0, 2*3, 3*2) = 6。
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^k
k-1
n
A^(n-1)
A^3:
A^3
觀察A^3的第一行,它是所有货币对人民币的比价。任两种货币的比价就是把它们对人民币的比价的商。所以其实一开始用A的第一行参加计算就好:A[1] * A * ... * A (最多n-1次)的第一行,它是所有貨幣對人民幣的比價。任兩種貨幣的比價就是把它們對人民幣的比價的商。所以其實一開始用A的第一行參加計算就好:A[1] * A * ... * A (最多n-1次),每次進行的是行向量和矩陣的乘法,直到所有行的元素非零結束。這個計算的複雜度是O(n³)。
A[1] * A * ... * A (最多n-1次)
調整求最短路徑演算法Floyd-Warshal中的遞推關係,也可以用於本題的匯率折算。 Floyd-Warshal的複雜度是Θ(n³)。所以用矩陣乘法可能會比較快一些。
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
兩種演算法都需要儲存匯率矩陣,所以的空間複雜度都是Θ(n²)。
如果是提供三元組數組,產生一個計算 x->y 匯率的方式的最優解: 有向圖最短路徑演算法
如果是每次提供不同的三元組數組,只需要取得一個結果就好: 有向圖尋路演算法
元組可以作為 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
上面的有些演算法寫得好複雜,寫個簡單的:
#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] = {'[field@learn]$./test_hello please input the two node: CNY GBP CNY->GBP 0.116000 [field@learn]$./test_hello please input the two node: GBP CNY CNY->GBP 0.116000 [field@learn]$ '}; for(i=0;i<npairs*3; i+= 3){ memset(tmp,'rrreee',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] = {'rrreee'}; char input1[8] = {'rrreee'}; scanf("%s%s",input0,input1); char data0[16] = {'rrreee'}; char data1[16] = {'rrreee'}; /*考虑正序和反序*/ 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 GBP CNY->GBP 0.116000 [field@learn]$./test_hello please input the two node: GBP CNY CNY->GBP 0.116000 [field@learn]$
測試結果如下:
這裡利用的是幣種名字的唯一性,兩個幣種拼接在一起必然也是唯一的。
思路:三元組 -> 有向圖 -> 求任兩節點的路徑 -> 矩陣乘法或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次)
的第一行,它是所有貨幣對人民幣的比價。任兩種貨幣的比價就是把它們對人民幣的比價的商。所以其實一開始用A
的第一行參加計算就好:A[1] * A * ... * A (最多n-1次)
,每次進行的是行向量和矩陣的乘法,直到所有行的元素非零結束。這個計算的複雜度是O(n³)。Floyd-Warshal
調整求最短路徑演算法Floyd-Warshal中的遞推關係,也可以用於本題的匯率折算。 Floyd-Warshal的複雜度是Θ(n³)。所以用矩陣乘法可能會比較快一些。
兩種演算法都需要儲存匯率矩陣,所以的空間複雜度都是Θ(n²)。
如果是提供三元組數組,產生一個計算 x->y 匯率的方式的最優解: 有向圖最短路徑演算法
如果是每次提供不同的三元組數組,只需要取得一個結果就好: 有向圖尋路演算法
元組可以作為 dict 的 key
上面的有些演算法寫得好複雜,寫個簡單的:
測試結果如下:
rrreee這裡利用的是幣種名字的唯一性,兩個幣種拼接在一起必然也是唯一的。