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

آمار پرسش:

  • پرسیده شده: 2015-04-28 03:23:38 -0500
  • مشاهده شده: 345 بار
  • بروز شده: 2015-04-28 13:21:00 -0500

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

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

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

یال های گراف کامل 6 راسی و مثلث ها

یال های گراف کامل 7راسی و مثلث

سوال الگوریتم بیست و سومین المپیاد کامپیوتر

منابع اطلاعاتی برای آزمون تستی مرحله دوم

پاسخ سوالات مرحله دوم المپیاد کامپیوتر دوره های قبل

ا ستقرا * :

سوال پنجم مرحله سوم دوره ی 19 (30 کاراکتر)

سوال 5 آزمون دوم مرحله سوم دوره ی 20

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

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

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

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

علائم ریاضی:

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

خاظره نویسی بارون - مرحله دوم - دوره 14

1

پس از این که «ویولانته دو ریوالنده» (Violante de Rivalonde) برای همیشه از نزد «بارون کوزیمو لاورس دو روندو» (Baron CosimoLaverse du Rondo) رفت، بارون از فرط ناراحتی خاطره‌نویسی‌های روزانه خود را متوقف کرد. اما پس از مدتی تصمیم گرفت دوباره آن را آغاز کند. اما این بار می‌خواست طوری بنویسد که تنها خودش بفهمد. بنابراین یک زبان رمز ابداع کرد که فقط از دو علامت X و O تشکیل شده بود و از این علائم برای نشان دادن حروف، فواصل خالی و نشانه‌های سجاوندی زبان مادری خود (که از این به بعد به آن‌ها هم حروف می‌گوییم) استفاده می‌کرد. به‌این‌ ترتیب که برای هرکدام از این حروف، رمزی از علائم X و O تعیین کرد، مثلا برای حرف d از رمز OX، برای s از رمز OOX، برای n از OXO، برای l از XO، برای a از XX، برای p از OO و برای e از X استفاده کرد. او برای نشان دادن یک کلمه، رمزهای تک‌تک حروف آن کلمه را به ترتیب پشت سر هم می‌نوشت.

یک روز که بارون یادداشت‌هایش را مرور می‌کرد به کلمه‌ی OOXXXOXOOX برخورد و نفهمید که این کلمه در اصل sand بوده یا pales. (شما هم امتحان کنید)

پس تصمیم گرفت رمزهای حروف را طوری تغییر دهد که هیچ دو ترتیب متفاوت از حروف (با معنی یا بی‌معنی) پس از رمز شدن به رشته‌ی یکسانی از علائم تبدیل نشود و در این کار موفق شد.

برای متن کام و دقیق سوال اینو بزنید موفق باشید

مرحله دوم - شرطی
2015-04-28 03:23:38 -0500
اسمیت 119 ● 1 ● 2 ● 7
پاک‌کردن   ویرایش سوال
نظرات

این خیلی شاخه سوالش! در واقع بیشتر سخته تا شاخ. با تابع مولد حل میشه که اخیرا دیگه مبحث مهمی نیست... . البته یه مدل ساده ترم داره این سؤال (که طراح در واقع می خواسته اون منظورو برسونه ولی صورت سؤالو که داستانیش کردن گند خورده توش!) که با استقرا حل میشه.

2015-04-28 11:11:19 -0500 م زمانی

کسی بلده جوابشو ؟؟ :))))

2015-04-28 11:26:24 -0500 حمیدرضاه

من اینو حل کردم ولی راحش طولانی هستش نمی تونم بنویسم یعنی وقتشو ندارم ولی ایده اسلیش استقرا هه

2015-04-28 11:42:11 -0500 چشمک

اصلیش*

2015-04-28 12:00:59 -0500 چشمک

من یه راه حلی دارم ولی اینطور که میگین تابع مولد و اینا فکر نکنم درست باشه با اینحال من مینویسمش.

2015-04-28 12:14:25 -0500 سماق دو

2 پاسخ

2

سلام.

من سوالو با یه فرض جدید حل میکنم چون تغییر فرض سوال دقیقا همون چیزی بوده که سوالو غیرقابل حل کرده.سوال اصلی مال المپیاد روسیه بوده:

درزبانی با x و o تعدادی کلمه داریم که هیچ دوتایی پیشوند هم نیستن.نامساوی بالا ( همون نامساوی اصلی سوال) را اثبات کنید.

یه درخت دودویی کامل در نطر بگیر،برای هر راس یال سمت چپشو x بزار و یال سمت راستشو o.هر کلمه با یه مسیر یکتا از ریشه به یه راس مشخص میشه پس به هر کلمه یه راس نسبت بده.از طرفی اگه یه راس انتخاب بشه زیریاش انتخاب نمیشن چون هیچ دو کلمه ای پیشوند هم نیستن حالا برگ های انتخاب شده رو حذف کن و پدرهاشون رو - که مطمئنا انتخاب نشدن- رو انتخاب کن.واضحه که حاصل جمع $\frac{1}{2^{l_i}}$ ها کمتر نمیشه.بعدشم استقرا...

image description

2015-04-28 13:21:00 -0500
روبیک 2379 ● 13 ● 27 ● 44
پاک‌کردن   ویرایش پاسخ
نظرات

قشنگ بود جدن ایدش من تا حالا ندیده بودم شاید دوستان دیده باشن :)

2015-04-28 13:53:47 -0500 حمیدرضاه

لازم نیست این فرض رو اضافه کنی میگی اگه یکی پیشوند یکی دیگه بود از پیشوند رو از ابتداش حذف میکنی اینجوری واضحه زبان همچنان خوبه این قدر این کارو میکنی تا به یک زبان جدید برسی و اینکه حکم رو اگه برای این زبان اصلی هم اثبات شده چون طول حروف کم شدند و چپ نا مساوی بزرگ ترشده.

2015-04-29 01:39:47 -0500 احمدرضا

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

2015-04-29 01:44:12 -0500 احمدرضا

جدان واضح نیست که زبان هنوز هم خوبه ها!!!

2015-04-29 11:03:21 -0500 حمیدرضاه

ٰفرض کنید دو تا کلمه یکسان شدند بعد نتیجه بگیرید قبلا هم دوتا کلمه یکسان بودند یا اینکه یک کلمه رو میشه با کنار هم گذاشتن چند تا کلمه دیگه ساخت بعد حالا ثابت کنید کنید که زبانی که هیچ کلمهای پیش وند یکی دیگه نیست و هیچ دو کلمه ای یکسان نیستند خوبه دو تا حکم واقعا آسونند

2015-04-29 14:53:15 -0500 احمدرضا
0

اگر بارون تا حدی عاقل باشه میتونه این راه حلو در نظر بگیره و مسلمن هیچ مشکلی در خواندن متن پیش نمیاد:

X = 1th
XO = 2th
XOO = 3th
.
.
.
XOOOO...O = kth

(i امین حرف = ith )

بعد میگیم با این اوصاف l1, l2, ... lk مشخص میشن و اون عبارت هم از ۱ کمتره (مساوی هم نیست مگر اینکه بینهایت تا حرف باشه) سوال در مورد اینکه بارون چقدر عاقله چیزی نگفته پس میشه این راه حل رو درست در نظر گرفت .:دی

2015-04-28 12:23:37 -0500
سماق دو 1349 ● 7 ● 19 ● 37
پاک‌کردن   ویرایش پاسخ
نظرات

الان بخندیم یا گریه کنیم ؟؟!!

2015-04-28 12:48:25 -0500 حمیدرضاه

:)

2015-04-28 13:00:38 -0500 روبیک

معلم جغرافی یا المپیاد ؟

2015-04-29 23:35:53 -0500 امین انوری

پاسخ شما

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

پیش‌نمایش:

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