演算法設計

1/2ページ

過河問題-狼羊人菜

/* *功能:解決狼羊人過河問題 *作者:王文堃 *作者郵箱:[email protected] *建立時間:2016/4/5 */ /* 問題描述:有一個人帶著一匹狼、一頭羊和白菜要過河 已知人每次過河只能帶一樣東西,狼和羊不能單獨在一起 羊和菜不能單獨在一起,求人過河的方案有幾種? 問題抽象 […]

蒙特卡洛樹演算法 (MCTS)

實質上可以看成一種增強學習 蒙特卡羅樹搜尋(MCTS)會逐漸的建立一顆不對稱的樹。可以分為四步並反覆迭代: (1)選擇 從根節點,也就是要做決策的局面R出發向下選擇一個最急迫需要被拓展的節點T;局面R是第一個被檢查的節點,被檢查的節點如果存在一個沒有被評價過的招式m,那麼被檢查的節點在執行m後得到的 […]

磁碟排程演算法剖析(FIFO、SSTF、SCAN、CSCAN、FSCAN)

常見的磁碟排程演算法有以下幾種: 1.FIFO:先來先服務演算法; 2.SSTF: 最短尋道時間演算法; 3.SCAN:電梯排程演算法;(這樣命名很形象) 4.CSCAN: 迴圈掃描演算法 5.FSCAN:分步電梯排程演算法(分兩個佇列) 下面詳細說一下各個演算法的主要思想: 首先是FIFO演算法, […]

藍橋杯-合併石子 (經典動態規劃)

題目大意:假設有一排n堆石子,每堆石子有若干個小石子,要求將它們合併成一堆,需要花費的最小代價。而且每次合併只能將相鄰的兩堆合併,合併的代價是兩堆石子的重量之和。 題目分析:因為不能合併有間隔的石子堆,所以這不是一道哈夫曼樹的例子(哈夫曼樹:利用貪心演算法,每次合併重量最小的兩堆石子)。 通過分解子 […]

數字影象加密演算法

本文主要介了四種加密:隨機擾亂圖片資訊的行或列進行加密;隨機擾亂圖片資訊的畫素點進行加解密;縮放圖片資訊的畫素點進行加解密;以上都屬於加密後立即進行解密。再就是利用混沌序列進行加解密,使用了固定演算法,通過加解密金鑰形成了加密後的非立即解密方法。 1.隨機打亂各行進行數字影象加密: %隨機打亂各行進 […]

費雪耶茲(Fisher–Yates) 也被稱作高納德( Knuth)隨機置亂演算法

Fisher–Yates隨機置亂演算法也被稱做高納德置亂演算法,通俗說就是生成一個有限集合的隨機排列。Fisher-Yates隨機置亂演算法是無偏的,所以每個排列都是等可能的,當前使用的Fisher-Yates隨機置亂演算法是相當有效的,需要的時間正比於要隨機置亂的數,不需要額為的儲存空間開銷。 一 […]

編輯距離——萊文斯坦距離(Levenshtein distance)

在資訊理論和電腦科學中,萊文斯坦距離是一種兩個字串序列的距離度量。形式化地說,兩個單詞的萊文斯坦距離是一個單詞變成另一個單詞要求的最少單個字元編輯數量(如:刪除、插入和替換)。萊文斯坦距離也被稱做編輯距離,儘管它只是編輯距離的一種,與成對字串比對緊密相關。 一、定義 數學上,兩個字串a、b之間的萊文 […]

蒙特卡洛演算法——投點求圓周率Pi

蒙特卡洛演算法是以概率和統計的理論、方法為基礎的一種計算方法,將所求解的問題同一定的概率模型相聯絡;用電子計算機實現統計模擬和抽樣,以獲得問題的近似解,故又稱統計模擬法或統計實驗法。 蒙特卡洛演算法:蒙特卡洛是美國摩納哥的一個城市,以賭博聞名於世。蒙特卡洛演算法借用這一城市的名稱是為了象徵性的表明該 […]

第六次CCF計算機軟體能力認證考試(第四題)

問題描述   某國有n個城市,為了使得城市間的交通更便利,該國國王打算在城市之間修一些高速公路,由於經費限制,國王打算第一階段先在部分城市之間修一些單向的高速公路。   現在,大臣們幫國王擬了一個修高速公路的計劃。看了計劃後,國王發現,有些城市之間可以通過高速公路直接(不經過其他城市)或間接(經過一 […]