求教一个算法解决方法
求教一个算法
一个方阵R， R[i][i] 为1 其他的为非0 浮点数 。设计一个算法求出所有的序列 i1,i2,i3.....ik 使得
R[i1][i2]*R[i1][i3]*......*R[ik][i1]>1
------解决方案--------------------
不知道别人是怎么套汇的,不过觉得蛮有意思.
下面是我的一点想法.
设有N种货币(N>1),则符合条件的正确序列中间货币个数为[1,n-1].只考虑一次出现.
如何排列这[1,n-1]个中间货币是算法的关键.
分解如下:(^表示次方)
中间货币为n-1个,即全部货种除开目标货币外全部参与兑换,组合数为(n-1)^(n-1),即若有10种货币组合数达到4亿.
中间货币为n-2个,即全部货币除开目标货币外,踢出一种货币参与兑换,组合数为(n-1)*(n-2)^(n-2),即若有10种货币组合数达到1.4亿.
中间货币为n-3个,即全部货币除开目标货币外,踢出两种货币参与兑换,组合数为(n-1)*(n-2)/2*(n-3)^(n-3),即若有10种货币货币组合数达到3百万.
...
中间货币为一个,只取一种货币参与兑换,组合数为n-1,即若有10种货币货币组合数达到9.
穷举法虽然笨,但是思路清晰,可以作优化,但是要清楚其中的逻辑关系.
简单来讲,这个算法主要是踢出不参与兑换的货币,然后全排列参与兑换的货币,这就可以了
一个方阵R， R[i][i] 为1 其他的为非0 浮点数 。设计一个算法求出所有的序列 i1,i2,i3.....ik 使得
R[i1][i2]*R[i1][i3]*......*R[ik][i1]>1
------解决方案--------------------
不知道别人是怎么套汇的,不过觉得蛮有意思.
下面是我的一点想法.
设有N种货币(N>1),则符合条件的正确序列中间货币个数为[1,n-1].只考虑一次出现.
如何排列这[1,n-1]个中间货币是算法的关键.
分解如下:(^表示次方)
中间货币为n-1个,即全部货种除开目标货币外全部参与兑换,组合数为(n-1)^(n-1),即若有10种货币组合数达到4亿.
中间货币为n-2个,即全部货币除开目标货币外,踢出一种货币参与兑换,组合数为(n-1)*(n-2)^(n-2),即若有10种货币组合数达到1.4亿.
中间货币为n-3个,即全部货币除开目标货币外,踢出两种货币参与兑换,组合数为(n-1)*(n-2)/2*(n-3)^(n-3),即若有10种货币货币组合数达到3百万.
...
中间货币为一个,只取一种货币参与兑换,组合数为n-1,即若有10种货币货币组合数达到9.
穷举法虽然笨,但是思路清晰,可以作优化,但是要清楚其中的逻辑关系.
简单来讲,这个算法主要是踢出不参与兑换的货币,然后全排列参与兑换的货币,这就可以了