【程序員必會十大算法】之分治算法（漢諾塔問題）

codecraft 發(fā)布于2021-09-24 09:48 / 2853人閱讀

摘要：應用分治法是一種很重要的算法。字面上的解釋是分而治之，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

1.應用

分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題…直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。
這個技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，二分查找，傅立葉變換(快速傅立葉變換)，漢諾塔問題

2.漢諾塔問題

public static void main(String[] args) {        int[] arr = {1,1,2,2,33};        hanoiTower(3,"A","B","C");    }public static void hanoiTower(int num,char a,char b,char c){	   if (num == 1){	       System.out.println("將第1個盤從"+ a +"移動到" + c);	   }else {	       //將上面的盤從a移動到c，移動過程中會經(jīng)過b	       hanoiTower(num - 1,a,c,b);		       //將最下面的盤從a移動到c	       System.out.println("將第"+ num +"個盤從" + a + "移動到" + c);		       //將B塔的所有盤從b移動到c 移動過程會用到a	       hanoiTower(num - 1,b,a,c);	   }}

結(jié)果

將第1個盤從A移動到C將第2個盤從A移動到B將第1個盤從C移動到B將第3個盤從A移動到C將第1個盤從B移動到A將第2個盤從B移動到C將第1個盤從A移動到C

GPU云服務(wù)器云服務(wù)器簡單漢諾塔c語言算法分治算法最近點對分治算法漢諾塔

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/120964.html

相關(guān)文章

看動畫輕松理解「遞歸」與「動態(tài)規(guī)劃」

摘要：程序員小吳打算使用動畫的形式來幫助理解遞歸，然后通過遞歸的概念延伸至理解動態(tài)規(guī)劃算法思想。因此，分治策略一般用來解決子問題相互對立的問題，稱為標準分治，而動態(tài)規(guī)劃用來解決子問題重疊的問題。難點就在于找出動態(tài)規(guī)劃中的這三個概念。在學習「數(shù)據(jù)結(jié)構(gòu)和算法」的過程中，因為人習慣了平鋪直敘的思維方式，所以「遞歸」與「動態(tài)規(guī)劃」這種帶循環(huán)概念（繞來繞去）的往往是相對比較難以理解的兩個抽象知識點。...

cnio 2019-07-30 18:41 評論0 收藏0
漢諾塔算法

摘要：漢諾塔問題描述有三個圓柱，其中上從上至下放置了從小到大個圓盤，一次只能移動一個圓盤，且大的圓盤不能放在小圓盤之上，要求打印出從將圓盤移到的方案。漢諾塔問題描述：有A, B, C三個圓柱，其中A上從上至下放置了從小到大n個圓盤，一次只能移動一個圓盤，且大的圓盤不能放在小圓盤之上，要求打印出從A將圓盤移到C的方案。當n = 1時， A->C當n = 2時， A->B, A->C, B-...

UsherChen 2019-08-21 16:55 評論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法之漢諾塔問題（Java遞歸）

摘要：漢諾塔問題有三根柱子，源桿，暫存桿，目的桿上有層盤子，由小到大向下排列，現(xiàn)需要將桿的盤子移到桿中要求大的盤在下面，小的盤在上面一次只能移動一個盤子個人思路先分析問題，用數(shù)學的歸納法當只有一個盤時，直接移動當有兩個盤時，先將小的移到暫存桿，再漢諾塔問題：有三根柱子，源桿A，暫存桿temp，目的桿C A上有n層盤子，由小到大向下排列，現(xiàn)需要將A桿的盤子移到C桿中 ...

yuxue 2019-08-16 15:51 評論0 收藏0
算法思想

摘要：基礎(chǔ)算法思想類別遞推枚舉遞歸分治貪婪回溯試探模擬遞推遞推分類順推法從已知條件出發(fā)，逐步推算出要解決問題的方法。貪心算法的局限不能保證最后的解是最優(yōu)的不能求最大最小解問題只能求滿足某些約束條件的可行解范圍。基礎(chǔ)算法思想類別遞推枚舉遞歸分治貪婪回溯（試探）模擬遞推遞推分類順推法：從已知條件出發(fā)，逐步推算出要解決問題的方法。逆推法：從已知結(jié)果出發(fā)，用迭代表達式...

sshe 2019-08-15 17:50 評論0 收藏0
經(jīng)典算法：漢諾塔

摘要：學編程，學，算法也是必不可缺的，這一次給大家?guī)硪粋€經(jīng)典的遞歸算法題，漢諾塔。當我們把層都搬到了中間柱的時候，只需要把最大的那個盤，從搬到柱就好了，剩下的怎么辦呢柱永遠是目標柱，我們不需要去移動它。學編程，學IT，算法也是必不可缺的，這一次給大家?guī)硪粋€經(jīng)典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~ 視頻教程什么是漢諾塔？我這里直接拉來一個圖解釋一下（掛了請聯(lián)系我）sho...

Lin_R 2019-07-31 11:17 評論0 收藏0