欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言遞歸思想實現(xiàn)漢諾塔詳解

 更新時間:2022年01月21日 11:49:50   作者:weixin_58165485  
大家好,本篇文章主要講的是C語言遞歸思想實現(xiàn)漢諾塔詳解,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下

1.遞歸思想簡介

在c語言中,程序調(diào)用自身的編程技巧稱為遞歸( recursion)。

遞歸的定義看上去似乎很抽象,使用代碼描述能夠讓人容易理解,下面是一個函數(shù)遞歸的例子。

/*                                遞歸求n的階乘                        */
 
 
int factorial(int n)  //定義一個求階乘的函數(shù)叫做factorial(),需要一個整形參數(shù),返回一個整形值
{
	if (n <= 1)       //遞歸結(jié)束的條件
	{
		return 1;
	}
	else
	{
		return n * factorial(n - 1);//在factorial()中再次調(diào)用自身,只不過參數(shù)由n變成n-1
	}	
}

在這個例子中,函數(shù) factorial()接收到一個整形數(shù)n,如n=5,暫時稱作F(5),這時n!=F(5),而函數(shù)的功能如下:

判斷5是否小于或等于1,如果是,將1返回;不是,進(jìn)到else執(zhí)行語句返回(這里可以將return看作等于)5× factorial(n - 1),等價于 F(5)=5×F(4)用上面的方法計算F(4)=4×F(3)....以此類推直到達(dá)到限制條件n=1時有,F(xiàn)(1)=1

遞歸算法的實質(zhì):是把問題轉(zhuǎn)化為規(guī)??s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題。

由于每個小問題處理起來都有與大問題類似的行為邏輯,因此我們可以“大事化小”,而遞歸說白了,就是不斷地在套娃。

但是,計算機(jī)的內(nèi)存是有限的,由于每次調(diào)用函數(shù)都需要在棧區(qū)開辟一個空間,使得遞歸不能無限制地進(jìn)行下去,沒有遞歸結(jié)束的條件,當(dāng)操作系統(tǒng)為進(jìn)程分配的虛擬地址空間當(dāng)中的??臻g被耗盡時,會發(fā)生堆棧溢出,產(chǎn)生段錯誤(segmentation fault)。

因此,使用遞歸時應(yīng)注意:

必須存在限制條件,當(dāng)滿足這個限制條件的時候,遞歸便不再繼續(xù)每次遞歸調(diào)用之后越來越接近這個限制條件 

遞歸的好處在于:

代碼簡潔在某些特定問題上求解方便

遞歸的缺點在于

消耗大量時間和空間資源——效率較低可能伴隨許多重復(fù)計算,工作量大——影響性能

2.漢諾塔問題

以下內(nèi)容來自維基百科

最早發(fā)明這個問題的人是法國數(shù)學(xué)家愛德華·盧卡斯。

傳說越南河內(nèi)某間寺院有三根銀棒,上串 64 個金盤。寺院里的僧侶依照一個古老的預(yù)言,以上述規(guī)則移動這些盤子;預(yù)言說當(dāng)這些盤子移動完畢,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創(chuàng)的這個傳說,還是他受他人啟發(fā)。

若傳說屬實,僧侶們需要2^{64}-1步才能完成這個任務(wù);若他們每秒可完成一個盤子的移動,就需要 5849 億年才能完成。整個宇宙現(xiàn)在也不過 137 億年。

這個傳說有若干變體:寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位于越南的河內(nèi),所以被命名為“河內(nèi)塔”。另外亦有“金盤是創(chuàng)世時所造”、“僧侶們每天移動一盤”之類的背景設(shè)定

漢諾塔基本的玩法如圖,其規(guī)則是:將圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。 

 當(dāng)圓盤數(shù)量只有3個的時候,求解的方法顯而易見,但當(dāng)數(shù)量增多時,問題變得有些棘手起來。但不管怎么移動,核心思想都是遞歸:

先從n塊圓盤中將最大的一塊移動到最后的柱子上接著從剩下n-1找到最大的一塊移到柱子上...... 

3.漢諾塔遞歸的c語言實現(xiàn)

C語言代碼如下:

/*                            漢諾塔問題(遞歸實現(xiàn))                     */
 
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
void move(char, char); // 聲明一個函數(shù)move,函數(shù)定義在下方,用于表示圓盤的交換
 
void Towers_Of_Hanoi(int n,char a,char b,char c) 
{
	if (1 == n)                        //遞歸結(jié)束標(biāo)志:當(dāng)柱子上只有一塊圓盤
	{
		move(a, c);                    //從a移動到c
	}
	else
		Towers_Of_Hanoi(n - 1, a, c, b);    //將最上面n-1個圓盤移動到b柱上
		move(a, c);                         //將a上面最后一塊圓盤移動到c柱上
		Towers_Of_Hanoi(n - 1, b, a, c);    //將b柱上n-1個圓盤移動到a柱上
	}
}
 
void move(char x, char y)
{
	printf("%c-->%c\n", x, y);
}
 
int main()
{
	int n = 0;
	scanf("%d", &n);
	Towers_Of_Hanoi(n, 'A', 'B', 'C');//n為A柱子上圓盤的數(shù)量,A,B,C代表三根柱子
	return 0;
}

程序運行結(jié)果為:

總結(jié)

到此這篇關(guān)于C語言遞歸思想實現(xiàn)漢諾塔詳解的文章就介紹到這了,更多相關(guān)C語言漢諾塔內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言繪制雷達(dá)圖的示例代碼

    C語言繪制雷達(dá)圖的示例代碼

    常用的統(tǒng)計圖有條形圖、柱形圖、折線圖、曲線圖、餅圖、環(huán)形圖、扇形圖,其中還有一種雷達(dá)圖的繪制也較難,本文為大家提供了雷達(dá)圖的繪制方法,需要的可以參考下
    2024-02-02
  • QT利用QPdfWriter實現(xiàn)繪制PDF(支持表單輸出)

    QT利用QPdfWriter實現(xiàn)繪制PDF(支持表單輸出)

    這篇文章主要為大家詳細(xì)介紹了QT如何利用QPdfWriter實現(xiàn)繪制PDF,并可以支持表單輸出。文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下
    2023-01-01
  • Qt跨平臺窗口選擇功能的實現(xiàn)過程

    Qt跨平臺窗口選擇功能的實現(xiàn)過程

    很多時候為了方便軟件的使用,我們需要讓編寫的界面程序顯示在最上層,這時候就需要對窗口屬性進(jìn)行調(diào)整,下面這篇文章主要給大家介紹了關(guān)于Qt跨平臺窗口選擇功能的實現(xiàn)過程,需要的朋友可以參考下
    2022-12-12
  • 探討:將兩個鏈表非降序合并為一個鏈表并依然有序的實現(xiàn)方法

    探討:將兩個鏈表非降序合并為一個鏈表并依然有序的實現(xiàn)方法

    本篇文章是對將兩個鏈表非降序合并為一個鏈表并依然有序的實現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • Cocos2d-x UI開發(fā)之CCControlPotentiometer控件類使用實例

    Cocos2d-x UI開發(fā)之CCControlPotentiometer控件類使用實例

    這篇文章主要介紹了Cocos2d-x UI開發(fā)之CCControlPotentiometer控件類使用實例,本文代碼中包含注釋來講解CCControlPotentiometer控件類的使用,需要的朋友可以參考下
    2014-09-09
  • C語言修煉之路靈根孕育源流出?初識C言大道生下篇

    C語言修煉之路靈根孕育源流出?初識C言大道生下篇

    C語言是一門面向過程、抽象化的通用程序設(shè)計語言,廣泛應(yīng)用于底層開發(fā)。C語言能以簡易的方式編譯、處理低級存儲器。C語言是僅產(chǎn)生少量的機(jī)器語言以及不需要任何運行環(huán)境支持便能運行的高效率程序設(shè)計語言
    2022-03-03
  • C++11中l(wèi)ambda、std::function和std:bind詳解

    C++11中l(wèi)ambda、std::function和std:bind詳解

    大家都知道C++11中增加了許多的新特性,下面在這篇文中我們就來聊一下lambda表達(dá)式,閉包,std::function以及std::bind。文中介紹的很詳細(xì),相信對大家具有一定的參考價值,有需要的朋友們下面來一起看看吧。
    2017-01-01
  • C語言數(shù)據(jù)結(jié)構(gòu)時間復(fù)雜度及空間復(fù)雜度簡要分析

    C語言數(shù)據(jù)結(jié)構(gòu)時間復(fù)雜度及空間復(fù)雜度簡要分析

    我們在進(jìn)行編程時,往往會開發(fā)諸多的算法,那么我們怎么在那么多算法中找到最好的那個呢?本文主要介紹時間和空間復(fù)雜度概念及時間復(fù)雜度的求解,預(yù)祝讀者學(xué)習(xí)愉快
    2021-10-10
  • C++核心編程之內(nèi)存分區(qū)模型詳解

    C++核心編程之內(nèi)存分區(qū)模型詳解

    這篇文章主要為大家介紹了C++核心編程中內(nèi)存分區(qū)模型,C++程序在執(zhí)行時,將內(nèi)存大方向分為四個區(qū)域,代碼區(qū),全局區(qū),棧區(qū),堆區(qū),文章通過代碼示例介紹的非常詳細(xì),感興趣的同學(xué)可以參考閱讀下
    2023-07-07
  • C語言 文件的隨機(jī)讀寫詳解及示例代碼

    C語言 文件的隨機(jī)讀寫詳解及示例代碼

    本文主要介紹C語言 文件的隨機(jī)讀寫,這里整理了相關(guān)資料及示例代碼以便大家學(xué)習(xí)參考,學(xué)習(xí)此部分內(nèi)容的朋友可以參考下
    2016-08-08

最新評論