十二 03

约瑟夫环数学算法的优化(转)

问题描述:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列,求最后一个出列人的编号。

递归的力量:优化到O(N)

在Donald E. Knuth的《

……阅读全文

01

扩展欧几里德算法

欧几里德算法找gcd已被我们所熟知,但刚看到扩展欧几里德算法的时候的确让我昏了一下,google,mathworld,wiki,baidu各给出了不同的说明,更是有多种多样的算法实现。

该算法在密码学中有非常重要的地位,因为很多算法都要用到乘法反元素,而它是找反元素最高效率的算法,无论两个数有……阅读全文

13

最短路径 之 SPFA算法

求最短路径的算法有许多种,除了排序外,恐怕是OI界中解决同一类问题算法最多的了。最熟悉的无疑是Dijkstra,接着是Bellman-Ford,它们都可以求出由一个源点向其他各点的最短路径;如果我们想要求出每一对顶点之间的最短路径的话,还可以用Floyd-Warshall。

SPFA是这篇日志……阅读全文

16

支援救灾

支援救灾2008年5月12日14时28分,四川省发生强烈地震,震中位于阿坝州汶川县,地震造成了严重的生命和财产损失。中国人民解放军某部接上级命令,组织部分官兵,携带重要的救灾物品,尽快赶往灾区支援救灾。第一批赶赴灾区的官兵共有N人,每人都要先到军备库领取需携带的救灾物品,然后整装打包,再整队集合发出……阅读全文