سوال ۱- استخدام کارمندان در دو شرکت به نحوی که هیچ کس تمایل به تغییر شرکت خود را نداشته باشد
سوال۵ - تعیین مقادیر الگوریتم برای پردازش دنباله‌ی A
یک مربع بزرگ را در نظر بگیرید. در داخل آن 1389 ...
2010 عدد طبیعی دلخواه نه لزوما متمایز کوچکتر از $2^1389$ را...
در یک شبکه 3x3 نقطه ای ، بین هر دو نقطه مجاور ...
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
به دنباله‌ی $\pi$ به طول $n$ از اعداد ${1,...,n}$ یک «جایگشت» می‌گوییم اگر و تنها اگر هرکدام از این اعداد دقیقاً یک بار در دنباله ظاهر شود. عددی که در مکان $i$ام جایگشت ظاهر میشود را با $\pi (i)$ نمایش می‌دهیم. برای مثال <۱٫۳٫۴٫۲> :$\pi$ یک جایگشت به طول ۴ می‌باشد. پدر علی به او جایگشتی از اعداد ۱ تا $2^k$ داده است ($1 \le k$). علی می‌خواهد کاری کند که به ازای هر $ 1 \le i \le n = 2^k$٬ داشته باشیم $\pi (i) = i$. او برای این کار از الگوریتم زیر استفاده می‌کند:
مثلاً٬ پس از اجرای الگوریتم فوق برای مثال بالا (<۱٫۳٫۴٫۲> :$\pi$)٬ به جایگشت <۱٫۲٫۳٫۴> :$\pi'$ میرسیم.
الف) ثابت کنید با $k$ بار اجرای الگوریتم فوق٬ تمام اعداد سر جای خود قرار میگیرند.
ب) برای هر عدد $k$٬ جایگشتی مثال بزنید که نتوان با $k-۱$ بار اجرای الگوریتم فوق تمام اعداد را در جای خود قرار داد.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 08:11:08 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 06:43:12 -0500 امیر شکریالف) در هربار اجرای الگوریتم هر عددی اگر در جایگاه اصلی اش باشد جابه جا نمیشود و در غیر این صورت حداکثر با قرار گرفتن در جایگاه اصلی اش مانع از چک شدن یک عدد دیگر میشود.پس با یک بار اجرا حداقل نیمی از اعداد به هم ریخته در جایگاه درست قرار میگیرند.پس برای 2 به توان k عدد باحداکثر k بار اجرای الگوریتم اعداد مرتب میشوند.
ب)
با استقرا عمل میکنیم.پایه برای 2 عدد واضح است.فرض میکنیم جایگشتی مانند x داشته باشیم که طول آن 2 به توان k-1 است و به حداقل k-1 بار اجرای الگوریتم برای مرتب شدن نیاز دارد.جایگشت y را قرینه جایگشت x فرض میکنیم.حال جایگشت مورد نظر به طول 2 به توان k را به شکل زیر میسازیم:
واضح است که با یک بار اجرای الگوریتم به جایگشت زیر میرسیم که طبق فرض به حداقل k-1 بار اجرا نیاز دارد:
پس حکم اثبات میشود.
موفق باشید!!
