算法分析theanalysisofalgorithms-資料下載頁
2025-02-06 22:22本頁面
【正文】 5 二叉樹的查找與插入 最差效率 Θ(n)，平均效率 Θ(logn) 169。 School of Computer Science and Technology, SWUST 26 拈游戲 (Nim Game) 有 13根火柴棍，每次最少拿走 1根， 最多能拿走 4根，拿走最后一根火 柴的就是贏家。該如何拿走火柴？ n=m+1實例是敗局 m+2≤n ≤2m+1是勝局 2m+2=2(m+1)另一個敗局 獲勝策略每次拿走 n mod (m+1)根火柴棍 169。 School of Computer Science and Technology, SWUST 27 拈游戲 (Nim Game) ? 多堆拈游戲 ? 每堆火柴棍的數量不一致，每次拿走火柴棍時可以從任意一堆中拿走任意允許數量的火柴棍，甚至可以把一堆都拿光。拿走最后一根火柴的是贏家。 ? 1901年，哈佛大學數學教授 . Bouton發(fā)現了一個精巧解法： ? 解是基于堆中數量的二進制表示的。 ? b1,b2,...,bi分別是各堆數量的二進制表示；計算它們的二進制數位和 （忽略進位）。 ? 當且僅當二進制數位和中包含至少一個 1時，為勝局；只包含 0時，為敗局。 169。 School of Computer Science and Technology, SWUST 28 減治法小結 ? 減治技術利用了一種關系：一個問題給定實例的解和同樣的問題較小實例的解之間的關系。一旦建立了這種關系，就可以從頂至下（遞歸），也可以從底至上（非遞歸）的來運用。 ? 減治法有三種變種： ? 1)減去一個常量 ? 2)減去一個常數因子 ? 3)減去的規(guī)模是可變的 ? 用減治法解決的問題有：插入排序， DFS，BFS，俄式乘法，選擇問題 169。 School of Computer Science and Technology, SWUST 29 reference 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH
語文相關推薦
鄂ICP備17016276號-1