کنکور سال۷۳ - نسخه‌ی قابل چاپ

کنکور سال۷۳ - Elham_tm - 03 فروردین ۱۳۹۶ ۰۱:۰۷ ب.ظ بچه ها من متوجه نمیشم چ جوری این الگوریتم روtraceکنم ک ب جواب برسم.هربار ب یه جواب مختلف میرسم.ممنون میشم اگر کسی کمکم کنه

RE: کنکور سال۷۳ - msour44 - 03 فروردین ۱۳۹۶ ۰۹:۰۰ ب.ظ سلام برای پاسخ به این چنین سوالات ورودی مسئله را کوچکتر فرض می کنند مثلا در اینجا درخت را کمی ساده می کنیم اگر فقط ریشه(A) و فرزندان ریشه (B,C,D,E)را درنظر بگیریم وبه جای اینکه y به نود P اشاره کند (فرض مسئله)به یکی از فرزندان A مثلا B اشاره کند بعد که تابعfind را اجرا کنیم جایی که Y به انجا اشاره می کند پارامتر x هم به اونجا اشاره می کند (یعنی هر دو به B اشاره می کنند) t هم که به ریشه اشاره می کند بعد دو متغیر محلی q,r تعریف می شود و با دستور[tex]q=t . down[/tex] جایی که فیلد لینک پایینt (ریشه ) به اونجا اشاره می کند q هم به انجا اشاره کند یعنی q به B اشاره می کند بعد حلقه while اجرا ودستور[tex]if\: q=x\: then\: return(t)[/tex] که x طبق فرض ما به جایی که y (اشاره گر به B) اشاره میکند اشاره می کردو q هم که به B اشاره می کند پس شرط if درست وreturn اشاره گر t که به ریشه(A ) اشاره می کند را بر می گرداند. حال اگر y به جای اشاره به B به c اشاره کند.دوباره با اجرای تابع q به پایین ریشه یعنی b اشاره می کندحلقه اجرا شرط if برقرار نیست(چون x هم مثل y به c اشاره می کند)پس else اجرا می شود که داخل ان تابع به صورت بازگشتی فراخوانی می شود طوری که این بار ریشه q (اشاره گر به b) است باید توجه کرد که دستور if بعد فراخوانی وارد پشته می شود تا بعد بازگشت اجرا شودحال اگر به اجرا ادامه دهیم یک q محلی دیگر به پایین b اشاره می کند که در درخت فرضی ما تهی است پس شرط while نقض و دستور return اخر تابع مقدار nil خروجی تابع تولید می شود که در r ذخیره می شود پس از بازگشت از فراخوانی دستور [tex]if\: r <>nil\: then\: return(r ) \: else\: q:=q.right[/tex] اجرا می شود چون r حاوی nil است پس else اجرا و q به راست خود یعنی C اشاره می کند حلقه while تکرار می شود و در [tex]if\: q=x\: then\: return(t)[/tex] شرط برقرار و t برگردانده می شود(اشاره گر به A) تا اینجا هم می توان حدس زد که تابع find اشاره گر به پدر Y را برمی گرداند یعنی اگر طبق فرض مسئله Y به P اشاره کند اشاره گر به پدرش یعنی i را بر می گرداند یعنی گزینه ۳ در واقع q در عمق حرکت می کند تا به nil برسد بعد به راست حرکت می کند ودرصورت نتیجه نگرفتن بازگشت به عقب و حرکت به راست در سطی بالاتر... باید به بازگشتی دقت کنید.(یه شباهتی به پیمایش preorder هم دارد).