goal00001111

     摘要: 1。建立迷宮（外圍建筑圍墻），可選擇人工創(chuàng)建迷宮或計(jì)算機(jī)隨機(jī)創(chuàng)建迷宮，還可修改迷宮
2。設(shè)置入口和出口。
3。尋找最短路徑，分別采用了廣度搜索，深度搜索（包括遞歸和非遞歸形式）
4。若找到可行路徑，打印路徑，否則報(bào)告錯(cuò)誤。  閱讀全文

     摘要: 三元組稀疏矩陣類：實(shí)現(xiàn)了矩陣的轉(zhuǎn)置，加法和乘法運(yùn)算  閱讀全文

     摘要: 人類習(xí)慣使用十進(jìn)制數(shù)進(jìn)行數(shù)值計(jì)算，而計(jì)算機(jī)則采用二進(jìn)制，所以為了讓計(jì)算機(jī)幫助人類計(jì)算，首先要把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)。本文以最簡(jiǎn)單的8位定點(diǎn)整數(shù)為例，分析了計(jì)算機(jī)存儲(chǔ)和計(jì)算數(shù)值的方法。  閱讀全文

     摘要: 摘要：延遲認(rèn)可算法（Gale-Shapley算法）是解決穩(wěn)定婚姻問題的經(jīng)典算法，本文用C++來實(shí)現(xiàn)Gale-Shapley算法。文章詳細(xì)介紹了Gale-Shapley算法的原理和編碼思路，給出了一個(gè)直接從原理出發(fā)的原始算法及其改進(jìn)版本，并對(duì)兩個(gè)版本進(jìn)行了比較分析。

關(guān)鍵詞：穩(wěn)定婚姻問題 延遲認(rèn)可算法 二維數(shù)組 以空間換時(shí)間
  閱讀全文

     摘要: 引子：這篇文章以前寫過，最近復(fù)習(xí)排序算法，覺得以前的代碼還可以改進(jìn)，因此有了此文。

歸并排序算法以O(shè)（NlogN）最壞情形運(yùn)行時(shí)間運(yùn)行，而所使用的比較次數(shù)幾乎是最優(yōu)的。

該算法中最基本的操作是合并兩個(gè)已排序的表，這只需要線性的時(shí)間，但同時(shí)需要分配一個(gè)臨時(shí)數(shù)組來暫存數(shù)據(jù)。

歸并排序算法可以用遞歸的形式實(shí)現(xiàn)，形式簡(jiǎn)潔易懂。如果N=1，則只有一個(gè)元素需要排序，我們可以什么都不做；否則，遞歸地將前半部分?jǐn)?shù)據(jù)和后半部分?jǐn)?shù)據(jù)各自歸并排序，然后合并這兩個(gè)部分。

歸并排序算法也可以用非遞歸的形式實(shí)現(xiàn)，稍微難理解一點(diǎn)。它剛好是遞歸分治算法的逆向思維形式，在使用遞歸分治算法時(shí)，程序員只需考慮將一個(gè)大問題分成若干個(gè)形式相同的小問題，和解的邊界條件，具體如何解決這些小問題是由計(jì)算機(jī)自動(dòng)完成的；而非遞歸形式要求程序員從最基本的情況出發(fā)，即從解決小問題出發(fā)，一步步擴(kuò)展到大問題。

我這里兩種形式都給出。

另外，很多人在寫遞歸形式的歸并排序算法時(shí)，臨時(shí)數(shù)組是在MergeSort函數(shù)中分配的，這使得在  閱讀全文

     摘要: 通過分析簡(jiǎn)單字符串模式匹配算法的缺陷，引導(dǎo)讀者觀察模式串P和目標(biāo)串T已比較相等字符的關(guān)系，自然而然的引入了高效的KMP算法，并對(duì)KMP算法的難點(diǎn)——失效函數(shù)進(jìn)行重點(diǎn)突破，先后比較了三種失效函數(shù)的區(qū)別和聯(lián)系，提供詳細(xì)的代碼及算法分析。最后得出結(jié)論：這樣我們就學(xué)習(xí)了三種失效函數(shù)的表示方法，雖然它們對(duì)應(yīng)的KMP算法代碼略有不同，但其本質(zhì)是一樣的，就是避免回溯目標(biāo)串T的下標(biāo)i，并使得模式串P的下標(biāo)j回溯到正確位置。同樣的，不管你用什么代碼來實(shí)現(xiàn)求解失效函數(shù)的算法，其本質(zhì)都是模式串內(nèi)部的模式匹配，采用遞推的方式，尋找最大的相同子串。  閱讀全文

     摘要: 我曾經(jīng)寫過一篇《有序全排列生成算法》，介紹了五種生成有序全排列的方法，在該文的末尾，我計(jì)劃再寫一篇姊妹篇《非有序全排列生成算法》，由于各種原因，一直遲遲未動(dòng)筆，前幾天學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)“棧”的時(shí)候，碰到一個(gè)有趣的問題“列車出棧序列”，其中有一種解法需要用到非有序全排列，所以決定先寫好本文，再總結(jié)該問題。

生成非有序全排列的算法很多，有普通遞歸算法，循環(huán)移位法，鄰位對(duì)換法，需要中介數(shù)的遞增進(jìn)位排列生成算法，遞減進(jìn)位排列生成算法和循環(huán)左移排列生成算法等。  閱讀全文

     摘要: 向量旋轉(zhuǎn)算法：將具有n個(gè)元素的向量a向左旋轉(zhuǎn)r個(gè)位置。
例如 ：將字符串"abcdefghij"旋轉(zhuǎn)成"defghjabc"，其中n=10，r=3。
其實(shí)就是將 AB 轉(zhuǎn)換成 BA 的過程，這里A ="abc"， B="defghij"。
本文總共采用了四種方法來解決向量旋轉(zhuǎn)問題  閱讀全文

     摘要: 實(shí)現(xiàn)了普通的查找和合并的算法，也實(shí)現(xiàn)了壓縮路徑和按大小求并高效算法，并對(duì)兩者進(jìn)行了測(cè)試比較。
有關(guān)算法的分析討論詳見拙作《一種簡(jiǎn)單而有趣的數(shù)據(jù)結(jié)構(gòu)--并查集》  閱讀全文

     摘要: 曼樹將字符串destCode進(jìn)行譯碼，得到目標(biāo)字符串objCode，比較objCode和sourceCode，發(fā)現(xiàn)完全一樣！編碼譯碼成功！最后銷毀有序二叉樹和赫夫曼樹。
本程序的一個(gè)亮點(diǎn)是使用了二叉堆來存儲(chǔ)需要合并的赫夫曼樹結(jié)點(diǎn)，這樣在求最小值時(shí)時(shí)間復(fù)雜度可以降低到log(n)。  閱讀全文