چند تا سؤال دیگه
نتایج مرحله اول هم اعلام شد. امیدوارم خودتون از نتیجه راضی باشید و به همه‌ی کسایی هم که قبول شدن تبریک می‌گم.
بهتره که کم‌کم جو مرحله ۲ رو به خودتون بگیرید! برای همین احتمالاً یه مدت کمتر طرف برنامه‌نویسی می‌ریم و بیشتر مطلب/سؤال تئوری (گراف، ترکیبیات و الگوریتم) می‌ذاریم.
برای این دفعه، یه سری سؤال هست که یا جدیده، یا احتمال اینکه دیده باشید کمتره.
در مورد همه‌ی سؤال‌ها پیشنهاد می‌کنم قبل از اینکه به راهنمایی نگاه کنید، حداقل یک ساعت بهش فکر کرده باشید.
در ضمن، برای کسانی که علاقه‌مند به شرکت در مسابقات برنامه‌نویسی هستن، دبیرستان علامه حلی ۳ تهران با همکاری فرزانگان ۲ تهران، تصمیم دارن مسابقات حلی‌کامپ رو برگزار کنن. تا جایی که من می‌دونم مسابقات توی دو مرحله‌ی آنلاین و حضوری و دو سطح راهنمایی و دبیرستان برگزار می‌شه. تیم‌های شرکت‌کننده هم باید دونفره باشن. برای اطلاعات بیشتر هم می‌تونید بهسایت مسابقهرجوع کنید.
خوش باشید
۱. n لامپ را روی یک خط قرار داده‌ایم. همگی بجز لامپ اول در ابتدا خاموش هستند. در هر مرحله اگر لامپی با همسایه‌هایش در مرحله‌ی قبل در یک وضعیت بود در این مرحله خاموش می‌شود و در غیر این صورت روشن می‌شود. ثابت کنید:
الف) بی‌نهایت n داریم که زمانی می‌رسد که همه‌ی لامپ‌ها خاموش باشند.
ب) بی‌نهایت n داریم که هرگز همه‌ی لامپ‌ها خاموش نمی‌شوند.
۲. کمترین n را بیابید که اگر یالهای گراف کامل n راسی (Kn) را به هر شیوه ای با دو رنگ آبی و قرمز رنگ کنیم، حتما یا زیرگراف K4داشته باشد که همه ی یالهای آن آبی باشد یا زیر گراف K3داشته باشد که همه ی یالهای آن قرمز باشد.
۳. به یک «گراف وزن‌دار جهت‌دار همبند»، «گوجه» می‌گوییم. در صورتی که وزن یالهای گوجه، اعداد طبیعی باشد به آن گوجه‌ی طبیعی، و اگر وزن یال‌ها اعداد حقیقیبزرگترمساوی یکباشد به آن گوجه‌ی حقیقی می‌گوییم.
در گوجه، کوتاهترین مسیر بین دو رأس، مسیریست کهجمعوزن یالهای درون مسیر را کمینه کند.
در گوجه، خفن‌ترین مسیر بین دو رأس، مسیریست کهضربوزن یالهای درون مسیر را کمینه کند.
در یک گوجه‌ی طبیعی، زشت‌ترین مسیر بین دو رأس، مسیریست که در صورت ضرب وزن یالهای درون مسیر، تعداد صفرهای سمت راست آن کمینه باشد.
دانشمندان علوم کامپیوتر جدیداً دستگاه خفنی به نام «گرافسالار» ساخته‌اند که با دریافت ماتریس مجاورت یک گوجه‌ی حقیقی n-رأسی، طول کوتاهترین مسیر بین تمام زوج-رئوس را در مرتبه‌ی زمانیO(n2)می‌یابد. شما می‌توانید از گرافسالار برای حل هر بخشی از مسائل زیر کمک بگیرید:
الف) ماتریس مجاورت یک گوجه‌ی حقیقی n-رأسی داده شده. به ازای تمام زوج-رئوس، طول خفن‌ترین مسیر بین آن دو رأس را بیابید.
ب) ماتریس مجاورت یک گوجه‌ی طبیعی n-رأسی داده شده. به ازای تمام زوج-رئوس، طول زشت‌ترین مسیر بین آن دو رأس را بیابید.
سعی کنید بهترین الگوریتم از نظر زمان اجرا را بیابید.
۴. به اجتماع یک یا چند دور که یال مشترک نداشته باشند «ابردور» می‌گوییم. رابطه‌ای برای محاسبه‌ی تعداد ابردورها در گراف دلخواهG بدست آورید. در این رابطه می‌توانید از خواص گراف (مانند ماتریس مجاورت) استفاده کنید. سعی کنید رابطه‌ی نهایی تا حد ممکن ساده‌تر باشد.
۱. به توان‌های ۲ فکر کنید.
۲. اعداد رمزی
۳. الف)log(a×b) = log(a) + log(b)ب) عوامل ۲ و ۵
۴. برای حل مسئله در حالتی که گراف همبند است، زیردرخت فراگیر را در نظر بگیرید...
۱۳۸۹/۱۲/۱۹ · ۱۵:۴۳