【考一考】汇率算法，号称算法强的可以来挑战一下^_^

Question

汇率信息中有不同币种之间的汇率，要求从已知信息中求出给定币种直接的汇率。
将汇率信息存放在sql server数据库中，结构如下：
SourceCurrency TargetCurrency Rate
A B 1.0000
G H 2.4454
H C 8.0000
M N 4.0000
J H 10.0000
……//任意多的汇率信息
B M 7.2222
X Y 8.9999求货币A对货币N的汇率（任意两种币种之间的汇率默认为1.0000），用sql作答，用c#亦可。

Answer 1

1. 首先，这数据设计的啊……欸…… 
2. A B有 找B相关， B x有 找X相关，如果是X B，就用汇率倒数……直到找到 X N相关。

Answer 2

A B
A C
A D
A E
A F
...
A Z
这样会死么…………这样省事儿很多啊少年……

Answer 3

我在想，如何保证 A-B，和A-C-B的结果是一致的？如果能保证的话，也就没有最优不最优的换法了。1楼一个个查询下去就可以了。

Answer 4

哎呀……真没那么难的。
如果感觉这种随时找太难且汇率不会总变化，可以看8楼那个。想找到X到Y的汇率 只需要将X设置为基本值1.0000，根据矢量方向计算汇率。

Answer 5

问题确实挺复杂，
一个是有可能有多条路径,源到目标得到一个汇率，目标到源有个汇率的倒数，每次查询都能得到两个汇率值。每次都要二叉树了。
二是还要考虑死循环，a-b,b-a，还要考虑推出机制，要记录下查询路径。

Answer 6

求解问题的过程和细节当然是算法啊，你所说的“算法”只是一个大致的思路，大致思路非常简单，基于简单的数学比率的传递：
A:B B:C C:D -> A:D
你说算法不难，实现一下咯？？？

Answer 7

有权图，币种为节点，汇率为权值，A->N的汇率肯定有多重汇率计算路线，根据权值可以求得最优汇率。

Answer 8

任意两种币种之间的汇率默认为1.0000，这个存在很大问题。A-B：2
A-C：3没有D，现在换，到底是A-D是默认的1？ 还是A-B-D的2×1？ 还是A-C-D的3×1？

Answer 9

提供一种思路：
首先，求出数据表中不同的SourceCurrency和不同的TargetCurrency之间的最小值NSELECT MIN(COUNT(DISTINCT([SourceCurrency])), COUNT(DISTINCT([TargetCurrency]))) AS [N]
FROM [数据表]然后，从0到N，逐渐增加条件查询：
第1次SELECT
     T0.[SourceCurrency] AS C0
     , T0.[TargetCurrency] AS C1, T0.[Rate] AS R1
FROM [数据表] T0
WHERE T0.[SourceCurrency]='A' AND T0.[TargetCurrency]='N'/* 0 row(s) affected */第2次SELECT
     T0.[SourceCurrency] AS C0
     , T0.[TargetCurrency] AS C1, T0.[Rate] AS R1
     , T1.[TargetCurrency] AS C2, T1.[Rate] AS R2
FROM [数据表] T0
INNER JOIN [数据表] T1 ON T1.[SourceCurrency]=T0.[TargetCurrency]
WHERE T0.[SourceCurrency]='A' AND T1.[TargetCurrency]='N'/* 0 row(s) affected */第3次SELECT
     T0.[SourceCurrency] AS C0
     , T0.[TargetCurrency] AS C1, T0.[Rate] AS R1
     , T1.[TargetCurrency] AS C2, T1.[Rate] AS R2
     , T2.[TargetCurrency] AS C3, T2.[Rate] AS R3
FROM [Rate] T0
INNER JOIN [Rate] T1 ON T1.[SourceCurrency]=T0.[TargetCurrency]
INNER JOIN [Rate] T2 ON T2.[SourceCurrency]=T1.[TargetCurrency]
WHERE T0.[SourceCurrency]='A' AND T2.[TargetCurrency]='N'/* 1 row(s) affected */根据结果
A-B:1.0000
B-M:7.2222
M-N:4.0000
就可以得到A-N。如果到第N次还得不到结果，说明从这张表中查不到了。 

Answer 10

感觉这个题目有些地方不明确：
假如：
A->B, B->C,....X->D可以推出A->D
，但是同时存在
A->M, M->N,....X->D也可以推出A->D
那么那一条路径是正确的呢？

Answer 11

那你说的默认为1，不是无意义的条件吗，就是误导，直接说找不到提示不就可以了
而且
A-D 是默认 1
C-D 也是默认 1
但A-C 确是明确的3 
这不是很明显的矛盾吗？

Answer 12

可能是我没说清楚吧。。这里的默认为1，是指最终求解不到结果时返回值为1，中间过程的币种间的汇率必须以提供的汇率为依据进行推算在找不到是返回1是基于业务考虑的，就算法本身而言找不到时返回null比较容易说明问题，至于业务方面可以在调用算法时将null转换为1

Answer 13

我来抛砖，正确与否概不负责（只要找出一个结果就可以）
public class process
    {
        public static void get()
        {
            List<rate> lst = new List<rate>();
            lst.Add(new rate() { From = "A", To = "B", ratio = 1.5, tag = false });
            lst.Add(new rate() { From = "G", To = "H", ratio = 1.5, tag = false });
            lst.Add(new rate() { From = "H", To = "C", ratio = 1.5, tag = false });
            lst.Add(new rate() { From = "M", To = "N", ratio = 1.5, tag = false });
            lst.Add(new rate() { From = "J", To = "H", ratio = 1.5, tag = false });
            lst.Add(new rate() { From = "B", To = "M", ratio = 1.5, tag = false });
            lst.Add(new rate() { From = "B", To = "A", ratio = 1.5, tag = false });            string strFrom = "B";
            string strTo = "G";            if (!Search(strFrom, strTo, lst, 1.0))
            { Console.WriteLine("Match not founded"); }        }        public static bool Search(string strFrom, string strTo, List<rate> lst, double dTemp)
        {
            var lst1 = lst.Where(rat => rat.From.Equals(strFrom) && !rat.tag).ToList();
            foreach (rate ratItem in lst1)
            {
                ratItem.tag = true;
                if (ratItem.To.Equals(strTo))
                {
                    double dBl = dTemp * ratItem.ratio;
                    Console.WriteLine("rate:{0}", dBl);
                    return true;
                }
                else
                {
                    if (Search(ratItem.To, strTo, lst, dTemp * ratItem.ratio))
                        return true;
                }
            }            var lst2 = lst.Where(rat => rat.To.Equals(strFrom) && !rat.tag).ToList();
            foreach (rate ratItem in lst2)
            {
                ratItem.tag = true;
                if (ratItem.From.Equals(strTo))
                {
                    double dBl = dTemp / ratItem.ratio;
                    Console.WriteLine("rate:{0}", dBl);
                    return true;
                }
                else
                {
                    if (Search(ratItem.From, strTo, lst, dTemp * ratItem.ratio))
                        return true;
                }
            }
            return false;        }
    }    public class rate
    {
        public string From { get; set; }
        public string To { get; set; }
        public double ratio { get; set; }
        public bool tag { get; set; }//标识是否搜索过
    }

Answer 14

如果有多种兑换方法，应该找出如何兑换换得最多才行。所以还是个最短路径问题，将兑换比例取log，转为路径的权值。因为存在负权，所以Dijkstra不能用了，需要用Floyd或SPFA之类的算法。抱歉，我也只能说思路，代码写不了。

Answer 15

男士程序员长时间接触电脑，要保护自己护肤。
本店新开张: <a href="http://lovezeng520.taobao.com">http://lovezeng520.taobao.com</a>

Answer 16

1. A->B
2. B->A 倒數
3. A->C->B
4. B->C->A 倒數