北京中瑞祥科技有限公司
中級會員 | 第7年

17316027162

當(dāng)前位置:首頁   >>   資料下載   >>   中瑞祥解析河內(nèi)塔背景由來以及算法

實驗室設(shè)備
氣體檢測儀
水質(zhì)檢測儀
無損檢測儀器
環(huán)境監(jiān)測儀器
分析儀器
電工儀器儀表
氣象儀器
流量計
試驗機
溫濕度儀器
記錄儀
電子測量儀器
光學(xué)儀器
專用儀器儀表
結(jié)晶點 烘干儀 旋光儀 比色管 阻力測定儀 破碎儀 定硫儀 雨量計 電流測定儀 擴散儀 篩分儀 粗糙度 放大 應(yīng)變 色差 視野 溶氧 頻響儀 洗砂機 消解儀 電位 發(fā)生 天平 場強 定氮儀 探傷 轉(zhuǎn)速 噴霧 記錄 計數(shù) 電導(dǎo)率 滴定儀 切片機 均質(zhì)機 指示器 消毒器 烤膠機 比重計 測定器 混合器 吹干儀 報警控制器 紫外輻照計 磨粉機 采泥器 過濾裝置 讀數(shù)望遠鏡 報警儀 萃取器 空壓機 指數(shù)儀 熒光顯微鏡 高頻Q表 測試臺 工具包 點膠機 消化器 測角 恒速器 測氡儀 壓力計 折射儀 密度 油耗儀 檢測記錄儀 輻射記錄儀 色度計 太陽輻射儀 輸液泵 消化爐 水質(zhì)PH儀 加熱器 試驗爐 氫氣發(fā)生器 電阻器 氣體流量計 評價附件 讀數(shù)儀 保險柜 消解器 浴槽系統(tǒng) 純水機 度計 離子焊機 混濾波器 氣浮實驗 檢定儀 旋轉(zhuǎn)儀 折光儀 儲存箱 風(fēng)速儀 生物顯微鏡 鉆取器 留樣器 回彈儀 數(shù)字電橋 評定儀 抄取器 沉積物采樣器 氮吹儀 測溫儀 崩解儀 電導(dǎo)率儀 檢定裝置 鍍膜機 洛氏硬度計 分析系統(tǒng) 監(jiān)測儀 實驗臺 無油空壓機 激光器 濕度計 比濁儀 清洗機 校準(zhǔn)器 反射率儀 壓片機 計數(shù)器 平衡箱 取樣器 提取儀 分光光度計 培養(yǎng)箱 土壤采樣器 制氮機 參數(shù)記錄儀 試驗箱 空氣采樣器 輻射照度計 混勻儀 水質(zhì)硬度計 定器裝置 速測儀 露點儀 極譜儀 低速風(fēng)洞 試驗儀 輥壓機 斯計 濾失儀 一體機 伏安表 離心機 白度儀 流速儀 攪拌儀 濕度記錄儀 強度儀 無菌均質(zhì)器 攤片機 實驗裝置 便攜式密度計 涂布機 活度計 沖片機 閃點儀 測量儀 情測報燈 識別儀 采信儀 沉淀池裝置 濁度儀 笑氣檢測儀 單色儀 皮脂厚度計 視野計 開關(guān) 分析儀 測厚儀 趕酸儀 測試儀 濃度計 電流表 PH計 涂膜機 溫度計 振蕩器 磁導(dǎo)率 發(fā)氣量 暗適應(yīng)儀 顆粒強度測定儀 油料專用計算器 傳感器 測距儀 檢測儀 測定儀
探測儀
頻率計

中瑞祥解析河內(nèi)塔背景由來以及算法

時間:2023-9-22閱讀:804
分享:
  • 提供商

    北京中瑞祥科技有限公司
  • 資料大小

    22.1KB
  • 資料圖片

    查看
  • 下載次數(shù)

    75次
  • 資料類型

    WORD 文檔
  • 瀏覽次數(shù)

    804次
點擊免費下載該資料

中瑞祥解析河內(nèi)塔背景由來以及算法

 

 

背景由來

法國數(shù)學(xué)家愛德華·盧卡斯曾編寫過一個印度的古老傳說:在世界中心貝拿勒斯(在印度北部)的圣廟里,一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候,在其中一根針上從下到上地穿好了由大到小的64片金片,這就是所謂的漢諾塔。不論白天黑夜,總有一個僧侶在按照下面的法則移動這些金片:一次只移動一片,不管在哪根針上,小片必須在大片上面。僧侶們預(yù)言,當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時,世界就將在一聲霹靂中消滅,而梵塔、廟宇和眾生也都將同歸于盡。

不管這個傳說的可信度有多大,如果考慮一下把64片金片,由一根針上移到另一根針上,并且始終保持上小下大的順序。這需要多少次移動呢?這里需要遞歸的方法。假設(shè)有n片,移動次數(shù)是f(n).顯然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不難證明f(n)=2^n-1。n=64時,

 

算法介紹

其實算法非常簡單,當(dāng)盤子的個數(shù)為n時,移動的次數(shù)應(yīng)等于2^n – 1(有興趣的可以自己證明試試看)。后來一位美國學(xué)者發(fā)現(xiàn)一種出人意料的簡單方法,只要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型,把所有的圓盤按從大到小的順序放在柱子A上,根據(jù)圓盤的數(shù)量確定柱子的排放順序:若n為偶數(shù),按順時針方向依次擺放 A B C;

n為奇數(shù),按順時針方向依次擺放 A C B。

⑴按順時針方向把圓盤1從現(xiàn)在的柱子移動到下一根柱子,即當(dāng)n為偶數(shù)時,若圓盤1在柱子A,則把它移動到B;若圓盤1在柱子B,則把它移動到C;若圓盤1在柱子C,則把它移動到A。

⑵接著,把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上,當(dāng)兩根柱子都非空時,移動較小的圓盤。這一步?jīng)]有明確規(guī)定移動哪個圓盤,你可能以為會有多種可能性,其實不然,。

⑶反復(fù)進行⑴⑵操作,最后就能按規(guī)定完成漢諾塔的移動。

所以結(jié)果非常簡單,就是按照移動規(guī)則向一個方向移動金片:

3階漢諾塔的移動:A→C,A→B,C→B,A→C,B→A,B→C,A→C

漢諾塔問題也是程序設(shè)計中的經(jīng)典遞歸問題,下面我們將給出遞歸和非遞歸的不同實現(xiàn)源代碼。


會員登錄

×

請輸入賬號

請輸入密碼

=

請輸驗證碼

收藏該商鋪

X
該信息已收藏!
標(biāo)簽:
保存成功

(空格分隔,最多3個,單個標(biāo)簽最多10個字符)

常用:

提示

X
您的留言已提交成功!我們將在第一時間回復(fù)您~
撥打電話
在線留言