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这里利用的是币种名字的唯一性,两个币种拼接在一起必然也是唯一的。