PHP算法

约瑟夫问题

故事

39个犹太人与Josephus以及他的朋友躲到一个洞里，决定宁愿死也不要被敌人抓到。于是决定了自杀方式，41个人围成一圈，又第1个人开始报数，每报到第3个人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不像遵从，Josephus让朋友想假装遵从，他将朋友与自己安排在第16个与第31个位置，结果逃过了这场死亡游戏。

约瑟夫自杀问题

约瑟夫环

约瑟夫环

• 第1轮 开始为0 循环为3 剔除为2
• 第2轮 开始为3 循环为3 剔除为5
• 第3轮 开始为6 循环为3 剔除为8
• 第4轮 开始为9 循环为3 剔除为1
• 第5轮 开始为3 循环为3 剔除为6
• ...

数学推导

有n个数，编号从0到n-1，从0开始数到m则剔除，下一位继续从0开始数，依此类推只剩下最后一个，求最后那个的编号。

每剔除一个就重新开始，相当于减少了问题的规模，解n个规模为n、n-1、n-2,n-3...3,2,1。

假如第2轮（n-1规模）中剔除编号为x，此编号是第1轮剔除后从新从0开始编排的，可推导出，此数在第1轮人数为n时中的编号为 (x+m)%n。

n-2中剔除的数在n-1中的编号为 (x+m)%(n-1)
n-3中剔除的数在n-1中的编号为(x+m)%(n-2)
...

$n = 100;
$m = 3;
$s = 0;//表示从第0个开始数
for($i=2; $i<=$n; $i++){
 $x = ($x + $m) % $i;
}
$result = ($x+$s)%n;

约瑟夫环应用：猴子大王

一群猴子排成一圈，按1,2,3,...,n依此编号，从第1只开始数，数到第m只将它踢出圈。再从它的后面开始数，再数到第m只，再把它踢出去...直到最后剩下的一直猴子，那只猴子就叫大王。

// 使用线性表求解约瑟夫
function josephus($n, $m){
  $result = 0;
  for($i=2; $i<=$n; $i++){
    $result = ($result + $m) % $i;
  }
  return $result + 1;
}

每只猴子出列后，剩下的猴子又组成另一个子问题。只是它们的编号变化了。第1个出列的猴子肯定是arr[1] = m%n。

踢出第1只猴子后剩余的猴子是arr[1]+1、arr[1]+2、arr[1]+3,....,n,1,2,3,...,arr[1]-2、arr[1]-1，对应新的编号为1,2,3,...,n-1。

假设此时某只猴子的新编号为i，原来的编号就是(i+a[1])%n。于是，便形成了一个递归问题。

假设知道子问题（n-1只个猴子）的解为x，那么原问题(n只猴子)的解就是(x+m%n)%N=(x+m)%n。问题的起始条件，若n=1那么结果就是1。

约瑟夫环：丢手帕

设编号为自然序号的1,2,3...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。

丢手帕问题

使用环形链表解决约瑟夫问题

可使用一个不带头节点的循环链表来处理约瑟夫问题，首先构造一个含有n个节点的单循环链表，然后由k节点起从1开始计数，计数到m时，对应节点从链表中删除，然后再从被删除节点的下一个节点从1开始计数，直到最后一个节点从链表中删除。

链表

链表，最灵活的数据结构。链表是有序的列表，而在内存中是分散存储的。

链表是一种在逻辑上连续且有序的数据存储结构，而在物理存储单元上是非连续且非有序的。

使用链表可解决类似约瑟夫问题、排序问题、搜索索引、广义表...

链表的类型可分为

• 单向链表
• 双向链表
• 单向循环链表
• 双向循环链表
• 十字链表/有向图

单向链表

单向链表又称为单链表，是一个链式存储结构，拥有一个表头head，除了最后一个节点外，所有节点都有后继节点。

单向链表

单链表的每个节点都保存其数据域和后继指针。

单向链表

案例：排行榜

内存分区

一个程序运行时，内存分成5个区域：栈区、堆区、全局区/静态存储区、常量存储区、代码区/自由存储区。

• 栈区
  由编译器需要时分配，不需要时自动清除的变量存储区，其中存储的变量通常是局变量、函数参数等。
• 堆区
  使用new分配的内存块，它们的释放是由应用程序控制，而非编译器控制。一般而言，一个new就会对应一个delete。如果程序员没有释放掉，在程序结束后，会由操作系统自动回收。
• 自由存储区
  由malloc等分配的内存块，与堆区十分类似，不过它是用free来结束自己的生命的。
• 全局/静态存储区
  全局变量和静态变量被分配到同一块内存中，C语言中全局变量又分为初始化和未初始化的，在C++中没有这个区分，他们共同占用同一块内存区域。
• 常量存储区
  比较特殊的存储区，存放着不允许修改的常量。

PHP的内存模型

内存从逻辑上可分为4段，程序中不同的声明存放在不同的内存段中。

内存段

• 数据段data segment
  又称为初始化静态段，用来存放程序中已被初始化且不为0的全局变量，如静态变量和常量。
• 代码段/文本段 code segment/text segment
  用于存放程序执行代码的内存区域，如函数和方法。
• 栈空间段
  存储占用相同空间长度，且占用空间小的数据类型。如整形在内存中占用的空间是等长的，都是64bit(4byte)。常有int、float、bool...
• 堆内存
  数据长度不定长，且占用空间很大的数据类型的存储区域。如 string、array、class...

栈空间段是可以直接存取的，而堆内存不可以直接存取。对于对象而言，是一种很大且占用不定长的数据类型，所以对象是存放在堆中。但对象名是存放在栈中的，因此通过对象名就可以访问使用对象。

PHP的内存管理

PHP的内存管理是分层的，由上到下分为接口层、堆层、存储层

PHP的内存管理

• 接口层

接口层是PHP对外提供的可调用的方法，通过宏封装了内部实现。这些宏定义了一个高层次的接口，使得调用更加容易，它隔离了外部调用和PHP内存管理的内部实现，实现了一种松耦合关系。

• 堆层

在接口层下面是PHP内存管理的核心实现，称之为heap层。堆层控制整个PHP内存管理的过程。

PHP中的内存管理主要工作就是维护3个列表：小块内存列表free_buckets、大块内存列表large_free_buckets、剩余内存列表rest_buckets。这里每个bucket也对应一定大小的内存块列表，这些列表都包含双向链表的实现。

对于小块内存是最常用的，所以追求高性能。对于大块内存则追求的是稳妥，尽量避免内存浪费。对于小块内存，PHP引入了cache机制，ZendMM希望通过cache尽量做到一次定位就能查找分配。

• 存储层

存储层的作用是将内存分配的方式对堆层透明化。

存储层通常申请的内存都比较大，这里申请的内存大小并不是指storage层结构所需要的大小，只是堆层通过调用存储层的分配方法时，以大块大块的方式申请的内存。

存储层通过malloc()、mmap()等函数向系统真正的申请内存，并通过free()函数释放掉所申请的内存。