تالار گفتمان مانشت

سلام دوستان میشه راهنمایی کنید که این سوال چطور حل میشه؟خیلی ممنون میشم زود راهنمایی کنید.

(25 خرداد 1395 12:36 ق.ظ)taro.misaki نوشته شده توسط: [ -> ]سلام دوستان میشه راهنمایی کنید که این سوال چطور حل میشه؟خیلی ممنون میشم زود راهنمایی کنید.

اول، حتماً میدونید که اون اعداد داخل FTها چجوری بدست اومدند. با توجه به اینکه ۳۲ تا گره داریم، هر FT ماکزیمم ۵ تا سلول میتونه داشته باشه (log32). بعد، برای هر گره p، داریم:
[tex]FT_p[i]=succ(p+2^{i-1})[/tex]. یعنی اولین گره "فعال" (در شکل‌ها پررنگ رسم شده‌اند) به فاصله‌ی [tex]p+2^{i-1}[/tex] رو می‌نویسیم. لذا برای گره شماره‌ی ۱، داریم:
[tex]FT_1[1]=succ(1+2^0)=succ(2)=4[/tex]
و یا
[tex]FT_1[3]=succ(1+2^2)=succ(5)=9[/tex].

در نهایت، برای پیدا کردن کلید K و فرض اینکه در حال حاضر در گره P قرار داریم، به گره‌ای تعیین شده در ایندکس‌های P می‌رویم که شرط زیر را داشته باشد:
[tex]FT_p[i]\le K<FT_p[i+1][/tex] و تا جایی ادامه می‌دهیم که K کوچکتر از اولین سلول‌های جدول باشد.
در این مثال، با شروع از 21، کلید (17) از اولین سلول یعنی 28 کوچکتر هست لذا جواب همین گره 21 هست!

سؤال خوبی نبود در کل این کلید 17 و شروع از گره 21.
یه مثال دیگه میتونه این باشه که از گره 1 شروع کنیم و دنبال کلید 22 باشیم. در این صورت از 1 به 18 باید بریم. از 18 به 20 باید بریم (چون 22 بین 20 و 28 هست که در سلول شماره‌ی 2 و 3 این گره آورده شده است). از 20 به 21 باید بریم. در 21 میبینیم که سلول اول عدد 28 داره که از کلید ما یعنی 17 بیشتر هست. پس جواب باید بشه این گره (گره 21). اما یک شرط دیگه هم هست اونم اینکه اگه کلید، از گره بزرگتر باشه، به اولی سلول از اون گره هم منتقل می‌شیم. در اینجا، کلید 22 هست که از گره جواب، یعنی 21، بزرگتر هست. پس به اولین سلول گره 21، یعنی 28 میریم. پس جواب نهایی میشه گره 28. منتهی در مثال قبلی، 17 از 21 بزرگتر نبود و در همون گره 21 توقف کردیم.

همانطور که مشخص هست، در سؤال اصلی (کلید 17 شروع از 21) حق نداریم به خونه‌ی 9 بریم چون در این صورت توو مثالی که بالا آوردم هم بعد از رسیدن به این گره، باید برای جستجوی کلید 22 به به 9 بریم که توو لوپ می‌افته.