約瑟夫問題
故事
39個猶太人與Josephus以及他的朋友躲到一個洞里，決定寧愿死也不要被敵人抓到幻碱。于是決定了自殺方式狂秦，41個人圍成一圈，又第1個人開始報(bào)數(shù)治专，每報(bào)到第3個人就必須自殺卖陵。然后下一個重新報(bào)數(shù)，直到所有人都自殺身亡為止张峰。然而Josephus和他的朋友并不像遵從泪蔫，Josephus讓朋友想假裝遵從，他將朋友與自己安排在第16個與第31個位置喘批，結(jié)果逃過了這場死亡游戲撩荣。
約瑟夫環(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ù)學(xué)推導(dǎo)
有n個數(shù)铣揉，編號從0到n-1，從0開始數(shù)到m則剔除餐曹，下一位繼續(xù)從0開始數(shù)逛拱，依此類推只剩下最后一個，求最后那個的編號台猴。
每剔除一個就重新開始朽合，相當(dāng)于減少了問題的規(guī)模，解n個規(guī)模為n饱狂、n-1曹步、n-2,n-3...3,2,1。
假如第2輪（n-1規(guī)模）中剔除編號為x休讳，此編號是第1輪剔除后從新從0開始編排的箭窜，可推導(dǎo)出，此數(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)應(yīng)用：猴子大王
一群猴子排成一圈磺樱，按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泽示，對應(yīng)新的編號為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開始報(bào)數(shù)，數(shù)到m的那個人出列砍鸠，他的下一位又從1開始報(bào)數(shù)扩氢，數(shù)到m的那個人又出列耕驰，以此類推爷辱，直到所有人出列為止，由此產(chǎn)生一個出隊(duì)編號的序列朦肘。
使用環(huán)形鏈表解決約瑟夫問題
可使用一個不帶頭節(jié)點(diǎn)的循環(huán)鏈表來處理約瑟夫問題饭弓，首先構(gòu)造一個含有n個節(jié)點(diǎn)的單循環(huán)鏈表，然后由k節(jié)點(diǎn)起從1開始計(jì)數(shù)媒抠，計(jì)數(shù)到m時弟断，對應(yīng)節(jié)點(diǎn)從鏈表中刪除，然后再從被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)從1開始計(jì)數(shù)趴生，直到最后一個節(jié)點(diǎn)從鏈表中刪除阀趴。
鏈表
鏈表，最靈活的數(shù)據(jù)結(jié)構(gòu)苍匆。鏈表是有序的列表刘急，而在內(nèi)存中是分散存儲的。
鏈表是一種在邏輯上連續(xù)且有序的數(shù)據(jù)存儲結(jié)構(gòu)浸踩，而在物理存儲單元上是非連續(xù)且非有序的叔汁。
使用鏈表可解決類似約瑟夫問題、排序問題检碗、搜索索引据块、廣義表...
鏈表的類型可分為
- 單向鏈表
- 雙向鏈表
- 單向循環(huán)鏈表
- 雙向循環(huán)鏈表
- 十字鏈表/有向圖
單向鏈表
單向鏈表又稱為單鏈表，是一個鏈?zhǔn)酱鎯Y(jié)構(gòu)折剃，擁有一個表頭head另假，除了最后一個節(jié)點(diǎn)外，所有節(jié)點(diǎn)都有后繼節(jié)點(diǎn)怕犁。
單鏈表的每個節(jié)點(diǎn)都保存其數(shù)據(jù)域和后繼指針浪谴。
案例：排行榜
內(nèi)存分區(qū)
一個程序運(yùn)行時，內(nèi)存分成5個區(qū)域：棧區(qū)因苹、堆區(qū)苟耻、全局區(qū)/靜態(tài)存儲區(qū)、常量存儲區(qū)扶檐、代碼區(qū)/自由存儲區(qū)凶杖。
- 棧區(qū)
由編譯器需要時分配，不需要時自動清除的變量存儲區(qū)款筑，其中存儲的變量通常是局變量智蝠、函數(shù)參數(shù)等腾么。 - 堆區(qū)
使用new分配的內(nèi)存塊，它們的釋放是由應(yīng)用程序控制杈湾，而非編譯器控制解虱。一般而言，一個new就會對應(yīng)一個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)存段中。
- 數(shù)據(jù)段
data segment
又稱為初始化靜態(tài)段窃这，用來存放程序中已被初始化且不為0的全局變量瞳别，如靜態(tài)變量和常量。 - 代碼段/文本段
code segment/text segment
用于存放程序執(zhí)行代碼的內(nèi)存區(qū)域杭攻，如函數(shù)和方法祟敛。 - 棧空間段
存儲占用相同空間長度兆解，且占用空間小的數(shù)據(jù)類型馆铁。如整形在內(nèi)存中占用的空間是等長的，都是64bit(4byte)锅睛。常有int埠巨、float、bool... - 堆內(nèi)存
數(shù)據(jù)長度不定長现拒，且占用空間很大的數(shù)據(jù)類型的存儲區(qū)域辣垒。如string、array印蔬、class...
椦埃空間段是可以直接存取的，而堆內(nèi)存不可以直接存取。對于對象而言例驹，是一種很大且占用不定長的數(shù)據(jù)類型捐韩，所以對象是存放在堆中。但對象名是存放在棧中的鹃锈，因此通過對象名就可以訪問使用對象荤胁。
PHP的內(nèi)存管理
PHP的內(nèi)存管理是分層的，由上到下分為接口層屎债、堆層仅政、存儲層
- 接口層
接口層是PHP對外提供的可調(diào)用的方法，通過宏封裝了內(nèi)部實(shí)現(xiàn)扔茅。這些宏定義了一個高層次的接口已旧，使得調(diào)用更加容易秸苗，它隔離了外部調(diào)用和PHP內(nèi)存管理的內(nèi)部實(shí)現(xiàn)召娜，實(shí)現(xiàn)了一種松耦合關(guān)系际插。
- 堆層
在接口層下面是PHP內(nèi)存管理的核心實(shí)現(xiàn)锥债，稱之為heap層。堆層控制整個PHP內(nèi)存管理的過程舆床。
PHP中的內(nèi)存管理主要工作就是維護(hù)3個列表：小塊內(nèi)存列表free_buckets檀咙、大塊內(nèi)存列表large_free_buckets雅倒、剩余內(nèi)存列表rest_buckets。這里每個bucket也對應(yīng)一定大小的內(nèi)存塊列表弧可，這些列表都包含雙向鏈表的實(shí)現(xiàn)蔑匣。
對于小塊內(nèi)存是最常用的，所以追求高性能棕诵。對于大塊內(nèi)存則追求的是穩(wěn)妥裁良，盡量避免內(nèi)存浪費(fèi)。對于小塊內(nèi)存校套，PHP引入了cache機(jī)制价脾，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)存骇笔。
