۰
subtitle
ارسال: #۱
تست (درخت ها) طراحی الگوریتم سال ۸۹
چون ارتفاع logn است پس مسیر بین u,vباید lognباشد یعنی به ارتفاع بستگی داشته باشد.
(استدلال من)
ولی جواب گزینه ۱می باشد.
ممنون میشم اگه کسی کمک کنه.![[تصویر: 62148_1_1379096101.png]](https://img.manesht.ir/62148_1_1379096101.png)
(استدلال من)
ولی جواب گزینه ۱می باشد.
ممنون میشم اگه کسی کمک کنه.
۰
ارسال: #۲
RE: تست ۸۹ درخت ها
(۱۹ دى ۱۳۹۰ ۰۹:۵۹ ب.ظ)vijay نوشته شده توسط: چون ارتفاع logn است پس مسیر بین u,vباید lognباشد یعنی به ارتفاع بستگی داشته باشد.
(استدلال من)
ولی جواب گزینه ۱می باشد.
ممنون میشم اگه کسی کمک کنه.
![[تصویر: 62150_1_1379096101.png]](https://img.manesht.ir/62150_1_1379096101.png)
فرض کن u گره ای در آخرین سطح سمت چپ ریشه و v گره ای در آخرین سطح سمت راست ریشه یک درخت کامل باشه.
حالا باید در زمان logn پدر u رو پیدا کنیم که همون ریشه هست و در زمان logn فرزند ریشه رو که همون v هستش رو پیدا کنیم.
پس کلا در زمان (O(logn*logn میتونیم مسیر بین u و v رو پیدا کنیم.
البته در بدترین حالت مرتبش اینه. واسه همین از O استفاده کرده.
۰
ارسال: #۳
تست ۸۹ درخت ها
(۱۹ دى ۱۳۹۰ ۱۰:۳۲ ب.ظ)sasanlive نوشته شده توسط: فرض کن u گره ای در آخرین سطح سمت چپ ریشه و v گره ای در آخرین سطح سمت راست ریشه یک درخت کامل باشه.
حالا باید در زمان logn پدر u رو پیدا کنیم که همون ریشه هست و در زمان logn فرزند ریشه رو که همون v هستش رو پیدا کنیم.
پس کلا در زمان (O(logn*logn میتونیم مسیر بین u و v رو پیدا کنیم.
البته در بدترین حالت مرتبش اینه. واسه همین از O استفاده کرده.
خوب این چیزی که شما میگی میشه O(2Logn) و با گزینه دو جور در میاد.
ارسال: #۴
RE: تست ۸۹ درخت ها
(۱۹ دى ۱۳۹۰ ۱۰:۳۸ ب.ظ)pos نوشته شده توسط: خوب این چیزی که شما میگی میشه O(2Logn) و با گزینه دو جور در میاد.
در صورتی حرف شما درسته که بشه همزمان هر دو کارو طی زمانه logn حساب کرد.
ولی اینجا اول باید گره پدر رو پیدا کنیم با زمان logn و دوباره با زمان logn گره فرزند رو پیدا کنبم.نمیشه همزمان این دو کارو انجام داد. اول باید گره پدر رو مشخص کنیم.
پس باید مرتبه‌ها رو ضرب کنیم نه جمع.
۰
ارسال: #۵
تست ۸۹ درخت ها
قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
ارسال: #۶
RE: تست ۸۹ درخت ها
(۱۹ دى ۱۳۹۰ ۱۱:۰۸ ب.ظ)pos نوشته شده توسط: قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
آخره سوال گفته میدانیم هر گره از این درخت به گره های فرزند و گره های پدر دسترسی دارد.
پس میتونه با مرتبه logn گره پدر رو پیدا کنه.
(۱۹ دى ۱۳۹۰ ۱۱:۰۸ ب.ظ)pos نوشته شده توسط: ۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
نگاه کن به ازای هر بار که گره پدر رو به دست میاره باید مسیره گره های فرزندان اونو هم چک کنه. مستقیم نمیره سر ریشه.
ارسال: #۷
RE: تست ۸۹ درخت ها
(۱۹ دى ۱۳۹۰ ۱۱:۰۸ ب.ظ)pos نوشته شده توسط: قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
به نظر پاسخ کامل بود
شکل پیاده سازیش اینجوریه که در یک حلقه For از یک تا logn یک حلقه For دیگه داریم از یک تا logn که در این دو حلقه تک تک مسیرها رو چک می کنیم.
ممکنه در همون ابتدا گره پیدا بشه ممکنه در انتها.
پس مرتبه زمانی( O(logn^2 می باشد
البته اگه استدلالم اشتباهه بگید
۰
ارسال: #۸
RE: تست ۸۹ درخت ها
ببخشید [tex]lg^{2}~n[/tex] میشه [tex]lg~lg~n[/tex] یا [tex]lg~n*lg~n[/tex] ؟؟
ارسال: #۹
RE: تست ۸۹ درخت ها
۰
ارسال: #۱۰
RE: تست ۸۹ درخت ها
بدترین حالت اینه که یه درخت پر رو فرض کنیم. و از چپ ترین برگ رو به عنوان راس u و راست ترین برگ رو به عنوان راس v انتخاب کنیم.
دوستان من اینو حلش کردم ولی جواب رو log^3 n در آوردم.
توضیحات رو توی ضمیمه نوشتم ... بخونید ببینید کجاش غلطه
خب اینم یه راه حله دیگه...!
دوستان من اینو حلش کردم ولی جواب رو log^3 n در آوردم.
توضیحات رو توی ضمیمه نوشتم ... بخونید ببینید کجاش غلطه
خب اینم یه راه حله دیگه...!
۰
ارسال: #۱۱
RE: تست ۸۹ درخت ها
جواب صحیح میشه گزینه ۴، طبق کتاب سنجش،،،
کتاب یوسفی هم در غلطنامه! صفحه آخر، گزینه صحیح نوشته.
کتاب یوسفی هم در غلطنامه! صفحه آخر، گزینه صحیح نوشته.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close