امروز در گروهی دوست ریاضیوَرزم آقای تِرِسُ پیوندی را به اشتراک گذاشتند که جالب بود. پیوندِ یادشده یک چیستان یا بازیباریاضی است که به عنوان تمرین یا پرسش برنامهنویسی دادهشدهاست. صورتِ پرسش در پیوند زیر نوشتهشدهاست. البته نویسنده جملههای متن پرسش را با بیدقتی نوشتهاست ولی نمونهای که آوردهاست درست است.
https://leetcode.com/problems/elimination-game/
پستهایی که سایرین برای این پرسش فرستادند را نیز میتوانید در پیوند زیر ببینید.
https://leetcode.com/problems/elimination-game/discuss/?currentPage=1&orderBy=hot&query=
نخست بیاییم پرسش را با هم بخوانیم.
یک عدد طبیعیِ $n$ به شما میدهند. یک لیست از عددهای طبیعیِ ۱ تا $n$ به
ترتیب از چپ به راست بنویسید. گام نخست بیایید نخستین عددی که سمت چپ
میبینید که ۱ است را خط بزنید و عدد پَسینش را نگه دارید، عدد پسین را
خط بزنید و عدد پسینِ آن را نگهدارید. این کار را تا به پایان رسیدن
لیست ادامه دهید. پس عددها را یک در میان حذف کردهاید. لیست شما اکنون
تفاوت کردهاست. تعداد اعضای کمتری دارد. گام پسین این است که گام پیشین
را دوباره تکرار کنید ولی از سمت راست. دوباره لیستتان کوچکتر میشود.
این کار را تکرار کنید و جهت حرکت را در هر گام تغییر دهید. در پایان به
لیستی تکعضوی میرسید. این عدد چند است؟
خواستهٔ پرسش این است که این برنامهای بنویسید که برای هر $n$ -ِ ورودی،
به شما عدد نهایی را بدهد.
خب، سادهترین کار این است که دقیقا همین چیزی که گفتهشدهاست را برنامهنویسی کنید. اما من جور دیگری اقدام کردم. در همین ابتدای کار دقت کنید که باید برایتان روشن باشد که تعداد گامها برابر خواهد بود با $[\log_2(n)]$ که $[.]$ علامت جزءِ صحیح است. بعلاوه اگر در آغازِ گامی تعداد عددها برابر با $m$ باشد، آنگاه در پایانِ آن گام $[\frac{m}{2}]$ عدد باقی خواهدماند. کاری که میکنم این است که در هر گام یک تابع از مجموعهٔ عددهای پس از انجام آن گام به مجموعهٔ عددهای طبیعی ۱ تا $[\frac{m}{2}]$ و در خلاف جهت نسبت میدهم. اگر گام $i$اُم را در نظر بگیرید، ضابطهٔ این تابع برابر است با
$$f_i(x)=[\frac{m}{2}]+1-\frac{x}{2}$$
امیدوارم برایتان دلیلش روشن باشد :) برای اینکه به ذهنیتتان کمک کند تا بتوانید تصورش کنید و ایدهاش را ببینید مثال $n=9$ را به شکل زیر تجسم کنید.
$$\require{cancel}
\begin{array}{llllllllll}
\text{گام ۱}\colon & \cancel{1} & 2 & \cancel{3} & 4 & \cancel{5} & \color{blue}{6} & \cancel{7} & 8 & \cancel{9}\\
\text{گام ۲}\colon & & 4 & & \bcancel{3} & & \color{blue}{2} & & \bcancel{1} & \\
\text{گام ۳}\colon & & \cancel{1} & & & & \color{blue}{2} & & & \\
& & & & & & \color{blue}{1} & & &
\end{array}$$
چشمبندی نکردهایم اگر بگوئیم که اکنون عدد خواستهشدهٔ ما چیزی نیست به جز $f_1^{-1}(f_2^{-1}(\dots(f_r^{-1}(1)\dots))$ که $r$ تعداد گامها است که پیشتر گفتیم چگونه محاسبه میشود (فرمول لگاریتمی بالا) و منظور از $f^{-1}$ تابع وارونِ $f$ است. قرار دهید $b_i=[\frac{m_i}{2}]+1$ که $m_i$ تعداد عددها در شروع گام $i$اُم است. در اینصورت داریم $f_i(x)=b_i-\frac{x}{2}$ که وارونش برابر است با $f_i^{-1}(x)=2b_i-2x$. به سادگی میتوانید ببینید که
$$\big( f_1^{-1}\circ\dots\circ f_r^{-1}\big)(x)=2b_1-4b_2+\dots+(-1)^{r-1}2^rb_r+(-2)^rx$$
پس اگر $m_i$ها را داشته باشیم همه چیز برای استفاده از فرمول بالا برای پاسخ دادن به پرسش را داریم. این مقدارها را نیز میتوان با یک چرخهٔ for محاسبه کرد پلهپله حساب کرد. یعنی $m_1=[\frac{n}{2}]$ و برای هر $i\geq 2$ داریم $m_i=[\frac{m_{i-1}}{2}]$.
اکنون با نرمافزار Maple یک پردازش (procedure) در زیر نوشتهایم که همین حرفها را انجام میدهد. امیدوارم با برنامهنویسی آشنا باشید :)
riddleSolver:=proc(n::posint)::posint;
description "This procedure solves the following riddle.\nFor a positive integer, n, which is the input, consider the list of natural numbers [1, 2, 3, ..., n]. From left to right, delete the first number, leave the second one, then remove the third one and so on. So alternate between deleting and keeping. Then you have a new list. This time do the same process but from right to left. Contune doing the same for the new lists alternating the direction, until when you get a list of only one element. Then return this survived number.\nThis procedure is doing something other than doing the processes as it is said in the riddle, but will give you the same answer you are looking for.\nFor details of the method see this link\nhttps://math.irancircle.com/blog/310\n";
local numberOfSteps,m,mList,i,ans;
numberOfSteps:=floor(log[2](n));
mList:=Array(1..numberOfSteps,1);
m:=n;
for i from 1 by 1 to numberOfSteps do
m:=floor(m/2);
mList[i]:=m+1;
end do;
ans:=add((-1)^(i-1)*2^i*mList[i],i=1..numberOfSteps)+(-2)^numberOfSteps;
return(ans);
end proc;
اکنون برای چند مقدار امتحان میکنیم، $n=9,8,1,14$.
riddleSolver(9);
riddleSolver(8);
riddleSolver(1);
riddleSolver(14);
که به ترتیب برابر میشوند با ۶ و ۶ و ۱ و ۸ که درست هستند. به عنوان یک نکته، اگر میخواهید ببینید که هر گام از پردازشِ بالا (نه گام از توضیحات نوشتاری) چه کاری انجام میدهد، میتوانید محتوای پردازشم را بیرون از محیطِ پردازش بنویسید مانند زیر. این کار گاهی برای رفعِ خطاها و پیدا کردن مکان مشکل در برنامه نیز استفاده میشود.
n:=9;
numberOfSteps:=floor(log[2](n));
mList:=Array(1..numberOfSteps,1);
m:=n;
for i from 1 by 1 to numberOfSteps do
m:=floor(m/2);
mList[i]:=m+1;
end do;
ans:=add((-1)^(i-1)*2^i*mList[i],i=1..numberOfSteps)+(-2)^numberOfSteps;
printf("\nThe answer is %d.\n",ans);
امیدوارم لذت برده باشد.
