تالار گفتمان مانشت
تست (درخت ها) طراحی الگوریتم سال ۸۹ - نسخه‌ی قابل چاپ

تست (درخت ها) طراحی الگوریتم سال ۸۹ - vijay - 19 دى ۱۳۹۰ ۰۹:۵۹ ب.ظ

چون ارتفاع logn است پس مسیر بین u,vباید lognباشد یعنی به ارتفاع بستگی داشته باشد.
(استدلال من)
ولی جواب گزینه ۱می باشد.
ممنون میشم اگه کسی کمک کنه.[تصویر:  62148_1_1379096101.png]

RE: تست ۸۹ درخت ها - sasanlive - 19 دى ۱۳۹۰ ۱۰:۳۲ ب.ظ

(۱۹ دى ۱۳۹۰ ۰۹:۵۹ ب.ظ)vijay نوشته شده توسط:  چون ارتفاع logn است پس مسیر بین u,vباید lognباشد یعنی به ارتفاع بستگی داشته باشد.
(استدلال من)
ولی جواب گزینه ۱می باشد.
ممنون میشم اگه کسی کمک کنه.[تصویر:  62150_1_1379096101.png]

فرض کن u گره ای در آخرین سطح سمت چپ ریشه و v گره ای در آخرین سطح سمت راست ریشه یک درخت کامل باشه.
حالا باید در زمان logn پدر u رو پیدا کنیم که همون ریشه هست و در زمان logn فرزند ریشه رو که همون v هستش رو پیدا کنیم.
پس کلا در زمان (O(logn*logn میتونیم مسیر بین u و v رو پیدا کنیم.
البته در بدترین حالت مرتبش اینه. واسه همین از O استفاده کرده.

تست ۸۹ درخت ها - pos - 19 دى ۱۳۹۰ ۱۰:۳۸ ب.ظ

(۱۹ دى ۱۳۹۰ ۱۰:۳۲ ب.ظ)sasanlive نوشته شده توسط:  فرض کن u گره ای در آخرین سطح سمت چپ ریشه و v گره ای در آخرین سطح سمت راست ریشه یک درخت کامل باشه.
حالا باید در زمان logn پدر u رو پیدا کنیم که همون ریشه هست و در زمان logn فرزند ریشه رو که همون v هستش رو پیدا کنیم.
پس کلا در زمان (O(logn*logn میتونیم مسیر بین u و v رو پیدا کنیم.
البته در بدترین حالت مرتبش اینه. واسه همین از O استفاده کرده.

خوب این چیزی که شما میگی میشه O(2Logn) و با گزینه دو جور در میاد.

RE: تست ۸۹ درخت ها - sasanlive - 19 دى ۱۳۹۰ ۱۰:۵۲ ب.ظ

(۱۹ دى ۱۳۹۰ ۱۰:۳۸ ب.ظ)pos نوشته شده توسط:  خوب این چیزی که شما میگی میشه O(2Logn) و با گزینه دو جور در میاد.

در صورتی حرف شما درسته که بشه همزمان هر دو کارو طی زمانه logn حساب کرد.
ولی اینجا اول باید گره پدر رو پیدا کنیم با زمان logn و دوباره با زمان logn گره فرزند رو پیدا کنبم.نمیشه همزمان این دو کارو انجام داد. اول باید گره پدر رو مشخص کنیم.
پس باید مرتبه‌ها رو ضرب کنیم نه جمع.

تست ۸۹ درخت ها - pos - 19 دى ۱۳۹۰ ۱۱:۰۸ ب.ظ

قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه

RE: تست ۸۹ درخت ها - sasanlive - 20 دى ۱۳۹۰ ۱۲:۰۵ ق.ظ

(۱۹ دى ۱۳۹۰ ۱۱:۰۸ ب.ظ)pos نوشته شده توسط:  قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.

آخره سوال گفته میدانیم هر گره از این درخت به گره های فرزند و گره های پدر دسترسی دارد.
پس میتونه با مرتبه logn گره پدر رو پیدا کنه.

(۱۹ دى ۱۳۹۰ ۱۱:۰۸ ب.ظ)pos نوشته شده توسط:  ۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه

نگاه کن به ازای هر بار که گره پدر رو به دست میاره باید مسیره گره های فرزندان اونو هم چک کنه. مستقیم نمیره سر ریشه.

RE: تست ۸۹ درخت ها - Ali-B - 20 دى ۱۳۹۰ ۱۲:۱۵ ق.ظ

ببخشید [tex]lg^{2}~n[/tex] میشه [tex]lg~lg~n[/tex] یا [tex]lg~n*lg~n[/tex] ؟؟

RE: تست ۸۹ درخت ها - sasanlive - 20 دى ۱۳۹۰ ۱۲:۲۷ ق.ظ

(۲۰ دى ۱۳۹۰ ۱۲:۱۵ ق.ظ)Ali-B نوشته شده توسط:  ببخشید [tex]lg^{2}~n[/tex] میشه [tex]lg~lg~n[/tex] یا [tex]lg~n*lg~n[/tex] ؟؟

[tex]lg~n*lg~n[/tex]

RE: تست ۸۹ درخت ها - مازیار صفایی - ۲۰ دى ۱۳۹۰ ۱۲:۰۴ ب.ظ

(۱۹ دى ۱۳۹۰ ۱۱:۰۸ ب.ظ)pos نوشته شده توسط:  قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه

به نظر پاسخ کامل بود
شکل پیاده سازیش اینجوریه که در یک حلقه For از یک تا logn یک حلقه For دیگه داریم از یک تا logn که در این دو حلقه تک تک مسیرها رو چک می کنیم.
ممکنه در همون ابتدا گره پیدا بشه ممکنه در انتها.
پس مرتبه زمانی( O(logn^2 می باشد
البته اگه استدلالم اشتباهه بگیدWink

RE: تست ۸۹ درخت ها - variant20002000 - 24 دى ۱۳۹۰ ۱۲:۱۶ ق.ظ

بدترین حالت اینه که یه درخت پر رو فرض کنیم. و از چپ ترین برگ رو به عنوان راس u و راست ترین برگ رو به عنوان راس v انتخاب کنیم.
دوستان من اینو حلش کردم ولی جواب رو log^3 n در آوردم.
توضیحات رو توی ضمیمه نوشتم ... بخونید ببینید کجاش غلطه
خب اینم یه راه حله دیگه...!Big Grin

RE: تست ۸۹ درخت ها - Ali-B - 30 دى ۱۳۹۰ ۰۸:۳۹ ب.ظ

جواب صحیح میشه گزینه ۴، طبق کتاب سنجش،،،
کتاب یوسفی هم در غلطنامه! صفحه آخر، گزینه صحیح نوشته.