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

【考一考】汇率算法，号称算法强的可以来挑战一下^_^
汇率信息中有不同币种之间的汇率，要求从已知信息中求出给定币种直接的汇率。
将汇率信息存放在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#亦可。


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

[解决办法]
A B
A C
A D
A E
A F
...
A Z
这样会死么…………这样省事儿很多啊少年……
[解决办法]
我只能想到1楼类似的办法了。
[解决办法]

探讨

你说的思路任何不傻的人都能想到，但是你把它实现试一下？

[解决办法]
我在想，如何保证 A-B，和A-C-B的结果是一致的？如果能保证的话，也就没有最优不最优的换法了。1楼一个个查询下去就可以了。
[解决办法]
还有一种方法是一次性读出现有的汇率，填充游标链表。

[解决办法]

探讨

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

[解决办法]

探讨

引用:

我只能想到1楼类似的办法了。

想法非常简单，但是实现完全是另外一回事，就像上天一样，大致思路就是推力克服重力，这样就可以上天了，但是真的要上天的话，是简单的吗？

[解决办法]
8楼那个适合于汇率变化时间间隔长的情况。
而且不像1楼那个那么抽象。
[解决办法]
问题确实挺复杂，
一个是有可能有多条路径,源到目标得到一个汇率，目标到源有个汇率的倒数，每次查询都能得到两个汇率值。每次都要二叉树了。
二是还要考虑死循环，a-b,b-a，还要考虑推出机制，要记录下查询路径。
[解决办法]
不知道有没有更好的算法，不过我觉得这个更多的繁琐，还不是算法的问题吧，8楼矢量的算法也许会简单点。
[解决办法]

探讨

引用:

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

嘿嘿。。
足以让各位号称擅长算法的同学哑火。。。

[解决办法]

探讨

引用:

引用:

引用:

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

嘿嘿。。
足以让各位号称擅长算法的同学哑火。。。


真不至于的…………

[解决办法]
有好的不用，拿个烂的死的来问别人，这怎么算？ 1+N等于多少？ N随意，这够简单吧，你知道答案吗
[解决办法]
闲的慌
[解决办法]
有权图，币种为节点，汇率为权值，A->N的汇率肯定有多重汇率计算路线，根据权值可以求得最优汇率。
[解决办法]

探讨

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

[解决办法]
任意两种币种之间的汇率默认为1.0000，这个存在很大问题。

A-B：2
A-C：3

没有D，

现在换，到底是A-D是默认的1？ 还是A-B-D的2×1？ 还是A-C-D的3×1？
[解决办法]
提供一种思路：
首先，求出数据表中不同的SourceCurrency和不同的TargetCurrency之间的最小值N

SQL code

SELECT MIN(COUNT(DISTINCT([SourceCurrency])), COUNT(DISTINCT([TargetCurrency]))) AS [N]FROM [数据表]
[解决办法]
感觉这个题目有些地方不明确：
假如：
A->B, B->C,....X->D可以推出A->D
，但是同时存在
A->M, M->N,....X->D也可以推出A->D
那么那一条路径是正确的呢？
[解决办法]
探讨

引用:

任意两种币种之间的汇率默认为1.0000，这个存在很大问题。

A-B：2
A-C：3

没有D，

现在换，到底是A-D是默认的1？ 还是A-B-D的2×1？ 还是A-C-D的3×1？

这里的默认为1，是指最终求解不到结果时返回值为1，中间过程的币种间的汇率必须以提供的汇率为依据进行推算

[解决办法]
这可表示容易说明问题的概念，是业务逻辑错误，返回-1也比1好，否则，你的业务数据就废了。
[解决办法]
没接触，学习
[解决办法]
不错，又学到东西了，谢谢你！
[解决办法]
我来抛砖，正确与否概不负责（只要找出一个结果就可以）

C# code
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; }//标识是否搜索过    }
[解决办法]
如果有多种兑换方法，应该找出如何兑换换得最多才行。所以还是个最短路径问题，将兑换比例取log，转为路径的权值。因为存在负权，所以Dijkstra不能用了，需要用Floyd或SPFA之类的算法。抱歉，我也只能说思路，代码写不了。 
 
[解决办法]
啊哦，前几个月，刚做了一个WP7上的小应用，就是单位转换的。其实很简单，就是找个基准变量，然后所有单位都参照基准变量来设置……
[解决办法]
模拟退火？
[解决办法]
这个是时间与空间之间的取舍。如果要省时间，就把计算的结果保存在一个链表中，每一次需要计算的时候先从链表中扫一遍，如果有就不用计算了，否则计算一下，然后再把这个结果填到这个链表中。 

 

查看更多 下一篇