همچنین:
فصل ششم صفحه 271 مسئله 19 از کتاب ساختمان داده لیپ شوتز:
حل مسئله برج هاي هانوي را تغيير دهيد به طوري که به جاي دو صدا زدن بازگشتي فقط يک صدا زدن بازگشتي داشته باشيم.
مي توان محورهاي (ميله هاي) A و B را قرينه يکديگر فرض کرد. به اين صورت که گام هاي ذيل را انجام دهيم.
N-1 ديسک از A به B انتقال يابد و بعد داشته باشيم A↑C
تعویض A با B
N-2 ديسک از A به B انتقال يابد و بعد داشته باشيم B↑C
تعویض A با B
N-3 ديسک از A به B انتقال يابد و بعد داشته باشيم A↑C
تعویض A با B
N-4 ديسک از A به B انتقال يابد و بعد داشته باشيم B↑C
تعویض A با B
و به همين ترتيب. بنابراين ما مي توانيم يک صدا زدن بازگشتي را تکرار کرده و در هر بار BEG و AUX را جابجا نماييم و رويه ذيل با توجه به توضيحات فوق حاصل مي شود.
TOWER(N,BEG,AUX,END)
1.If N=0 then: RETURN
2.Call tower(k-1.beg,end,aux.)
4.Write: BEG -> END.
5.BEG with AUX
Set TEMP:=BEG:=AUX.AUX:=TEMP.
[End of step 2 loop.]
6.Return
مشاهده مي کنيد به جاي
N=1
از
N=0
بعنوان ملاک بازگشت استفاده کرده ايم. هر کدام از آنها مي توانند براي بدست آوردن جواب مورد استفاده قرار گيرند.
پاسخ با نقل قول