玩蛇网提供最新Python编程技术信息以及Python资源下载!

python折算汇率计算的小问题

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

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

  3. 谢谢!

三元组(a,b,c)标识a币种到b币种的汇率为c,反向亦成立。
输入一堆这样的三元组,再指定两个币种x y,问x->y的汇率是多少?
请编程实现,并给出时间、空间复杂度。

注意: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

如果是提供三元组数组,生成一个计算 x->y 汇率的方式的最优解: 有向图最短路径算法

如果是每次提供不同的三元组数组,只需要获取一个结果就好: 有向图寻路算法

上面的有些算法写得好复杂,写个简单的:

#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 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 rc2 -> 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中的递推关系,也可以用于本题的汇率折算。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²)。

玩蛇网文章,转载请注明出处和文章网址:https://www.iplaypy.com/wenda/wd13908.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年05月31日 - 11时19分25秒 发布自玩蛇网

您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容
我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules