آمار پرسش:
- پرسیده شده: 2015-03-11 17:34:30 -0600
- مشاهده شده: 1,216 بار
- بروز شده: 2015-09-08 05:28:47 -0600
پرسش‌های مشابه:
آشپزباشی: مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن
تعداد جواب های معادله ${1\over x}+{1\over y}={1\over n}$ در دستگاه اعداد صحیح
همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1
یکی کردن علامت خانه‌های یک جدول $4\times 4$ از + و - ها
تبدیل جدول با چرخش‌های ساعتگرد مربع $2\times 2$
دو زیرمجموعه فرد و زوج از مجموعه {۱، 2، 3، ...64}
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
جدولی $2010\times 2010$ امکان رسیدن به جدولی که همه مهره ها در یک خانه جمع شوند
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
مرتب سازی عجیب با تعویض بلوکی ًًًًًً
یک رشته از داریم که میخواهیم مرتبش کنیم در هر مرحله میتوانیم که دو بلوک را انتخاب کرده وجای انها را عوض کنیم
بلوک به یک زیر رشته متوالی در یک رشته گفته میشود برای مثال :
7 6 3 2 1 5 4 ->
7 6 3 2 1 | 5 4
->
7 6 5 4 3 2 1
حالا میخواهیم حداقل تعداد حرکت رو بدانیم که با اون تعداد مرحله مطمئن باشیم که رشته مرتب میشه (بر حسب n تعداد اعداد رشته)
خودم چون نمیدونم چون جوابش چیه میگم خفنه D:
ویرایش : واقعا ببخشید سوالو اشتباه گفتم دو تابلوک همسایه فقط ویرایش 2:رشته اولیه رشته نزولیه از n تا 1 هست
این که بعضیا میگن n-1 میشه برای 5 مثال میزنم:
54321
32541
34125
12345
برای 9 که اقا ایدین برنامه نوشته :
1,2,3,4,5,6,7,8,9
1,2,5,6,7,8,3,4,9
1,6,7,8,3,2,5,4,9
7,8,3,2,1,6,5,4,9
7,6,5,4,9,8,3,2,1
2015-03-11 17:34:30 -0600
حمیدرضاه 2979 ● 20 ● 26 ● 52
نظرات
6 پاسخ
جواب n-1 ه چون بدیهیه که با n-1کی میشه و برعکس sort شده ی اعداد نیز بین هر دو تایی حتما یکی می خواد که می شه n-1
2015-03-12 08:20:24 -0600
یارا 741 ● 7 ● 13 ● 30
نظرات
اول این که غلته چون برای بعضی n ها کمتر هم میشه :) تو الان کافی بودنش رو گفتی نه لازم بودنش رو :)
2015-03-12 08:30:00 -0600 حمیدرضاهمن یه کد BFS زدم که تا n=9 رو خوب جواب می‌ده. برای ۹ جواب ۵ هست که این هست.
1,2,3,4,5,6,7,8,9
1,2,5,6,7,8,3,4,9
1,6,7,8,3,2,5,4,9
7,8,3,2,1,6,5,4,9
7,6,5,4,9,8,3,2,1
9,8,7,6,5,4,3,2,1
حدس من این هست که جواب برای $n>1$ برابرست با $1+\lfloor {n\over2}\rfloor$ که شاید با استقرا بشه درش آورد.
2015-03-23 14:19:13 -0600
آیدین 343 ● 6
نظرات
کدم خیلی کثیف و هول هولکیه. اما اگه کسی خواست اینجاست: http://pastebin.com/2KRkr87i برای ۱۰ هم جواب ۶ هست و روی این ماشین من حدود یک دقیقه و نیم طول می‌کشه.
2015-03-23 15:52:59 -0600 آیدیننمیتونم بگم چرا کمتر از n/2 نمیشه ولی برا n/2 یا n/2+1 میتونم الگوریتم بیارم
نگا کنین در مرحله i بیاین این کارو انجام بدین از خونه iام تا یه خونه قبل از i+کف n/2 با دو خونه بعدیش ینی i+کف n/2 و 1+i+کف n/2 عوض کنیم خب با این راه بعد از n/2 مرحله نیمه آخر به صورت صعودی در نیمه اول قرار میگیره و نیمه اول به صورت صعودی در نیمه آخر
میشه اثبات کرد خیالتون راحت:)
حالا برای اینکه بهتر متوجه بشین یه مثال میزنم
برای 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 9 10 11 12 13 14 7 8
1 2 3 4 5 10 11 12 13 14 7 6 9 8
1 2 3 4 11 12 13 14 7 6 5 10 9 8
1 2 3 12 13 14 7 6 5 4 11 10 9 8
1 2 13 14 7 6 5 4 3 12 11 10 9 8
1 14 7 6 5 4 3 2 13 12 11 10 9 8
7 6 5 4 3 2 1 14 13 12 11 10 9 8
14 13 12 11 10 9 8 7 6 5 4 3 2 1
خب اثبات اینکه الگوریتم درستیه یکی به صورت تجربی:) یکی دیگ اینه ک هر دفعه دو دنباله صعودی به هم چسبیده داریم هر مرحله یه عضو ب انتهای دنباله صعودی اولی و یکی به ابتدا ی دنباله صعودیه آخری اضافه میشه این دو عضو هم همون بلوک دو عضویه هر مرحلست
حالا یه خورده روش فکر کنین میفهمین اگه نشد بیشتر توضیح میدم
اینم کدش:link text
2015-09-07 08:20:15 -0600
هادیزاده 264 ● 4
نظرات
بد ترین حالت زمانیه که اعداد به صورت نزولی چیده شده باشند..........................................................................
نظرات
این حرف غلطه چون توی المپیاد باید اثبات بشه این بدترین حالته و اثبات این موضوع هم اصلا ساده نیست
2015-03-12 12:28:45 -0600 ایمان خانفکر میکنم جواب 1+کف n/2 باشه چون فکر میکنم تو هر مرحله حداکثر 2 تا از ترتیب اعداد درست شود و در مراحل 1و2 2 تا فکر میکنم درست نمیشود پس حداقل 1+کف n/2 تا فکر میکنم لازم داره اما الگوریتم برای 1+کف n/2 : اگر n فرد بود مثل زیر: n=11 1 2 3 4 5 6 7 8 9 10 11
1 7 8 9 10 11 2 3 4 5 6
11 2 1 7 8 9 10 3 4 5 6
11 10 3 2 1 7 8 9 4 5 6
11 10 9 4 3 2 1 7 8 5 6
11 10 9 8 5 4 3 2 1 7 6
11 10 9 8 7 6 5 4 3 2 1
2015-09-06 13:48:37 -0600
پوری 11 ● 2
فکر کنم n/2 باشه............................................................................................
2015-03-12 03:58:12 -0600
ابوالفضل خان 248 ● 6 ● 10 ● 22
نظرات
چرا؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
2015-03-12 11:46:50 -0600 پلانگتون