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

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

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

1.應(yīng)用

分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題…直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。
這個(gè)技巧是很多高效算法的基礎(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個(gè)盤從"+ a +"移動(dòng)到" + c);	   }else {	       //將上面的盤從a移動(dòng)到c，移動(dòng)過程中會(huì)經(jīng)過b	       hanoiTower(num - 1,a,c,b);		       //將最下面的盤從a移動(dòng)到c	       System.out.println("將第"+ num +"個(gè)盤從" + a + "移動(dòng)到" + c);		       //將B塔的所有盤從b移動(dòng)到c 移動(dòng)過程會(huì)用到a	       hanoiTower(num - 1,b,a,c);	   }}

結(jié)果

將第1個(gè)盤從A移動(dòng)到C將第2個(gè)盤從A移動(dòng)到B將第1個(gè)盤從C移動(dòng)到B將第3個(gè)盤從A移動(dòng)到C將第1個(gè)盤從B移動(dòng)到A將第2個(gè)盤從B移動(dòng)到C將第1個(gè)盤從A移動(dòng)到C

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/120964.html

相關(guān)文章

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

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

cnio 2019-07-30 18:41 評(píng)論0 收藏0
漢諾塔算法

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

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

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

yuxue 2019-08-16 15:51 評(píng)論0 收藏0
算法思想

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

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

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

Lin_R 2019-07-31 11:17 評(píng)論0 收藏0