解N匹马、M个赛道中，求最快Y匹马需要的场次X

无意中看到很多人讨论一个算法问题，自己也来做一下。
原题地址：http://www.iteye.com/topic/255969?page=1

N匹马、M个赛道中，求最快Y匹马需要的场次X。

解：
该问题属于递归问题，求解步骤为3大步骤：
1.确定N匹马中跑的最快的马。
2.将步骤1确定的最快的马去除，对剩下的N-1匹马执行步骤1。
3.确定第Y匹最快的马时，全部执行的场次为X。（此时步骤1执行Y次，步骤2执行Y-1次）
步骤1可以分为2个小步骤：
1.1安排每匹马进行比赛：场次C=*(N/M)，其中*(U)表示对U无条件进位取整。
1.2再安排步骤1.1中每场第一的C匹马执行1.1直到C==1，最后一场的第一既为N匹马中最快的马。
步骤分解完毕，在非并行情况下，伪代码如下：

N;M;Y;X=0;
for(int count=0;count<Y;count=count+1){
  int C=N;
  for(int i=0;*(C/M)!=1;i=+1){
    X+=*(C/M);
    C=*(C/M);
  }
  X=X+1;
  N=N-1;
}
X;

在Z场并行时，可以对上面的求解*(C/M)进行并行优化。

评论

1 楼 bubble 2008-11-07  

以上是最笨的方法，当然对步骤1.2中的最后一场的结果可以进行优化，不过用计算机做就没这个必要了，哈哈