java - 已知外汇牌价折算汇率

问题描述

碰到了一个关于元组的算法问题

请大家帮忙看看,能不能给个答案,或者解决思路也行.

谢谢!

三元组(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。这些牌价实际上给出一个有向图：

这里假设给出的三元组不会导出矛盾，且有向图是联通的（不会有折算不到的情况）。这个有向图写成带权重的邻接矩阵就是：

矩阵元素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(n³)。

调整一下求最短路径算法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回答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]$

这里利用的是币种名字的唯一性，两个币种拼接在一起必然也是唯一的。