اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!

ورود ثبت‌نام راهنما درباره‌ی کاهو
پرسش‌ها برچسب‌ها کاربر‌ها سوال بپرسید!

آمار پرسش:

  • پرسیده شده: 2015-06-27 08:11:28 -0500
  • مشاهده شده: 631 بار
  • بروز شده: 2015-07-01 05:58:57 -0500

پرسش‌های مشابه:

آیا گراف قویا همبند است؟

پیدا کردن مولفه های قویا همبند گراف جهت دار

انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز

یافتن کوتاه ترین دور در گراف ساده

کد برای بررسی یک ریختی 2 گراف

جزوه ی برنامه نویسی قسمت (گراف)

پيدا كردن دومين كوتاهترين مسير بين دو راس گراف با توجه به الگوريتم ديكسترا

ثابت کنید تعداد درخت هایی که دو راس دارند که اختلاف جمع فاصله هایشان دقیقا 1 است فرد است

شبکه $n\times n$ پایدار

پیدا کردن گراف دوبخشی کامل یکرنگ

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

پیدا کردن راسی در درخت که دارای فاصله ی مینیمم است

2

فکر می کنم که این خیلی معروفه.یه درخت داریم که تو ورودی داده می شه.بعد به هر راس یه عدد اختصاص می دیم که فاصله ی دورترین راس از اونه.حالا بین عدد های اختصاص یافته به راس ها مینیمم رو پیدا کنید.

واسه ی این مثال جواب می شه 2.چون راس 3 از دورترین راس نسبت به خودش 2 تا فاصله داره.

این هم از کد خودم که اصلن بهینه نیست .

گراف درخت الگوریتم
2015-06-27 08:11:28 -0500
آرپا 947 ● 13 ● 15 ● 31
پاک‌کردن   ویرایش سوال
نظرات

منیموم فک کنم یکشه مطمعنن نیستما

2015-06-27 09:57:41 -0500 رصاوووو

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

2015-06-27 11:17:22 -0500 محمد خداداد

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

2015-06-27 11:21:36 -0500 محمد خداداد

2 تا dfs فک کنم بخواد

2015-06-27 11:27:29 -0500 چشمک

dfs چیست؟؟؟؟

2015-06-27 12:23:50 -0500 محمد خداداد

3 پاسخ

5

توی هر درخت یا یک راس این ویژگی رو داره یا دو راس مجاور. (اثباتش با خودتون)

.


راه حل اول: $\impliedby$ (O(n

الگوریتم:

۱)در درخت فعلی تمام برگ ها رو حذف کن.

۲) اگر کمتر از ۳ راس باقی مانده بود به ۴ برو.

۳) به ۱ برو.

۴) (راس/رئوس) باقی مانده جواب مسئله هستند.

$\impliedby$ لینک کد


راه حل دوم: $\impliedby$ (O(n

الگوریتم :

۱) از راسی دلخواه Dfs اجرا رو اجرا کن و روی هر راس فاصله آن راس تا راس انتخاب شده رو بنویس.

۲) راسی که بیشترین عدد روی آن نوشته شده را a1 بنام.

راس a1 حتما یکی از دو سر قطر گراف است‌. (اثباتش با خودتون)

۳) از راس Dfs , a1 اجرا رو اجرا کن و روی هر راس فاصله آن راس تا راس a1 رو بنویس.

4) راسی که بیشترین عدد روی آن نوشته شده را a2 بنام.

رئوس a1 و a2 دو سر قطر گراف هستند. (واضحه چرا)

۵) رئوس قطر گراف رو با ۰ تا m شماره گذاری کن.

۶) درصورتی که m فرد بود رئوس $\lfloor m/2 \rfloor$ و $\lceil m/2 \rceil$ جواب مسئله هستند.

۷) در صورتی که m زوج بود راس $m/2$ جواب مسئله هست.

2015-06-27 12:40:12 -0500
ایمان خان 1250 ● 21 ● 24 ● 36
پاک‌کردن   ویرایش پاسخ
نظرات

ایمان خان شماره راس نخواسته فقط مقدار مینیمم رو خواسته.

2015-06-27 19:01:08 -0500 کنکوری

کلیشو گفتم بقیش ریزه کاریه مثلا تو الگوریتم اول کافیه یه متغیر رو توی مرحله ۳ مقدارش رو زیاد کنی.

2015-06-27 19:12:54 -0500 ایمان خان

الگوریتم ها هر دوتاشون خیلی عالین.تشکر.به زودی کد هر دو تا رو می زنم می ذارم اینجا.

2015-06-27 21:17:35 -0500 آرپا
2

میشه یه کار قوی تر کرد که به ازای هر راس دورترین راس نسبت بهش رو پیدا کرد. اول با یه DFS واسه هر راس دور ترین راس زیرشو پیدا میکنیم سپس واسه هر راس با توجه به دور ترین راس پدرش میشه دور ترین راس خودشو پیدا کرد $^_^$

2015-06-27 21:43:49 -0500
مرغ تخم یخ سیبیل سیگار 64 ● 3
پاک‌کردن   ویرایش پاسخ
نظرات

فکر کنم منظور سوال رو اشتباه فهمیدی!

2015-06-29 03:54:20 -0500 توفیقی

خیلی کار بیهوده ایه کدش الکی زیاد میشه

2015-06-30 16:10:41 -0500 موسول

‌دقیقن کار درستی داره می‌کنه :) هیچ مشکلی هم نداره. اگه نمی‌فهمین که چی کار داره می‌کنه مشکل از شماست!

2015-07-01 06:31:27 -0500 احسان

@احسان خوب من درست سوال رو متوجه نشده بودم! :) درسته حرف @مرغ تخم یخ سیبیل سیگار :)

2015-07-01 20:19:18 -0500 توفیقی

البته شاید هم درست نباشه، دوباره دارم بهش فکر میکنم مثال نقض میخوره...

2015-07-01 20:23:16 -0500 توفیقی
1

خب گفتم کدشو بزنم و بزارم اینجا که ملت استفاده کنن :) از روش ایمان خان استفاده کردم یعنی این:

۱)در درخت فعلی تمام برگ ها رو حذف کن.

۲) اگر کمتر از ۳ راس باقی مانده بود به ۴ برو.

۳) به ۱ برو.

۴) (راس/رئوس) باقی مانده جواب مسئله هستند.

5)گراف را باز سازی کن و فاصله ی این راس(ها) را تا دور ترین راسشان پیدا کن و به عنوان خروجی بده.

این هم ازلینک کد

2015-06-29 23:28:10 -0500
آرپا 947 ● 13 ● 15 ● 31
پاک‌کردن   ویرایش پاسخ
نظرات

خیله خوبه :)

2015-07-01 03:46:57 -0500 ایمان خان

منم کدشون گذاشتم ولی گراف رو باز سازی نمیکنم :)

2015-07-01 04:53:18 -0500 ایمان خان

پاسخ شما

فقط در صورتی که پاسخی برای این پرسش دارید، آن را اینجا بنویسید و برای بحث کردن از قسمت «ثبت‌ نظر» استفاده کنید. شما می‌توانید قبل از وارد شدن به سایت پاسخ خود را بنویسید. این پاسخ ذخیره می‌شود و زمانی که شما وارد سایت شدید یا ثبت‌نام کردید منتشر می‌شود.

پیش‌نمایش:

کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر است.