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 است.
ببخشید من تو پست قبلی با این عنوان یک اشتباه تو اثبات این سوال داشتم ولی به هر حال در این پست مجددا اشتباه بودن کلید اولیه این سوال رو اثبات کردم.
سوال 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 است.