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

Question

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

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

3. 谢谢!

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

注意：x->y的汇率是唯一的。

Answer 1

Idée : Triplet -> Graphique dirigé -> Trouver le chemin de deux nœuds quelconques -> Multiplication matricielle ou Floyd-Warshal.

Par exemple, le prix de change obtenu est :

La première ligne indique que chaque yuan peut être échangé contre 0,116 livre. Chaque triple (c1, c2, r) correspond à deux arêtes pondérées : c1 -> c2 weighted r et c2 -> c1 weighted 1/r. Ces citations donnent en fait un graphique orienté :

On suppose ici que le triplet donné ne conduira pas à des contradictions, et que le graphe orienté est connexe (il n'y aura pas d'incompréhension). Ce graphe orienté s'écrit sous forme de matrice de contiguïté pondérée :

L'élément matriciel A[i,j] représente le nombre d'unités de i devise pouvant être échangées contre 1 unité de j devise. Les zéros dans la matrice signifient que le taux de change actuel est inconnu.

Multiplication matricielle

Multiplier les matrices A permet de supprimer progressivement ces éléments nuls. Mais l'ajout du calcul du produit scalaire dans la multiplication matricielle ordinaire doit être remplacé par l'opération "obtenir le premier nombre supérieur à zéro, ou zéro sinon". Par exemple : (1,2,3).(0,3,2) = first_positive(1*0, 2*3, 3*2) = 6.

Utilisez "Multiplication du taux de change" pour calculer la puissance de A représente le tableau des taux de change converti au plus A^k pas, et le calcul continue jusqu'à ce qu'il n'y ait plus de zéro dans k-1. S'il y a A^k devises, jusqu'à n sera calculé. A^(n-1)

 : A^3

Observez la première ligne de

, c'est la comparaison des prix de toutes les devises par rapport au RMB. La comparaison de deux monnaies est le quotient de leur comparaison avec le RMB. Donc en fait, il suffit d'utiliser la première ligne de A^3 pour participer au calcul du début : A, à chaque fois le vecteur ligne et la matrice sont multipliés jusqu'à ce que tous les éléments de la ligne soient non nuls. La complexité de ce calcul est O(n³). A[1] * A * ... * A (最多n-1次)

Floyd-Warshal

Ajustez la relation de récursion dans l'algorithme du chemin le plus court

Floyd-Warshal et elle peut également être utilisée pour la conversion du taux de change dans cette question. La complexité de Floyd-Warshal est Θ(n³). La multiplication matricielle pourrait donc être plus rapide.

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

Les deux algorithmes doivent stocker la matrice du taux de change, donc la complexité spatiale est Θ(n²).

Answer 2

Si un tableau de triplets est fourni, générez une solution optimale pour calculer le taux de change x->y : algorithme de plus court chemin à graphique dirigé

Si vous fournissez un triple tableau différent à chaque fois, vous n'avez besoin d'obtenir qu'un seul résultat : un algorithme de recherche de chemin à graphe orienté

Answer 3

Les tuples peuvent être utilisés comme clés de dict

>>> 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

Answer 4

Certains des algorithmes ci-dessus sont très compliqués à écrire. Écrivons-en un simple :

#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;
}

Les résultats des tests sont les suivants :

rrreee

Ce qui est utilisé ici, c'est le caractère unique du nom de la devise. Les deux devises doivent être uniques lorsqu'elles sont associées.