زمان کنونی: ۰۸ آذر ۱۳۹۹, ۱۱:۴۷ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تست (درخت ها) طراحی الگوریتم سال ۸۹

ارسال:
  

vijay پرسیده:

تست (درخت ها) طراحی الگوریتم سال ۸۹

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

۰
ارسال:
  

sasanlive پاسخ داده:

RE: تست ۸۹ درخت ها

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

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

۰
ارسال:
  

pos پاسخ داده:

تست ۸۹ درخت ها

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

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

ارسال:
  

sasanlive پاسخ داده:

RE: تست ۸۹ درخت ها

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

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

۰
ارسال:
  

pos پاسخ داده:

تست ۸۹ درخت ها

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

ارسال:
  

sasanlive پاسخ داده:

RE: تست ۸۹ درخت ها

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

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

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

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

ارسال:
  

مازیار صفایی پاسخ داده:

RE: تست ۸۹ درخت ها

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

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

۰
ارسال:
  

Ali-B پاسخ داده:

RE: تست ۸۹ درخت ها

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

ارسال:
  

sasanlive پاسخ داده:

RE: تست ۸۹ درخت ها

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

[tex]lg~n*lg~n[/tex]
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۰
  

variant20002000 پاسخ داده:

RE: تست ۸۹ درخت ها

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


فایل‌(های) پیوست شده
asd.docx
اندازه فایل: ۴۸/۶۳ KB

۰
ارسال: #۱۱
  

Ali-B پاسخ داده:

RE: تست ۸۹ درخت ها

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۳,۷۰۰ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri
  مرتبه ایجاد درخت rad.bahar ۱ ۱۴۵ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۳ ۲۰۷ ۱۱ مهر ۱۳۹۹ ۰۳:۴۷ ب.ظ
آخرین ارسال: عزیز دادخواه
  عمق درخت ???? rad.bahar ۱ ۱۷۰ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  سوال درباره طراحی سایت و جدول ahantell ۰ ۲۱۶ ۰۲ مرداد ۱۳۹۹ ۱۰:۴۳ ق.ظ
آخرین ارسال: ahantell
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۳,۱۷۹ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  طراحی سایت شرکتی ideasoft98 ۰ ۱۲ ۲۶ اسفند ۱۳۹۸ ۰۲:۵۶ ب.ظ
آخرین ارسال: ideasoft98
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۶۱۶ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t
  تعداد درخت فراگیر ss311 ۰ ۴۴۴ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  تاثیر بودجه در انتخاب شرکت طراحی سایت wone ۱ ۲۰ ۲۳ آبان ۱۳۹۸ ۰۱:۱۴ ب.ظ
آخرین ارسال: xiaomi

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close