Galex

Tag: Algorithm

约瑟夫环问题

约瑟夫环问题应该是都熟悉的,传说著名犹太历史学家夫拉维·约瑟夫在犹太罗马战争期间,约瑟夫和其他40名犹太反抗者被困在了罗马人包围的洞穴。这些犹太人宁可自杀也不愿当俘虏,于是决定围成一个圆圈,并沿着圆圈每隔两个人杀死一个,直到最后只剩两个人为止。约瑟夫和他的一个朋友不想自杀,于是他计算出他和他[......]

Read more

主定理的证明

算法导论其实已经给出了具体的证明步骤,但是还是有些省略,此文章是对主定理进行了完全的证明;

01

主定理的证明大致分为两个阶段:
  1. 假设n为b的整数次幂,如1,b,b^2,b^3….
  2. 不限定n的范围,n可以为任意整数;
首先我们先证明第一阶段,即n=b^i;
 [......]

Read more

Copyright © 2017 Galex

署名-非商业性使用-禁止演绎 3.0 | Creative Commons BY-NC-ND 3.0