C++递归问题,流程,意思
说得好可以追加分数,谢谢了!
我想问的是递归运算的流程是怎么样的?请详讲!谢谢!
主要想问下面程序中:
hanio(num-1,aa,cc,bb);//这句是什么意思?里面的参数是代表什么?什么意思?
cout<<"移动第"<<num<<"的盘 从"<<aa<<"柱到"<<cc<<"柱\n";
hanio(num-1,bb,aa,cc);//这句是什么意思?里面的参数又是代表什么?什么意思?
//下面是一个河内塔问题。
#include<iostream.h>
void hanio(int num,char aa,char bb,char cc)
{
if(num>0)
{
hanio(num-1,aa,cc,bb);
cout<<"移动第"<<num<<"的盘 从"<<aa<<"柱到"<<cc<<"柱\n";
hanio(num-1,bb,aa,cc);
}
return;
}
void main()
{
int num;
cout<<"请输入共需移动多少个盘(>0):";
cin>>num;
hanio(num,'A','B','C');
return;
}
追问:可以再细说一下这三句吗? hanio(num-1,aa,cc,bb);//这里cc和bb,换了位置,用处/意思是什么?为什么要换位?
cout<<"移动第"<<num<<"的盘 从"<<aa<<"柱到"<<cc<<"柱\n";
hanio(num-1,bb,aa,cc);//这里cc和bb,换了位置,用处/意思是什么?为什么要换位?
答案:main函数不管,关键在于递归函数。递归函数调用自己,将同样的问题细分。
汉诺塔的移动盘子的问题可以细分为多个相似的子问题。首先,你要明白,这个问题划分,是如何划分的。就本题而言,我们需要将num个盘子从A移动到C,需要B作为中介。那么,A中最大的盘子必然是要放在C上的。你可以假想,我们移动盘子的时候,到了眼下这一步:A中只留下了最大的盘子,其余盘子由小到大依次放在了B上,C上为空。接下来的一步为,将A上的盘子移动到C上。
此时的柱子上的盘子情况为,A :空;B:由小到大(num-1)个;C: 最大的盘子。
接下来,要将B上的最大的盘子,放到C上,A作为中介。这个问题,就是刚才我们解决的问题的子问题了,结果为,A:由小到大(num-2)个;B:空;C,两个盘子。
它们的解决方法是一样的,只是问题规模在逐渐缩小。
递归解决问题的思路与我们正常解决问题的思维方式有点不同,它先从眼前最大规模的问题(本题即为:先将最大的盘子移动到C上)进入递归函数,然后才一步步地细分。
void hanio(int num,char aa,char bb,char cc)
{
if(num>0)
{
hanio(num-1,aa,cc,bb); //在做下一步时,首先要将本柱子上的其他盘子移到中介柱子上,只留下最大的盘子(<num>个盘子中,最大的一个盘子。)。可以理解为:aa借助cc移动到bb上。
cout<<"移动第"<<num<<"的盘 从"<<aa<<"柱到"<<cc<<"柱\n"; //这一步就是移动最大的盘子到目的柱子上。
hanio(num-1,bb,aa,cc); //这一步是将其他的盘子从中介柱子上移动到刚才最大盘子所在的柱子上。可以理解为:bb借助aa移动到cc上。
}
} //我所说的中介柱子,目的柱子,都是每个子问题对应的。例如刚才所说的情况:A :空;B:由小到大(num-1)个;C: 最大的盘子。这时,A就是中介柱子,而不是B。
不晓得我说的这些你能看明白不。这是我对递归的理解。写个简单的递归函数吧,比如,整数num的阶乘。
递归分解为 num!=num*(num-1)!,然后(num-1)!=(num-1)*(num-2)!,以此类推。
当然,这个问题可以一个for/while循环解决。。。。我只是在举例说明递归函数如何分解子问题。
int result(int num)
{
if(num>1)
return num*result(num--);
else
return 1;
}
我个人C学的不是很好,但是希望对你有所帮助。如有错误,请指正。
递归即一个函数自己调用自己,在这里就是hanio调用自己。可以看到在hanio的代码中又调用了hanio函数自己。
注意:
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。(否则程序会没有终点,无限制的递归下去,直到计算资源或者递归堆栈资源用尽。)
算法介绍:
一位美国学者发现一种出人意料的简单方法,只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上,根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放 A B C;
若n为奇数,按顺时针方向依次摆放 A C B。
(1)按顺时针方向把圆盘1从现在的柱子移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;若圆盘1在柱子B,则把它移动到C;若圆盘1在柱子C,则把它移动到A。
(2)接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘。这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。
(3)反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。
hanio(num-1,aa,cc,bb);//即执行(1)操作
hanio(num-1,bb,aa,cc);//即执行(2)操作
上面两句就是递归的实质。
num-1:代表递归进行的次数,而递归退出的条件就是递归中的某一次hanio函数接受的参数:num为零,if(num>0)不执行而执行后面的return;(递归结束条件,即递归出口)
aa,cc,bb:注意他们的排列顺序,就是这个顺序完成了(1)操作。
bb,aa,cc:同上,这个顺序完成了(2)操作。
递归的思想是逐渐化大为小,并自身循环。就像剥洋葱,最终把问题层层分解,落脚在小问题上。
这是个汉诺塔的问题,实现了汉诺塔问题的步骤解析。(就是说它会输出你应如何放盘) void hanio(int num,char aa,char bb,char cc)这句话是在 定义函数。hanio是函数名,里面的是函数参数,分别是整型和三个字符型。 我来详细解答吧。唉,好困了
void hanio(int num,char aa,char bb,char cc)//定义函数
{
if(num>0)
{
hanio(num-1,aa,cc,bb);
cout<<"移动第"<<num<<"的盘 从"<<aa<<"柱到"<<cc<<"柱\n";
hanio(num-1,bb,aa,cc);
}
return;
}//有“num”个盘,三个柱(aa,cc,bb).没执行一次函数,num就自减1,输出走法。注意,aa,bb,cc在执行时是变动的,以此实现不同走法。你注意到他的循环了吗?知道num减为0才停止。哈哈,这就是神奇的递归!
void main()//这是主函数,要先看主函数,才明白在干什么
{
int num;
cout<<"请输入共需移动多少个盘(>0):"; //这是汉诺塔的级别了
cin>>num;
hanio(num,'A','B','C');//函数声明
return 0;
}
楼主觉得满意就采纳吧,我在完成任务,感谢你的支持!
上一个:C++鍏ラ棬锛岃鐪嬪摢鏈功锛?- 宸茶В鍐?- 鎼滄悳闂棶
下一个:那种C++编译软件和Win7兼容?