| | hàn nuò tǎ （ yòu chēng hé nèi tǎ） wèn tí shì yìn dù de yī gè gǔ lǎo de chuán shuō。 kāi tiān pìdì de shén bó lā mǎ zài yī gè miào lǐ liú xià liǎo sān gēn jīn gāng shí de bàng， dì yī gēn shàng miàn tào zhe 64 gè yuán de jīn piàn， zuì dà de yī gè zài dǐ xià， qí yú yī gè bǐ yī gè xiǎo， yǐ cì dié shàng qù， miào lǐ de zhòng sēng bù juàn dì bǎ tā men yī gè gè dì cóng zhè gēn bàng bān dào lìng yī gēn bàng shàng， guī dìng kě lì yòng zhōng jiān de yī gēn bàng zuò wéi bāng zhù， dàn měi cì zhǐ néng bān yī gè， ér qiě dà de bù néng fàng zài xiǎo de shàng miàn。 jiě dá jiēguǒ qǐng zì jǐ yùn xíng jì suàn， chéng xù jiàn wěi bù。 miàn duì páng dà de shù zì ( yí dòng yuán piàn de cì shù )18446744073709551615， kàn lái， zhòng sēng men hào jìn bì shēng jīng lì yě bù kě néng wán chéng jīn piàn de yí dòng。
hòu lái， zhè gè chuán shuō jiù yǎn biàn wéi hàn nuò tǎ yóu xì :
1. yòu sān gēn gān zǐ a,b,c。 a gān shàng yòu ruò gān dié zǐ
2. měi cì yí dòng yī kuài dié zǐ , xiǎo de zhǐ néng dié zài dà de shàng miàn
3. bǎ suǒ yòu dié zǐ cóng a gān quán bù yí dào c gān shàng
jīng guò yán jiū fā xiàn， hàn nuò tǎ de pò jiě hěn jiǎn dān， jiù shì 'àn zhào yí dòng guī zé xiàng yī gè fāng xiàng yí dòng jīn piàn：
rú 3 jiē hàn nuò tǎ de yí dòng： a → c,a→ b,c→ b,a→ c,b→ a,b→ c,a→ c
cǐ wài， hàn nuò tǎ wèn tí yě shì chéng xù shè jì zhōng de jīng diǎn dì guī wèn tí。
bǔ chōng： hàn nuò tǎ de suàn fǎ shí xiàn（ c++）
#include<fstream>
#include<iostream>
usingnamespacestd;
ofstreamfout("out.txt");
voidmove(intn,charx,chary)
{
fout<<" bǎ "<<n<<" hào cóng "<<x<<" nuó dòng dào "<<y<<endl;
}
voidhannoi(intn,chara,charb,charc)
{
if(n==1)
move(1,a,c);
else
{
hannoi(n-1,a,c,b);
move(n,a,c);
hannoi(n-1,b,a,c);
}
}
intmain()
{
fout<<" yǐ xià shì 7 céng hàn nuò tǎ de jiě fǎ :"<<endl;
hannoi(7,'a','b','c');
fout.close();
cout<<" shū chū wán bì！ "<<endl;
return0;
}
c yǔ yán jīng jiǎn suàn fǎ
/*copyrighterbyss7e*/
#include<stdio.h>/*copyrighterbyss7e*/
voidhanoi(intn,chara,charb,charc)/*copyrighterbyss7e*/
{
if(n==1)
{
printf("movedisk%dfrom%cto%c
",n,a,c);
}
else
{
hanoi(n-1,a,c,b);/*copyrighterbyss7e*/
printf("movedisk%dfrom%cto%c
",n,a,c);
hanoi(n-1,b,a,c);/*copyrighterbyss7e*/
}
}
main()/*copyrighterbyss7e*/
{
intn;
printf(" qǐng shū rù shù zì n yǐ jiě jué n jiē hàn nuò tǎ wèn tí：
");
scanf("%d",&n);
hanoi(n,'a','b','c');
}/*copyrighterbyss7e*/ | | hàn nuò tǎ de yóu lái
hàn nuò tǎ shì yuán zì yìn dù shén huà lǐ de wán jù。
shàng dì chuàng zào shì jiè de shí hòu zuò liǎo sān gēn jīn gāng shí zhù zǐ， zài yī gēn zhù zǐ shàng cóng xià wǎng shàng 'ān dà xiǎo shùn xù luò zhe 64 piàn huáng jīn yuán pán。
shàng dì mìng lìng pó luó mén bǎ yuán pán cóng xià miàn kāi shǐ 'àn dà xiǎo shùn xù chóngxīn bǎi fàng zài lìng yī gēn zhù zǐ shàng。 bìng qiě guī dìng， zài xiǎo yuán pán shàng bù néng fàng dà yuán pán， zài sān gēn zhù zǐ zhī jiān yī cì zhǐ néng yí dòng yī gè yuán pán。
yòu yù yán shuō， zhè jiàn shì wán chéng shí yǔ zhòu huì zài yī shùn jiān shǎn diàn shì huǐ miè。 yě yòu rén xiāng xìn pó luó mén zhì jīn hái zài yī kè bù tíng dì bān dòng zhe yuán pán。
hàn nuò tǎ yǔ yǔ zhòu shòu mìng
rú guǒ yí dòng yī gè yuán pán xū yào 1 miǎo zhōng de huà， děng dào 64 gè yuán pán quán bù chóngxīn luò zài yī qǐ， yǔ zhòu bèi huǐ miè shì shénme shí hòu ní？
ràng wǒ men lái kǎo lǜ yī xià 64 gè yuán pán chóngxīn luò hǎo xū yào yí dòng duō shǎo cì bā。 1 gè de shí hòu dāng rán shì 1 cì， 2 gè de shí hòu shì 3 cì， 3 gè de shí hòu jiù yòng liǎo 7 cì ...... zhè shí zài shì tài lěi liǎo
yīn cǐ ràng wǒ men luó ji xìng de sī kǎo yī xià bā。
4 gè de shí hòu néng gòu yí dòng zuì dà de 4 pán shí rú tú suǒ shì。
dào cǐ wéi zhǐ yòng liǎo 7 cì。
jiē xià lái rú xià tú shí yòng 1 cì， zài shàng miàn zài fàng shàng 3 gè yuán pán shí hái yào yòng 7 cì（ bǎ 3 gè yuán pán chóngxīn fàng zài yī qǐ xū yào de cì shù）。
yīn cǐ， 4 gè de shí hòu shì
“ 3 gè yuán pán chóngxīn luò zài yī qǐ de cì shù ” +1 cì +“ 3 gè yuán pán chóngxīn luò zài yī qǐ xū yào de cì shù”
=2x“ 3 gè yuán pán chóngxīn luò zài yī qǐ de cì shù” +1 cì
=15 cì。
nà me， n gè de shí hòu shì
2x“（ n-1） gè yuán pán chóngxīn luò zài yī qǐ de cì shù” +1 cì。
yóu yú 1 gè de shí hòu shì 1 cì， jiēguǒ n gè de shí hòu wéi（ 2 de n cì fāng jiǎn 1） cì。
1 gè yuán pán de shí hòu 2 de 1 cì fāng jiǎn 1
2 gè yuán pán de shí hòu 2 de 2 cì fāng jiǎn 1
3 gè yuán pán de shí hòu 2 de 3 cì fāng jiǎn 1
4 gè yuán pán de shí hòu 2 de 4 cì fāng jiǎn 1
5 gè yuán pán de shí hòu 2 de 5 cì fāng jiǎn 1
........
n gè yuán pán de shí hòu 2 de n cì fāng jiǎn 1
yě jiù shì shuō， n=64 de shí hòu shì（ 2 de 64 cì fāng jiǎn 1） cì。
yīn cǐ， rú guǒ yí dòng yī gè yuán pán xū yào 1 miǎo de huà，
yǔ zhòu de shòu mìng =2 de 64 cì fāng jiǎn 1（ miǎo）
yòng yī nián =60 miǎo x60 fēn x24 xiǎo shí x365 tiān lái suàn de huà， dà yuē yòu 5800 yì nián bā。
jù shuō， xiàn zài de yǔ zhòu nián líng dà yuē shì 150 yì nián， hái chā dé yuǎn ní。
hàn nuò tǎ wèn tí zài shù xué jiè yòu hěn gāo de yán jiū jià zhí，
ér qiě zhì jīn hái zài bèi yī xiē shù xué jiā men suǒ yán jiū，
yě shì wǒ men suǒ xǐ huān wán de yī zhǒng yì zhì yóu xì，
tā kě yǐ bāng zhù kāi fā zhì lì， jī fā wǒ men de sī wéi。
hàn nuò tǎ de C yǔ yán shí xiàn
#include"stdio.h"
voidmove(charx,chary)
{
printf("%c-->%cn",x,y);
}
voidhanoi(intn,charone,chartwo,charthree)
{
if(n==1)move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main()
{
intm;
printf("inputthenumberofdisks:");
scanf("%d",&m);
printf("thesteptomoving%3ddiskes:n",m);
hanoi(m,'A','B','C');
}
==================================== huá lì de fēn gē xiàn ==================================
concreteHAM：
xiàn zài yòu sān gēn xiāng lín de zhù zǐ， biāo hào wéi A,B,C， A zhù zǐ shàng cóng xià dào shàng 'àn jīn zì tǎ zhuàng dié fàng zhe n gè bù tóng dà xiǎo de yuán pán， xiàn zài bǎ suǒ yòu pán zǐ yī gè yī gè yí dòng dào zhù zǐ B shàng， bìng qiě měi cì yí dòng tóng yī gēn zhù zǐ shàng dōubù néng chū xiàn dà pán zǐ zài xiǎo pán zǐ shàng fāng， qǐng wèn zhì shǎo xū yào duō shǎo cì yí dòng， shè yí dòng cì shù wéi H(n)。
shǒu xiān wǒ men kěn dìng shì bǎ shàng miàn n-1 gè pán zǐ yí dòng dào zhù zǐ C shàng， rán hòu bǎ zuì dà de yī kuài fàng zài B shàng， zuì hòu bǎ C shàng de suǒ yòu pán zǐ yí dòng dào B shàng， yóu cǐ wǒ men dé chū biǎo dá shì：
H(1)=1
H(n)=2*H(n-1)+1(n>1)
nà me wǒ men hěn kuài jiù néng dé dào H(n) de yī bān shì：
H(n)=2^n-1(n>0)
bìng qiě zhè zhǒng fāng fǎ díquè shì zuì shǎo cì shù de， zhèng míng fēi cháng jiǎn dān， kě yǐ cháng shì cóng 2 gè pán zǐ de yí dòng kāi shǐ zhèng， nǐ kě yǐ shì shì。
jìn yī bù jiā shēn wèn tí ( jiě fǎ yuán chuàng *_*)：
jiǎ rú xiàn zài měi zhǒng dà xiǎo de pán zǐ dōuyòu liǎng gè， bìng qiě shì xiāng lín de， shè pán zǐ gè shù wéi 2n， wèn： (1) jiǎ rú bù kǎo lǜ xiāng tóng dà xiǎo pán zǐ de shàng xià yào duō shǎo cì yí dòng， shè yí dòng cì shù wéi J(n)； (2) zhǐ yào bǎo zhèng dào zuì hòu B shàng de xiāng tóng dà xiǎo pán zǐ shùn xù yǔ A shàng shí xiāng tóng， xū yào duō shǎo cì yí dòng， shè yí dòng cì shù wéi K(n)。
(1) zhōng de yí dòng xiāng dāng yú shì bǎ qián yī gè wèn tí zhōng de měi gè pán zǐ duō yí dòng yī cì， yě jiù shì：
J(n)=2*H(n)=2*(2^n-1)=2^(n+1)-2
zài fēn xī (2) zhī qián， wǒ men lái shuō míng yī gè xiàn xiàng， jiǎ rú A zhù zǐ shàng yòu liǎng gè dà xiǎo xiāng tóng de pán zǐ， shàng miàn yī gè shì hēi sè de， xià miàn yī gè shì bái sè de， wǒ men bǎ liǎng gè pán zǐ yí dòng dào B shàng， xū yào liǎng cì， pán zǐ shùn xù jiāng biàn chéng hēi de zài xià， bái de zài shàng， rán hòu zài bǎ B shàng de pán zǐ yí dòng dào C shàng， xū yào liǎng cì， pán zǐ shùn xù jiāng yǔ A shàng shí xiāng tóng， yóu cǐ wǒ men guī nà chū dāng xiāng lín liǎng gè pán zǐ dū yí dòng 'ǒu shù cì shí， pán zǐ shùn xù jiāng bù biàn， fǒu zé shàng xià diān dǎo。
xiàn zài huí dào zuì kāi shǐ de wèn tí， n gè pán zǐ yí dòng， shàng fāng de n-1 gè pán zǐ zǒng yí dòng cì shù wéi 2*H(n-1)， suǒ yǐ shàng fāng n-1 gè pán zǐ de yí dòng cì shù bì dìng wéi 'ǒu shù cì， zuì hòu yī gè pán zǐ yí dòng cì shù wéi 1 cì。
tǎo lùn wèn tí (2)， zōng shàng liǎng diǎn， kě yǐ dé chū， yào bǎ A shàng 2n gè pán zǐ yí dòng dào B shàng， shǒu xiān kě yǐ dé chū shàng fāng de 2n-2 gè pán zǐ bì dìng yí dòng 'ǒu shù cì， suǒ yǐ shùn xù bù biàn， yí dòng cì shù wéi：
J(n-1)=2^n-2
rán hòu zài yí dòng dàoshǔ dì 'èr gè pán zǐ， yí dòng cì shù wéi 2*J(n-1)+1=2^(n+1)-3，
zuì hòu yí dòng zuì dǐ xià yī gè pán zǐ， suǒ yǐ zǒng de yí dòng cì shù wéi：
K(n)=2*(2*J(n-1)+1)+1=2*(2^(n+1)-3)+1=2^(n+2)-5 |
|
|