جواب n-1 ه چون بدیهیه که با n-1کی میشه و برعکس sort شده ی اعداد نیز بین هر دو تایی حتما یکی می خواد که می شه n-1

من یه کد 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$ که شاید با استقرا بشه درش آورد.

نمیتونم بگم چرا کمتر از 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

بد ترین حالت زمانیه که اعداد به صورت نزولی چیده شده باشند..........................................................................

فکر میکنم جواب 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

فکر کنم n/2 باشه............................................................................................