約瑟夫問題

故事

39個猶太人與Josephus以及他的朋友躲到一個洞里，決定寧愿死也不要被敵人抓到。于是決定了自殺方式，41個人圍成一圈，又第1個人開始報數(shù)，每報到第3個人就必須自殺。然后下一個重新報數(shù)，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不像遵從，Josephus讓朋友想假裝遵從，他將朋友與自己安排在第16個與第31個位置，結(jié)果逃過了這場死亡游戲。

約瑟夫自殺問題

約瑟夫環(huán)

約瑟夫環(huán)

• 第1輪 開始為0 循環(huán)為3 剔除為2
• 第2輪 開始為3 循環(huán)為3 剔除為5
• 第3輪 開始為6 循環(huán)為3 剔除為8
• 第4輪 開始為9 循環(huán)為3 剔除為1
• 第5輪 開始為3 循環(huán)為3 剔除為6
• ...

數(shù)學推導

有n個數(shù)，編號從0到n-1，從0開始數(shù)到m則剔除，下一位繼續(xù)從0開始數(shù)，依此類推只剩下最后一個，求最后那個的編號。

每剔除一個就重新開始，相當于減少了問題的規(guī)模，解n個規(guī)模為n、n-1、n-2,n-3...3,2,1。

假如第2輪（n-1規(guī)模）中剔除編號為x，此編號是第1輪剔除后從新從0開始編排的，可推導出，此數(shù)在第1輪人數(shù)為n時中的編號為 (x+m)%n。

n-2中剔除的數(shù)在n-1中的編號為 (x+m)%(n-1)
n-3中剔除的數(shù)在n-1中的編號為(x+m)%(n-2)
...

$n = 100;
$m = 3;
$s = 0;//表示從第0個開始數(shù)
for($i=2; $i<=$n; $i++){
 $x = ($x + $m) % $i;
}
$result = ($x+$s)%n;

約瑟夫環(huán)應用：猴子大王

一群猴子排成一圈，按1,2,3,...,n依此編號，從第1只開始數(shù)，數(shù)到第m只將它踢出圈。再從它的后面開始數(shù)，再數(shù)到第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。

假設(shè)此時某只猴子的新編號為i，原來的編號就是(i+a[1])%n。于是，便形成了一個遞歸問題。

假設(shè)知道子問題（n-1只個猴子）的解為x，那么原問題(n只猴子)的解就是(x+m%n)%N=(x+m)%n。問題的起始條件，若n=1那么結(jié)果就是1。

約瑟夫環(huán)：丟手帕

設(shè)編號為自然序號的1,2,3...n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數(shù)，數(shù)到m的那個人出列，他的下一位又從1開始報數(shù)，數(shù)到m的那個人又出列，以此類推，直到所有人出列為止，由此產(chǎn)生一個出隊編號的序列。

丟手帕問題

使用環(huán)形鏈表解決約瑟夫問題

可使用一個不帶頭節(jié)點的循環(huán)鏈表來處理約瑟夫問題，首先構(gòu)造一個含有n個節(jié)點的單循環(huán)鏈表，然后由k節(jié)點起從1開始計數(shù)，計數(shù)到m時，對應節(jié)點從鏈表中刪除，然后再從被刪除節(jié)點的下一個節(jié)點從1開始計數(shù)，直到最后一個節(jié)點從鏈表中刪除。

鏈表

鏈表，最靈活的數(shù)據(jù)結(jié)構(gòu)。鏈表是有序的列表，而在內(nèi)存中是分散存儲的。

鏈表是一種在邏輯上連續(xù)且有序的數(shù)據(jù)存儲結(jié)構(gòu)，而在物理存儲單元上是非連續(xù)且非有序的。

使用鏈表可解決類似約瑟夫問題、排序問題、搜索索引、廣義表...

鏈表的類型可分為

• 單向鏈表
• 雙向鏈表
• 單向循環(huán)鏈表
• 雙向循環(huán)鏈表
• 十字鏈表/有向圖

單向鏈表

單向鏈表又稱為單鏈表，是一個鏈式存儲結(jié)構(gòu)，擁有一個表頭head，除了最后一個節(jié)點外，所有節(jié)點都有后繼節(jié)點。

單向鏈表

單鏈表的每個節(jié)點都保存其數(shù)據(jù)域和后繼指針。

單向鏈表

案例：排行榜

內(nèi)存分區(qū)

一個程序運行時，內(nèi)存分成5個區(qū)域：棧區(qū)、堆區(qū)、全局區(qū)/靜態(tài)存儲區(qū)、常量存儲區(qū)、代碼區(qū)/自由存儲區(qū)。

• 棧區(qū)
  由編譯器需要時分配，不需要時自動清除的變量存儲區(qū)，其中存儲的變量通常是局變量、函數(shù)參數(shù)等。
• 堆區(qū)
  使用new分配的內(nèi)存塊，它們的釋放是由應用程序控制，而非編譯器控制。一般而言，一個new就會對應一個delete。如果程序員沒有釋放掉，在程序結(jié)束后，會由操作系統(tǒng)自動回收。
• 自由存儲區(qū)
  由malloc等分配的內(nèi)存塊，與堆區(qū)十分類似，不過它是用free來結(jié)束自己的生命的。
• 全局/靜態(tài)存儲區(qū)
  全局變量和靜態(tài)變量被分配到同一塊內(nèi)存中，C語言中全局變量又分為初始化和未初始化的，在C++中沒有這個區(qū)分，他們共同占用同一塊內(nèi)存區(qū)域。
• 常量存儲區(qū)
  比較特殊的存儲區(qū)，存放著不允許修改的常量。

PHP的內(nèi)存模型

內(nèi)存從邏輯上可分為4段，程序中不同的聲明存放在不同的內(nèi)存段中。

內(nèi)存段

• 數(shù)據(jù)段data segment
  又稱為初始化靜態(tài)段，用來存放程序中已被初始化且不為0的全局變量，如靜態(tài)變量和常量。
• 代碼段/文本段 code segment/text segment
  用于存放程序執(zhí)行代碼的內(nèi)存區(qū)域，如函數(shù)和方法。
• ?？臻g段
  存儲占用相同空間長度，且占用空間小的數(shù)據(jù)類型。如整形在內(nèi)存中占用的空間是等長的，都是64bit(4byte)。常有int、float、bool...
• 堆內(nèi)存
  數(shù)據(jù)長度不定長，且占用空間很大的數(shù)據(jù)類型的存儲區(qū)域。如 string、array、class...

?？臻g段是可以直接存取的，而堆內(nèi)存不可以直接存取。對于對象而言，是一種很大且占用不定長的數(shù)據(jù)類型，所以對象是存放在堆中。但對象名是存放在棧中的，因此通過對象名就可以訪問使用對象。

PHP的內(nèi)存管理

PHP的內(nèi)存管理是分層的，由上到下分為接口層、堆層、存儲層

PHP的內(nèi)存管理

• 接口層

接口層是PHP對外提供的可調(diào)用的方法，通過宏封裝了內(nèi)部實現(xiàn)。這些宏定義了一個高層次的接口，使得調(diào)用更加容易，它隔離了外部調(diào)用和PHP內(nèi)存管理的內(nèi)部實現(xiàn)，實現(xiàn)了一種松耦合關(guān)系。

• 堆層

在接口層下面是PHP內(nèi)存管理的核心實現(xiàn)，稱之為heap層。堆層控制整個PHP內(nèi)存管理的過程。

PHP中的內(nèi)存管理主要工作就是維護3個列表：小塊內(nèi)存列表free_buckets、大塊內(nèi)存列表large_free_buckets、剩余內(nèi)存列表rest_buckets。這里每個bucket也對應一定大小的內(nèi)存塊列表，這些列表都包含雙向鏈表的實現(xiàn)。

對于小塊內(nèi)存是最常用的，所以追求高性能。對于大塊內(nèi)存則追求的是穩(wěn)妥，盡量避免內(nèi)存浪費。對于小塊內(nèi)存，PHP引入了cache機制，ZendMM希望通過cache盡量做到一次定位就能查找分配。

• 存儲層

存儲層的作用是將內(nèi)存分配的方式對堆層透明化。

存儲層通常申請的內(nèi)存都比較大，這里申請的內(nèi)存大小并不是指storage層結(jié)構(gòu)所需要的大小，只是堆層通過調(diào)用存儲層的分配方法時，以大塊大塊的方式申請的內(nèi)存。

存儲層通過malloc()、mmap()等函數(shù)向系統(tǒng)真正的申請內(nèi)存，并通過free()函數(shù)釋放掉所申請的內(nèi)存。