یک آرایه از عددهای طبیعی 1 تا n را به ترتیب بنویسید. سپس عددها را یکیدرمیان حذف کنید. عدد اول را حذف کنید و دومی را نگه دارید، سومی را حذف کنید و چهارمی را نگه دارید و به همین شکل تا آخر آرایه پیش بروید. حالا یک آرایۀ جدید دارید که تعداد اعضایش کمتر شده. سپس همین کار را برای آرایۀ جدید تکرار کنید ولی از سمت راست، یعنی عدد آخر را حذف کنید و عدد یکی مانده به آخر را نگه دارید، عدد دوتا مانده به آخر را حذف کنید و عدد سه تا مانده به آخر را نگه دارید و به همین شکل تا اول آرایه. دوباره جهت حذف کردن را برای آرایۀ جدیدی که بهدست میآید، عوض کنید. انقدر این مراحل را تکرار کنید که در نهایت به یک آرایۀ تکعضوی برسید. آن عدد باقیمانده در آرایۀ تکعضوی، چه عددی است؟
تمرین: تابعی بنویسید که عدد n را به عنوان آرگومان بگیرد و همین کارها را تا رسیدن به آرایۀ تکعضوی انجام دهد و عدد داخل آن آرایۀ تکعضوی را در خروجی برگرداند.
به عنوان یک مثال، آرایۀ زیر را در نظر بگیرید:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
چون آخرین عدد آرایه عدد 9 است، پس n برابر با 9 میباشد. سپس ابتدا یکیدرمیان عددهای از اول آرایه حدف میکنیم. به آرایۀ زیر میرسیم:
[2, 4, 6, 8]
سپس این بار از سمت راست یکیدرمیان حذف میکنیم. به آرایۀ زیر میرسیم:
[2, 6]
سپس دوباره از اول آرایه حذف میکنیم. اینجا دیگر به آرایۀ تکعضوی 6 میرسیم:
[6]
پس برای عدد 9، تابع باید عدد 6 را برگرداند.
نمونه ورودی و خروجی
last_remaining(9) ➞ 6
last_remaining(14) ➞ 8
last_remaining(9) ➞ 6
last_remaining(14) ➞ 8
نظرات