PDA

View Full Version : سوال 33. طراحی الگوریتم کنکور کارشناسی ارشد88



manager
پنج شنبه 08 اسفند 1387, 21:08 عصر
HTML clipboardسلام


ببخشید من تو پست قبلی با این عنوان یک اشتباه تو اثبات این سوال داشتم ولی به هر حال در این پست مجددا اشتباه بودن کلید اولیه این سوال رو اثبات کردم.



سوال 33. فرض کنید T یک درخت دودوئی کامل با n گره و به ارتفاع logn می باشد. می خواهیم یک مسیر از یک راس u به یک راس دیگر v بیابیم. گره های u و v داده شده اند و می دانیم که هر گره به گره های فرزند و گره های پدر دسترسی دارد.

در این سوال ذکر شده که T یک درخت دودوئی کامل هست خوب من دو تا فرض رو در نظر می گیرم 1- طراح منظورش این بوده که درخت رو در آرایه می تونیم نگه داریم و از این طریق می تونیم به شاخص هر گره دسترسی داشته باشیم پس مثلا u.index و v.index در دسترس است. منظورم از index شماره خانه ی آرایه ای ست که درخت در آن نگه داری می شود. لذا اگر u.index<v.index باشه می تونیم نتیجه بگیریم که گره u و v یا هم سطح هستند یا گره u در عمق کمتری نسبت به v قرار داره. خوب فرض اول یک فرض خاصه که به نظر مردم می تونه در حالت کلی درست نباشه مثلا هنگامی که از لیست پیوندی استفاده بشه. اما پاسخ این سوال با این فرض به قرار زیره :
الگوریتم زیر را به کار می بریم :


int ui,vi;
Stack pu,pv;

ui=u.index;
vi=v.index;

while(ui!=0 && vi!=0 && ui!=vi)
{
if(ui>vi)
{
pu.push(ui);
ui/=2;
}
else if(ui<vi)
{
pv.push(vi);
vi/=2;
}
else if (ui==vi)
break;
}

در انتهای الگوریتم pi=vi در حقیقت پدر مشترک گره های u و v است و مسیر u در پشته pu و مسیر v در پشته pv ذخیره شده. به صراحت مشخصه که مرتبه زمانی این الگوریتم حداکثر logn است.

اما فرض دوم که یک الگوریتم کلی برای تمام درخت هاست. در این الگوریتم ما مسیر u و v را در دو پشته جدا گانه بدست می آوریم و قسمت مشترک را به جز جد مشترک از آن دو حذف می کنیم. بدین صورت می توانیم بزرگترین جد مشترک گره های u و v را یافته و مسیر به u و مسیر به v را بیابیم. الگوریتم زیر رو می تونیم برای این کار استفاده کنیم.



Stack<int> pu = new Stack<int>();
Stack<int> pv = new Stack<int>();

// Computing path of u and v

p = u;
while(p!=root)
{
pu.Push(p);
p = parent(p);
}

p = v;
while (p != root)
{
pv.Push(p);
p = parent(p);
}

int cp = -1; // Common Parent
while (pu.Peek() == pv.Peek())
{
cp = pu.Pop();
pv.Pop();
}



در انتها مسیر u در پشته pu و مسیر v در pv و جد مشترک آنها در cp قرار خواهد داشت. پر واضحه که الگوریتم فوق عضو مرتبه زمانی logn است.

pesar irooni
جمعه 09 اسفند 1387, 17:15 عصر
اینو به سازمان سنجش نگی هاااااااااا
حالا ما یه سوال درست حل کردیم گیر دادی به اون. برو سراغ مشترک ها

hossein taghi zadeh
جمعه 09 اسفند 1387, 18:06 عصر
با سلام

در مورد اين سوال گزينه‌ي درست همون log n هست.
الگوريتم من:

1. براي گره‌ي u، تا رسيدن به ريشه بالا مي‌رويم و مشخصات اين اجداد را در يك ليست پيوندي دوطرفه درج مي‌كنيم. (پيچيدگي در بدترين حالت log n)

2. براي گره‌ي v، تا رسيدن به ريشه بالا مي‌رويم و مشخصات اين اجداد را در يك ليست پيوندي دوطرفه درج مي‌كنيم. (پيچيدگي در بدترين حالت log n)

3. از انتهاي هر دو ليست پيوندي، دو عنصر آخر دو ليست در صورتيكه يكسان باشند حذف مي‌كنيم و در يك متغير موقتي ذخيره مي‌كنيم و اينكار را تا زمانيكه به دو عنصر متفاوت برسيم، انجام مي‌دهيم. (پيچيدگي در بدترين حالت log n)

4. با يافتن اولين جد مشترك دو گره، در مرحله‌ي قبل، آن را به انتهاي ليست پيوندي گره‌ي u، اضافه كرده و ليست پيوندي گره‌ي v را نيز به انتهاي اين ليست اضافه مي‌كنيم.

pesar irooni
شنبه 10 اسفند 1387, 00:32 صبح
توجه کنید در هر دو روش ما به ساختمان داده های کمکی نیاز داریم، اما در روش اصلی که به ازای هر بار بالارفتن U ، V تا ریشه یا رسیدن به V بالا می رود هیچ چیز نمیخواهیم.

Developer Programmer
شنبه 10 اسفند 1387, 09:19 صبح
ا يافتن اولين جد مشترك دو گره، در مرحله‌ي قبل، آن را به انتهاي ليست پيوندي گره‌ي u، اضافه كرده و ليست پيوندي گره‌ي v را نيز به انتهاي اين ليست اضافه مي‌كنيجد مشترک ؟! ممکنه توضیح بدی؟ متوجه نشدم.
خوب وقتی از گره V رسیدی به ریشه، بعد از گره U رسیدی به ریشه حالا یه مسیر از V به U داری... غیر از اینه؟

راستی، من لینک کلیدهای سنجش رو پیدا نکردم، ممنون میشم لینکش رو بدید.

manager
شنبه 10 اسفند 1387, 13:24 عصر
توجه کنید در هر دو روش ما به ساختمان داده های کمکی نیاز داریم، اما در روش اصلی که به ازای هر بار بالارفتن U ، V تا ریشه یا رسیدن به V بالا می رود هیچ چیز نمیخواهیم.
در روش اول نداریم !! در روش اول ما نیازی به ساختمان داده اضافی نداریم و اینکه وجود کلمه درخت کامل در صورت سوال رو توجیه می کنه !

منظور از جد مشترک جدی از دو گره uوv که بیشترین عمق رو داره. مثلا فرض کنید u و v در زیر درخت سمت چپ ریشه باشند. اونوقت جد مشترک این دو تا گره دیگه ریشه نیست و ریشه زیر درخت سمت چپ هستش. مثل اینکه طراح منظورش کوتاه ترین مسیر بوده ....

manager
شنبه 10 اسفند 1387, 21:41 عصر
خیلی رو این سوال فکر کردم که منظور طراح رو بفهمم، کم کم دارم نتیجه می گیرم حق با PesarIrooni هستش و منظور طراح الگوریتم ابلهانه ایه که مرتب زمانیش log^2n هستش... اگر اعتراض به این سوال به حد نساب همون کلید جواب غلط تائید می شه...