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

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

ارسال:
  

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: تست ۸۹ درخت ها

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۴۰ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  [دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی هاتف ۳۳ ۴۰,۸۰۵ ۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ
آخرین ارسال: solmaz58
  طراحی ui/ux kimiya1234 ۲ ۲,۰۱۲ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۶ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  طراحی یک سیستم عامل (از صفر) sina4everafter ۱۲ ۱۵,۶۲۸ ۰۶ بهمن ۱۳۹۹ ۱۲:۵۳ ب.ظ
آخرین ارسال: nahalmomen2007@yahoo.com
  طراحی سایت ریسپانسیو wikidemy1 ۰ ۱,۶۰۳ ۱۳ دى ۱۳۹۹ ۰۴:۰۱ ب.ظ
آخرین ارسال: wikidemy1
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  تشریح تست همروندی - بررسی یکی از سوالات سال ۸۲ abji22 ۵ ۴,۶۲۷ ۰۲ دى ۱۳۹۹ ۱۱:۰۵ ق.ظ
آخرین ارسال: mohammadasadi1
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۱,۴۸۴ ۳۰ آذر ۱۳۹۹ ۰۸:۲۴ ب.ظ
آخرین ارسال: amir.m5560@gmail.com

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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