بازگشت، استقرا و حل مسئله
یادآور نظریه مجموعهها: قسمت ۸
درآمد به منطق و رایانش
__ TL. Wingensrein, On Certainty, 471
در این قسمت با دو مفهوم بنیادین در ریاضیات و علوم کامپیوتر، یعنی «بازگشت (Recursion)» و «استقرا (Induction)»، و تمایز جهتگیری آنها (بالا به پایین در برابر پایین به بالا) آشنا میشویم. سپس اصول «استقرای ریاضی»، «استقرای کامل» و «استقرای ساختاری» معرفی میگردند. کاربرد این ابزارها در تعریف بازگشتی مجموعهها و توابع (همچون جمع، ضرب، توان و ب.م.م)، حل مسئله کلاسیک «برج هانوی» (با استخراج و اثبات آن رابطه بازگشتی آن)، و اثبات قضایایی مانند وجود مقسومعلیه اول و کران دنباله فیبوناچی به تفصیل نشان داده میشود. در پایان نیز برای درکی عینی، شبیهسازی روند بازگشت را در حافظه (پشته) خواهیم ید.
بازگشت، استقرا و حل مسئله
| ویرایش: ۱۴۰۵/ ۰۳/۲۷ | |
• مقدمه: بازگشت چیست؟ استقرا چیست؟ | • توابع بازگشتی و نمونهها |
• تعریف بازگشتی (Recursive definition) | • حل مسئله: معمای برج هانوی (برج برهما) |
• تعریف استقرایی (Inductive Definition) | • مسئله توزین [تعمیم تمرین ۱۱ - قسمت مسئله و استدلال - کتاب درآمد به منطق] |
• روش تعریف استقرایی | • مسئله: هر عدد طبیعی بزرگتر از یک حداقل یک مقسوم علیه اول دارد. |
• اصل استقرای ریاضی (Mathematical induction principle) | • مسئله: `F_n < ۲^n`. [`≺F_n≻` دنباله فیبوناتچی] |
• استقرای کامل (Complete induction) | • مسئله: تقریب عناصر دنباله فیبوناتچی |
• استقرای ریاضی (Mathematical induction) | • مثال: تعریف غیربازگشتی توان (`x^n`) |
• مجموعههای بازگشتی (Recursive sets) | • مثال: تعریف بازگشتی توان (`x^n`) |
• استقرای ساختاری (Structural Induction) | |
■ مقدمه: بازگشت چیست؟ استقرا چیست؟
پیش از آغاز بحث، شایسته است برای دوری از ابهام، مراد خود را از دو اصطلاح «بازگشت / Recursion» و «استقرا / Induction» در این قسمت روشن کنیم تا از ابهام و خلط مفهومی پرهیز شود.
بازگشت و استقرا هر دو به ساختارهایی مربوطاند که «گامبهگام» فهمیده، ساخته یا تعریف میشوند، با این حال، نقش و جهت آنها یکسان نیست. معمولاً، بازگشت یک روند از بالا به پایین و استقرا یک روند پایین به بالا است.
در استقرا، معمولاً دو بخش اصلی داریم:
- گام پایه
- گام استقرایی
در بازگشت نیز معمولاً دو عنصر اصلی داریم:
- گام پایه
- قاعده بازگشتی
از اینرو، هر تعریف استقرایی ناگزیر بازگشتی است، اما هر تعریف بازگشتی الزاماً استقرایی نیست. تفاوت اصلی در این است که تعریف استقرایی باید هم نقطهی آغاز روشن داشته باشد و هم سازوکار تولید مرحلهبهمرحله. در حالی که، تعریف بازگشتی ممکن است صرفاً بر ارجاع به خود متکی باشد و لزوماً ساختار کامل استقرا را فراهم نکند.
شکل. ۱ بازگشت و استقرا
معمولاً، بازگشت یک روند از بالا به پایین و استقرا یک روند از پایین به بالا است.
تعریف استقرایی Induction Definition تعریف استقرایی (که «تعریف از طریق استقرای ترامتناهی» نیز نامیده میشود) با مشخص کردن عناصر زیر تعریفشده را تعریف میکند: حالت(های) پایه: معرفی عنصر(عناصر) نخستینی، مرحله استقرایی: نحوه ساخت عناصر جدید از مراحل قبلی (که پرش استقرایی نیز نامیده میشود). این تعریف به سمت بالا پیش میرود (پایین به بالا - Bottom-Up). یعنی، از پایه به سمت ساختارهای پیچیدهتر میرود. این تعریف مشخص میکند که در هر مرحله چه چیزی به یک مجموعه یا ساختار تعلق دارد. |
تعریف بازگشتی Recursive Definition تعریف بازگشتی یک تابع، مجموعه یا یک ساختار را با مشخص کردن عناصر زیر تعریف میکند: حالت(های) پایه: نقطه(های) شروع، قاعده(های) بازگشتی: نحوه ساخت عناصر جدید از حالتهای موجود. این تعریف، تعریفی به سمت پایین است (بالا به پایین) Top-Down. یعنی، از حالتهای پیچیده به حالتهای سادهتر پیش میرود. این میگوید که چگونه چیزی را گام به گام ساخت (یا محاسبه) کرد. |
■ تعریف بازگشتی (Recursive definition)
تعریف بازگشتی شیوهای برای تعریف یا توصیف یک مفهوم بر حسب خود همان مفهوم، یا بر پایهی موردهای سادهتر آن، است.
این شیوه در حوزههایی مانند زبانشناسی، ریاضیات، علوم رایانه و منطق کاربرد گستردهای دارد. در یک تعریف بازگشتی، مفهوم مورد نظر به نحوی به خود آن مفهوم ارجاع داده میشود. با این حال، اگر این ارجاع بدون سازوکار روشن و نقطهی آغاز معین صورت گیرد، میتواند به ابهام یا دور باطل بینجامد. برای مثال «فرهنگ واژگان کتابی است که شامل تعاریف واژگان از جمله واژه فرهنگ واژگان است» گرچه یک تعریف بازگشتی است، اما یک تعریف استقرایی نیست. [کتابخانه راسل و پارادوکس درغگو را ببینید.]
تابع بازگشتی تابعی است که برای تعیین مقدار خود، به مقدار همان تابع در ورودیهای کوچکتر یا سادهتر مراجعه میکند. برای مثال، تابع فاکتوریل بهصورت بازگشتی چنین تعریف میشود: [ `n! = n \times (n-1)!` ] به این ترتیب، محاسبهی فاکتوریل یک عدد به محاسبهی فاکتوریل عددی کوچکتر فروکاسته میشود.
الگوریتم بازگشتی نیز، روشی برای حل یک مسئله با شکستن آن به زیرمسئلههای کوچکتر از همان نوع، و به کار زدن همان الگوریتم برای هر زیرمسئله تا رسیدن به حالت پایه است.
یادداشت:
در کل، نظریه توابع بازگشتی شاخهای از منطق است که کلاسی از توابع را مطالعه میکند که میتوان با استفاده از بازگشت، یعنی با اعمال همان تابع برای ورودیهای کوچکتر تعریف یا محاسبه کرد.
بازگشت و توابع بازگشتی توسط تورالف آلبرت اسکولم (Thoralf Albert Skolem)، یکی از پیشگامان فرامنطق، به عنوان راهکاری برای اجتناب از پارادوکسهای نامتناهی که هنگام کارزدن توابع برای کلاسهای نامتناهی و نیز رهایی از تعاریف دوری برای کلاسهای نامتناهی به وجود میآیند، ایجاد شد. همچنین، تئوری توابع بازگشتی یک مدل صوری از محاسبات ارائه میکند و محدودیتها و امکانات محاسبه کارآمد را بررسی میکند. [توابع بازگشتی-نخستینی را ببینید.]
■ تعریف استقرایی (Inductive Definition)
تعریف استقرایی نوع خاصی از تعریف بازگشتی است که در آن، عناصر یک مجموعه یا ساختار بهصورت گام به گام ساخته میشوند. این نوع تعریف معمولاً دو بخش دارد:
• گام پایه: معرفی یک یا چند عنصر اولیه،
• گام استقرایی: بیان قاعدهای برای ساخت عناصر جدید از عناصر پیشین.
تعاریف اسقرایی معمولاً از پایین به بالا پیش میرود. یعنی از موارد ابتدایی آغاز میکند و بهتدریج ساختارهای پیچیدهتر را میسازد.
■ روش تعریف استقرایی
همانطور که در بالا گفته شد، یک تعریف استقرایی در دو گام به شرحی که میآید ساخته میشود.
۱- در گام پایهای استقرا یک یا تعداد محدود از عناصر دنباله معرفی میشود؛
۲- در گام استقرایی (که پرش استقرایی نیز نامیده میشود) اعمالی معرفی میشود که بهموجب آن اعمال بقیه عضوهای دنباله برحسب عضوهای پیشین دنباله به دست میآید.
سپس تأکید میشود که فقط آنچه از گامهای ۱ و ۲ حاصل میشود عضو دنباله است و نه هیچچیز دیگر. (برخی این گام را ضروری نمیدانند.)
در مثالی که میآید دنباله `≺F_n≻` که به دنباله فیبوناچی را به صورت بازگشتی میسازیم:
در گام پایه میگوییم `F_۰=۰` و `F_۱=۱` عناصر این دنباله هستند.
در پرش استقرایی میگوییم اگر `F_k` و `F_{k-۱}` عضو دنباله باشند آنگاه `F_{k-۱}+F_k`،`k gt ۰`، نیز عنصر این دنباله است.
در گام سوم میگوییم فقط آنچه از دو گام اول ساخته میشوند عناصر `F_n` است.
در زیر هفت عضو آغازی این دنباله آمده است:
| `F_۰` | `F_۱` | `F_۲` | `F_۳` | `F_۴` | `F_۵` | `F_۶` | ... |
| ۰ | ۱ | ۲ | ۳ | ۵ | ۸ | ۱۳ | ... |
| ۱+۱=۲ | ۱+۲=۳ | ۲+۳=۵ | ۳+۵=۸ | ۵+۸=۱۳ | ... |
■ اصل استقرای ریاضی (Mathematical induction principle)
گیریم ویژگی P برای عدد ۰ برقرار باشد و هرگز برای هر عدد طبیعی `n` برقرار نباشد مگر آنکه برای `n+۱` برقرار باشد. در این صورت P برای همه اعداد طبیعی برقرار خواهد بود.
■ استقرای کامل (Complete induction)
گیریم ویژگی P برای هر عدد طبیعی n وقتی برقرار است که برای همه اعداد طبیعی کوچکتر از n برقرار باشد؛ آنگاه P برای همه اعداد طبیعی برقرار است.
☚ . همارزی اصل استقرای ریاضی، استقرای ریاضی کامل و خوش-ترتیبی:
اصل استقرای ریاضی و استقرای ریاضی کامل دو بیان متفاوت و همارز هستند، یعنی با فرض یکی دیگری را میتوان اثبات کرد. همچنین ااصل خوشترتیبی اعداد طبیعی (هر زیرمجموعه ناتهی اعداد طبیعی دارای کوچکترین عنصر است) با اصل استقرای ریاضی همارز است.
اصل استقرای ریاضی ⇔ استقرای ریاضی کامل ⇔ اصل خوشترتیبی اعداد طبیعی
■ استقرای ریاضی (Mathematical induction)
| .۲ | گیریم خاصیت P برای ۱ برقرار باشد و |
| .۲ | اگر برای عدد طبیعی n برقرار باشد آنگاه برای n+۱ نیز برقرار باشد؛ |
| .۳ | آنگاه P برای همه اعداد طبیعی برقرار است. |
■ مجموعههای بازگشتی (Recursive sets)
مجموعهها را میتوان به روش بازگشتی مشابه با آنچه درباره دنبالهها (بازگشتی) گفتیم تعریف کرد. مجموعهای که به روش بازگشتی قابلتعریف باشد به مجموعه بازگشتی موسوم است. هر مجموعه بازگشتی در سه گام به شرحی که میآید تعریف میشود:
۱- (گام پایهای) یک یا تعداد محدودی از اعضای مجموعه معرفی میشود؛
۲- (گام استقرایی) اعمال (یا قواعدی) معرفی که بهموجب آنها عضوی از مجموعه برحسب اعضای موجود (فعلی) مجموعه ساخته میشود.
تأکید میشود که فقط آنچه از دو مرحله ساخت ۱ و ۲ ساخته شود عضو مجموعه است و نه هیچ عنصر دیگر.
فرض کنید میخواهیم مجموعهای که به آن N خواهیم گفت را به روش بازگشتی تعریف کنیم.
۱- در گام پایهای میگوییم:
۰∈N؛
۲- در گام استقرایی میگوییم:
اگر x∈N آنگاه x+۱∈N؛
تاکید میکنیم: فقط و تنها فقط آنچه از ۱ و ۲ حاصل میشود عضو N است.
به ۰ عنصر سازنده مجموعه N میگوییم. میتوان دید N همان Z+ است. بنابراین مجموعه اعداد طبیعی یک مجموعه بازگشتی است.
برای مثال دیگر فرض کنید میخواهیم مجموعهای بنام N' را به روش بازگشتی تعریف کنیم.
۱- در گام پایهای میگوییم ۰∈N'.
۲- در گام استقرایی ابتدا تابع s را در N' به قسمی تعریف میکنیم که s(x) مخالف ۰ و نیز مخالف اعضای تاکنون ساختهشده در N' باشد و میگوییم اگر x∈N' باشد آنگاه s(x)∈N'.
تاکید میکنیم: فقط و تنها فقط آنچه از ۱ و ۲ حاصل میشود عضو N' است.
بنابراین
N'={۰, s(۰), s(s(۰)), s(s(s(۰))), . . .}.
◄ . به تابعی با کارکرد تابع s در بالا تابع تالی [پی-آمد] گفته و آن را معمولاً با succ نشان داده. در این مثال میتوان نوشت:
succ(n) = n + ۱.
برای مثال دیگر فرض کنید میخواهیم مجموعهای بنام N'' را به روش بازگشتی تعریف کنیم.
۱- در گام پایهای میگوییم:
ø ∈ N''.
۲- در گام استقرایی میگوییم:
اگر x ∈ N'' آنگاه x∪{x}∈N''.
[در اینجا succ(x)=x∪{x}.]
تاکید میکنیم: تنها و فقط تنها آنچه از ۱ و ۲ حاصل میشود عضو N'' است.
بنابراین:
N''={ø, ø∪{ø}={ø}, {ø}∪{{ø}}={ø, {ø}}, {ø, {ø},{ø,{ø}}}, . . . }.
اگر در این مثال ø را با نماد ۰، {ø} را با ۱، {ø, {ø}} را با ۲ نشان دهیم و همینطور مانند آنها، آنگاه مجموعه {۰, ۱, ۲, . . .} را در پی خواهیم داشت که ø عنصر سازنده آن است.
■ استقرای ساختاری (Structural Induction)
استقرای ساختاری گونهای استقرای ریاضی است و یک تکنیک برهان است که استقرای ریاضی را به ساختارهای تعریفشده به شیوه بازگشتی (مثل مجموعهها بازگشتی و مانند آن) تعمیم میدهد.
به عبارت دیگر، استقرای ساختاری یک ویژگی، بفرض `P` را برای همه عناصر یک ساختار بازگشتی معین به صورت زیر اثبات میکند:
- گام(های) پایه: اثبات ویژگی `P` برای سادهترین مولفههای ساختار.
گام (های) استقرایی: فرض کنید `P` برای مؤلفههای ساده برقرار است (فرض استقرا). سپس ثابت میکنیم که برای یک عنصر مرکب ساخته شده با استفاده از یک قاعده ساختِ ساختار مورد نظر نیز برقرار است. [برای مثال اسقرای روی ساختاری فرمول را ببینید.]
■ توابع بازگشتی و نمونهها
همانطور که نیز در ابتدای این قسمت گفته شد، یک تابع بازگشتی تابعی است که در چرخههای پی در پی خود را به عنوان بخشی از محاسبات خود اما با ورودیهای کوچکتر فرامیخواند.
☜ در آنچه میآید، مگر خلاف آن گفته شود، مجموعه مرجع ما اعداد طبیعی ℕ است.
• مثال ۱. تابع جمع در دستگاه پئانو
در این مثال و دو مثال بعد فرض کردهایم که مروری به دستگاه پئانو داشتهایم و نیز توجه داریم که اعداد در این دستگاه به قرار زیر هستند:
۰, S(۰), S(S(۰)), S(S(S(۰))), . . .
[S(n) تالی بیواسطه n است.]
به عبارت دیگر:
۰, S۱(۰), S۲(۰), S۳(۰), . . . ,Sn(.), . . .
تابع جمع بازگشتی، sum(x, S(y))، در این دستگاه به روش بازگشتی مطابق زیر تعریف میشود:
| sum(x, y) | = |
 |
|
| آ: | x | اگر y = . | گام پایهای: |
| sum(x, S(y)) | |||
| ب: | S(sum(x, y)) | در غیر آن. | گام استقرایی: |
در این تعریف جمع x و تالی y در گام استقرایی بر حسب جمع x و y تعریف شده است.
• مثال ۲. تابع بازگشتی ضرب در دستگاه پئانو
تابع ضرب بازگشتی، mul(x, S(y))، در این دستگاه به روش بازگشتی مطابق زیر تعریف میشود:
| mul(x, y) | = |
|
|
| آ: | . | اگر y = . | گام پایهای: |
| mul(x, S(y)) | |||
| ب: | sum(x, mul(x, y)) | در غیر آن. | گام استقرایی: |
در این تعریف ضرب x و تالی y در گام استقرایی بر حسب جمع x با حاصلضرب x در y تعریف شده است.
• مثال ۳. تابع توان در دستگاه پئانو
تابع توان، pow(x, S(y))، در این دستگاه به روش بازگشتی مطابق زیر تعریف میشود:
| pow(x, y) | = |
|
|
| آ: | S(.) | اگر y = . | گام پایهای: |
| pow(x, S(y)) | |||
| ب: | mul(x, pow(x, y)) | در غیر آن. | گام استقرایی: |
در این تعریف x به توان تالی y در گام استقرایی بر حسب ضرب x در x به توان y تعریف شده است.
• تابع بزرگترین مقسوم علیه مشترک
فرض کنید x≥y>۰ اعداد طبیعی باشند و مقدار تابع mod(x,y) باقیمانده تقسیم صحیح x بر y باشد. در این صورت تابع GCD(x,y)، که به قرار زیر تعریف شده است، را بزرگترین مقسوم علیه مشترک x و y مینامیم.
| GCD(x, y) | = |
|
|
| آ: | x |
اگر mod(x, y)=۰ |
گام پایهای: |
| ب: | GCD(x, mod(x, y)) | در غیر آن. | گام استقرایی: |
در حساب بزرگترین مقسوم علیه مشترک دوعدد بزگترین عددی است که آن دو را میشمرد. آیا تابع GCD در بالا این تعریف را برمیآورد؟ از حساب میدانیم اعداد q و r بگونه یکتا وجود دارند به قسمی که:
I. x = qy + r; m > r ≥ ۰
[میدانیم اگر t ،s را بشمرد و u ،t را بشمرد آنگاه u ،s را خواهد شمرد.]
[میتوان در رابطه I نشان داد: mod(x, y) < [x / ۲]]
از رابطه I داریم که هر چه r و y را بشمارد آنگاه x را میشمارد. I را میتوان به صورت زیر نیز نوشت:
II.x - qy = r
از رابطه II نیز داریم: هر چه x و y را بشمارد r را نیز میشمارد.
[نمونهای از محاسبه ب.م.م در بحث مقدماتی الگوریتم آمده است.]
■ حل مسئله: معمای برج هانوی (برج برهما)
معمای مشهور به برج هانوی (نیز برج برهما) در ۱۸۸۳ توسط ریاضیدان فرانسوی ادوارد لوکاس (Edouard Lucas) همرا با افسانه خود (برج برهما) پا به جهان گشود.↧
«در معبد بزرگ بنارس، زیر گنبدی که مرکز جهان است، صفحهای برنجی قرار دارد که در آن سه سوزن الماس، هر یک به ارتفاع یک ذراع و به ضخامت بدن زنبور عسل تعبیه شده است. روی یکی از این سوزنها، هنگام آفرینش، خداوند شصت و چهار قرص از طلای ناب قرار داد که بزرگترین قرص روی صفحهای برنجی و بر روی آن بقیه قرصها تا بالا کوچکتر و کوچکتر قرار دارند. روز و شب، بی وقفه، کاهنان قرصها را از یک سوزن الماس به سوزن الماس دیگر بر اساس قوانین ثابت و تغییرناپذیر برهما منتقل میکنند. طبق قوانین ثابت و تغییرناپذیر برهمای در حال انجام وظیفه نباید بیش از یک قرص را در یک زمان انتقال دهد و نیز نباید قرصی در یک سوزن روی قرص کوچکتر آن باشد. هنگامی که شصت و چهار قرص به این ترتیب از سوزنی که در آفرینش خداوند آنها را اینگونه آفریده بود به یکی از سوزنهای منتقل شوند، آنگاه جهان درهم میریزد و با صدای مهیب محو میشود.»
آنچه این معما از ما میخواهد (یا اینجا در پی آنیم):
۱- یافتن دنبالهای از حرکتهای تک دیسکی برای انتقال ۶۴ دیسک از یکی از سه سوزن به سوزنی دیگر مطابق با قوانین برهمایی.
۲- چند حرکت تک دیسکی برای انجام کار لازم و کافی است؟
بهترین راه در برابر چنین پرسشی (پرسشهایی)، تعمیم آن(ها) است. برج برهما دارای ۶۴ دیسک است، در نظر بگیرید که اگر n دیسک وجود داشته باشد چه اتفاقی میافتد.
یکی از مزایای این تعمیم این است که میتوان مسئله را کاهش داد. در واقع، در بیشتر موارد و در ابتدا نگاه به موارد کوچک سودمند است و به ما بینش در مورد کل مسئله را میدهد. [«اگر از عهده حل مسئلهای برنمیآیید، مسئلهای آسانتر هست که از عهده آن برمیآیید: آن را بیابید➥»]. دنباله حرکتهای تک دیسکی از سوزنی که فقط شامل یک یا دو دیسک است آسان است. تعداد کمی آزمون نشان خواهد داد که چگونه میتوان دیسکها را از یک سوزن دوتایی به سوزن دیگر منتقل کرد.
میتوانیم از انتقال n=۰ دیسک آغاز کنیم که در این حالت به تعداد صفر جابجایی نیاز است. در نمودار زیر حل معما برای یک و دو دیسک آمده است.
• استخراج رابطه بازگشتی
اگر Ti را تعداد انتقالهای تک دیسکی برای برج برهما با i دیسک بنامیم، آنگاه با توجه به شکل بالا میتوان نوشت:
T۰ = ۰
T۱ = ۱
T۲ = ۳
برای حل معما در حالت سه دیسک، یعنی یافتن دنباله حرکتهای تک دیسکی برای انتقال سه دیسک آنگونه که برهما میخواهد چه باید کرد؟ پاسخ نه تنها آسان بلکه آماده هم است. یعنی:
| ۱- | دو دیسک رویی را با روش حل در حالت دو دیسکی به یکی از دو میله خالی، به فرض c انتقال میدهیم. |
| ۲- | دیسک سوم، یعنی بزرگتری دیسک، را به میله b انتقال میدهیم. |
| ۳- | دو دیسک در میله c را با روش حل در حالت دو دیسکی به میله به فرض b انتقال میدهیم. |
| ۴- | پایان. |
اکنون حل معما تا اینجا را تعمیم میدهیم و میگوییم: اگر حل معما را برای n-۱ دیسک داشته باشیم آنگاه روند حل معما برای n دیسک بگونه زیر است.
| ۱- | n-۱ دیسک رویی را با روش حل در حالت n-۱دیسکی به یکی از دو میله خالی، به فرض c انتقال میدهیم. |
| ۲- | دیسک nام، یعنی بزرگتری دیسک، را به میله b انتقال میدهیم. |
| ۳- | n-۱ دیسک در میله c را با روش حل در حالت n-۱ دیسکی به میله به فرض b انتقال میدهیم. |
| ۴- | پایان. |
در روند بالا دوبار انتقال n-۱ داریم، یعنی Tn-۱ بار حرک تک دیسکی و یک بار هم انتقال دیسک زیرین، یعنی بزرگترین دیسک، پس مینویسیم:
a.Tn ≤ ۲Tn - ۱ + ۱; n > ۰ برای
در فرمول بالا بجای «=» نماد کوچکتر یا بزرگتر، ≤، آمده است. این به این دلیل است که روند ساخت این فرمول از عهده کفایت ۲Tn-۱+۱ حرکت برای و نه لزوم آن برمیآید. در روند حل این معما سرانجام باید بزرگترین دیسک را جابجا کنیم. وقتی این کار را انجام میدهیم که n-۱ کوچکترین دیسک روی یک میله باشند، و حداقل باید Tn-۱+۱ جابجایی انجام شده باشد تا آنها را در آن میله قرار داده باشیم. اگر خیلی هوشیار نباشیم، ممکن است بزرگترین دیسک را بیش از یک بار جابجا کنیم. اما پس از جابجایی بزرگترین دیسک برای آخرین بار، باید n-۱ کوچکترین دیسک (که باید دوباره روی یک میله قرار گیرند) را روی بزرگترین دیسک منتقل کنیم. این نیز به Tn-۱ جابجایی نیاز دارد. بنابراین میتوان نوشت:
b. Tn ≥ ۲Tn - ۱ + ۱; n > ۰ برای
از دو نامعادله a و b و اینکه T۰= ۰، میتوان نوشت:
T۰ = ۰ n = ۰ برای
Tn = ۲Tn - ۱ + ۱; n > ۰ برای
بنابراین:
T۰ = ۰= ۲۰ - ۱
T۱ = ۲ × ۰ + ۱ = ۱ = ۲۱ - ۱
T۲ = ۲ × ۱ + ۱ = ۳ = ۲۲ - ۱
T۳ = ۲ × ۳ + ۱ = ۷ = ۲۳ - ۱
T۴ = ۲ × ۷ + ۱ = ۱۵ = ۲۴ - ۱
T۵ = ۲ × ۱۵ + ۱ = ۳۱ = ۲۵ - ۱
....
....
Tn = ۲Tn - ۱ + ۱ ≟ ۲n - ۱ - ۱
....
برای اینکه نشان دهیم Tn=۲n-۱ برقرار است از اصل استقرا بهره میبریم و فرض میکنیم برای کمتر از n این رابطه برقرار باشد. پس مینویسیم:
Tn = ۲Tn - ۱ + ۱ = ۲(۲n - ۱ - ۱ ) + ۱=
= ۲×۲n - ۱ - ۲ + ۱= ۲n - ۱
بنابراین برهمای مامور به آخر رساندن جهان باید T۶۴=۲۶۴-۱ جابجایی انجام دهد که برابر عددی با ۱۹ رقم است. اگر هر جابجای تک دیسک یک میلیونام ثانیه زمان ببرد، برهما باید بیش از ۵۰۰۰ قرن به کار جابجایی بپردازد.↧
■ مسئله توزین [تعمیم تمرین ۱۱ - قسمت مسئله و استدلال - کتاب درآمد به منطق]
`n` (`n` زوج) گوی فلزی در اختیار داریم كه ازهرجهت شبیه هم بوده بهجز یكی كه فقط ازنظر وزن از بقیه سبکتر است. یك ترازو دوكفهای نیز در اختیارداریم. مسئله از ما میخواهد نشان دهیم حداقل با چند توزین میتوان گوی سبکتر را مشخص کرد. [تعمیم تمرین ۱۱ در قسمت مسئله و استدلال - کتاب درآمد به منطق]
پاسخ مسئله چنین است:
`T(n) = |~ log_۳^n ~|`, ↝
که در آن `T(n)` حداقل تعداد توزین در بدترین حالت است.
اثبات:
اثبات از دو بخش تشکیل میشود: ۱- ابتدا نشان میدهیم کمتر از این تعداد توزین ممکن نیست، ۲- سپس با استقرا نشان میدهیم این تعداد توزین کافی است.
۱. کران پایین
در هر توزین، اگر تعداد گویهای دو کفه برابر باشد، سه نتیجه ممکن وجود دارد:
- کفه چپ سبکتر باشد،
- کفه راست سبکتر باشد،
- دو کفه مساوی باشند.
بنابراین هر توزین حداکثر سه حالت را از هم متمایز میکند. پس با `k` توزین، حداکثر `۳^k` دنباله متفاوت از نتایج قابل تشخیص است.
از طرف دیگر، گوی سبکتر میتواند هر یک از `n` گوی باشد. بنابراین باید:
`۳^k ge n`
در نتیجه:
`k ge |~log_۳^n ~|`
پس هیچ الگوریتمی نمیتواند در کمتر از `|~ log_۳^n ~|` توزین مسئله را حل کند.
۲. اثبات کفایت با استقرا
میگوییم اگر
`n le ۳^k`
آنگاه میتوان گوی سبکتر را حداکثر در `k` توزین یافت کرد.
گام پایه اسقرا:
برای `k=۱` ، داریم `n le ۳`.
- اگر `n=۲`، دو گوی را باهم وزن میکنیم و گوی سبکتر مشخص میشود.
- اگر `n=۳`، دو گوی را وزن میکنیم:
- اگر برابر باشند، گوی سوم سبکتر است؛
- در غیر این صورت، کفه سبکتر گوی مورد نظر را نشان میدهد.
یعنی حکم برقرار است.
فرض استقرا
فرض کنید هر مجموعه با حداکثر `۳^k` گوی را بتوان در `k` توزین حل کرد.
گام استقرا:
اکنون فرض کنید:
`n le ۳^(k+۱)`.
گویها را به سه دسته A، B و C تقسیم میکنیم، بهگونهای که اندازه هر دسته حداکثر `۳^k` باشد. دستههای A و B را با هم وزن میکنیم.
- اگر دو کفه برابر باشند، گوی سبکتر در C است.
- اگر کفه چپ سبکتر باشد، گوی در A است.
- اگر کفه راست سبکتر باشد، گوی در B است.
در هر سه حالت، مسئله به مجموعهای با حداکثر `۳^k` گوی کاهش مییابد. طبق فرض استقرا، این زیرمسئله در `k` توزین حل میشود. با احتساب توزین اول، مجموعاً به `k+۱` توزین نیاز داریم.
بنابراین هر مجموعه با حداکثر `۳^{k+۱}` گوی نیز در `k+۱` توزین قابل حل است.
نتیجه:
از استقرا نتیجه میشود که هرگاه
`۳^{k-۱} lt n le ۳^k`
میتوان گوی سبکتر را در `k` توزین پیدا کرد. از طرف دیگر، کران پایین نیز نشان داد که کمتر از `k` توزین ممکن نیست. بنابراین:
`T(n) = |~ log_۳^n ~|`
این مقدار، حداقل تعداد توزین لازم و کافی برای یافتن گوی سبکتر است.
■ مسئله: هر عدد طبیعی بزرگتر از یک حداقل یک مقسوم علیه اول دارد.
اعداد ۱، ۲، ۳، ۴ دارای مقسوم علیه اول هستند.
نشان میدهیم: اگر همه اعداد کوچکتر یا مساوی از عدد اختیاری `k` دارای مقسوم علیه اول باشند
آنگاه
`k+۱` نیز دارای مقسوم علیه اول است.
میگوییم `k+۱` اول است یا اول نیست. اگر اول باشد که اثبات تمام است. اگر اول نباشد پس `k + ۱ = bc`. بنابراین:
`۱ < c < (k + ۱)` و `۱< b < (k + ۱)`.
بنا بر فرض استقر، گیریم `b` دارای مقسوم علیه به فرض `p` است (پس `b/p` عدد صحیح است). بنابراین:
`{k+۱} / p = {bc} / p = b/p c`.
از رابطه بالا برمیآید `{k+۱} / p` عدد صحیح است. این حل مسئله را پایان میدهد.
■ مسئله: `F_n < ۲^n`. [`≺F_n≻` دنباله فیبوناتچی]
`F_۰ = ۰ < ۱ = ۲^۰` و `F_۱ = ۱ < ۲ = ۲^۱`
نشان میدهیم اگر `F_k < ۲^k` برای `k`
آنگاه
`F_{k+۱} < ۲^{k+۱}` نیز دارای مقسوم علیه اول است.
| `F_{k+۱}=` | `F_k + F_{k-۱}` | تعریف دنباله: |
| <`۲^k +۲^{k - ۱}` | بنا بر فرض استقرا داریم:`F_k < ۲^k` | |
| `=۲ xx ۲^(k-۱) +۲^{k - ۱}` | ||
| `=۲^{k-۱} xx (۲ +۱)` | ||
| <`۲^{k-۱} xx ۴` `=۲^{k-۱} xx ۲^۲` `=۲^{k+۱}` |
■ مسئله: تقریب عناصر دنباله فیبوناتچی
«آن چه عددی است که اگر یک واحد از آن بکاهیم وارون آن بدست میآید؟» پاسخ به این پرسش به حل معادله `x-۱= ۱/x` منجر میگردد.
معادله درجه دوم بالا را میتوان به صورت `x^۲- x -۱=۰` نوشت که جوابهای آن به قرار زیر هستند:
`{۱ +- sqrt((-۱)^۲ - ۴ xx(-۱)xx(-۱))}/ ۲ =`
`= {۱ +- sqrt(۵)}/ ۲`
`{۱ + sqrt(۵) }/ ۲` و `{۱ - sqrt(۵) }/ ۲` را بترتیب `phi` و `phi^'` مینامیم. پس:
`phi={۱ + sqrt(۵) }/ ۲` , `phi'={۱ - sqrt(۵) }/ ۲`
اکنون نشان میدهیم:
(I): `F_n = {phi^n - phi'^n} / sqrt(۵)` ; `(n>۰)`
`(phi^۰ - phi'^۰) / sqrt(۵) = ۰ = F_۱`
`(phi^۱ - phi'^۱) / sqrt(۵) = ۱ = F_۱`
میگوییم اگر رابطه (I) به شرح زیر برقرار باشد:
` F_۰, F_۱, ..., F_(k-۱), F_k`
آنگاه
رابطه (I) برای `F_(k+۱)` نیز برقرار است.
| `F_{k+۱}` | =`F_k + F_{k+۱}` | تعریف: `≺F_n≻` |
| =`=(phi^k - phi'^k + phi^(k-۱) - phi'^(k-۱)) / sqrt(۵)` | بنا بر فرض استقرا داریم: | |
| =`{phi^(k-۱)(phi+۱))/sqrt(۵)` - `{phi'^(k-۱)(phi'+۱))/sqrt(۵)` | ||
|
توجه داریم که `phi` و `phi'` ریشههای معادله `x^۲= x + ۱` هستند. بنابراین: `phi^۲ = phi + ۱` و `phi'^۲ = phi' + ۱`. و از اینجا، با جایگذاری داریم: |
||
`F_(k+۱)= {phi^(k-۱)phi^۲ - phi'^(k-۱)phi'^۲ } / sqrt(۵)=` `={phi^(k+۱) - phi'^(k+۱) } / sqrt(۵)=`(I) |
||
■ مثال: تعریف غیربازگشتی توان (`x^n`)
این بند برای مخاطبی با آشنایی کم تا متوسط با برنامهنویسی مفید است.
میتوان بدون
گسست از آن عبور کرد.
تعریف غیربازگشتی توان `x^k` (که در آن:`k in NN; ``x in RR`) به قرار زیر ایت:
| `x^n;` `k` `in NN`; `x in RR` | = | |
| `k=۰` | ۱ | |
| `k>۰` | `ubrace(x xx x xx ... xx x)_("بار-k")` |
همانطور که دیده میشود در این تعریف قید «k-بار» با زیرنوشت «`ubrace(" ")_"بار-k"`» در تعریف گنجانده است.
نسخه کد شده این تعریف در زیر آمده است، که در آن تعداد چرخهها از پیش معین است:
int IterativePower(int x, int k) // `x in RR, k in NN`
{
int power = 1;
if (k == 0) return power;
for (int i=1; i<=k; i++) { power *= x;}
return power;
}
■ مثال: تعریف بازگشتی توان (`x^n`)
آ: گام پایه: توان صفر هر عدد حقیقی را یک تعریف میکنیم (`AA x ∈ NN; x^۰=۱`).
ب: گام استقرایی: برای هر عدد `x in RR` و `k in NN` داریم: `x^k=x^(k-۱) . k`.
⦁ مثال: محاسبه `x^۱`: طبق گام استقرایی داریم: `x^۱=x*x^(۱-۱)`. بنا بر گام پایه: `x^۰=۱`. بنابراین: `x^۱=۱xx x=x`
⦁ مثال: محاسبه `x^۲`: بنا بر دو گام استقرایی و سرانجام گام پایه داریم:
`x^۲=x^۱ xx x = x^۰ xx x xx x`= `۱ xx x xx x = x xx x`.
در زیر تابع `x^k` بطور دقیق تعریف شده است:
| `x^n;` `k` `in NN`; `x in RR` | = | |
| `k=۰` | ۱ | |
| `k>۰` | `x*x^(k-۱)` |
■ نمایش اجرایی تعریف بازگشتی توان
این بند برای مخاطبی با آشنایی کم تا متوسط با برنامهنویسی مفید است. هدف آن، نمایش عینی روند اجرای بازگشتی در سطح حافظه و ساختار دادههاست تا درکی ملموس و غیرانتزاعی از بازگشت ارائه دهد.
میتوان بدون
گسست از آن عبور کرد.
نسخه کد شده تعریف (روند)، که در آن تعداد چرخههای اجرایی از پیش معین نیست، در زیر آمده است:
int RecursivePower(int x, int k) // `x, k in NN`
{
if (k == 0) return 1;
k--;
int p = RecursivePower(x, k);
p = p * x;
return p;
}
شبیه سازی یک مورد اجرایی از کد بالا [`RecursivePower(x, k)`] برای `x=۵` و `k=۳` در زیر آمده است:
در نمودار زیر اجرای روند تعریف بازگشتی توان (`۵ ^ ۳`) آمده است.
شکل ۲. نمایش رایانش توان به روش بازگشتی: (`۵ ^ ۳`)
تصویر فلوچارت اجرای تابع بازگشتی `Power(x, k)` برای مقادیر `x = ۵` و `k = ۳` است که فریمهای متوالی پشته، لوزیهای تصمیمگیری، کاهش k، فراخوانیهای بازگشتی و عملیات ضرب در مسیر بازگشت را تا رسیدن به حالت پایه (`k = ۰`) و محاسبهٔ نتیجهٔ نهایی (۱۲۵) نشان میدهد.
-
0: در 0 اجرای کد اصلی [تابع `Recursive Power(x , k )` برای ورودیهای و `x = ۵` و `k = ۳` ] در حافظه آغاز میشود.
از آنجا که k ≠ ۰ کاردستور `k - -` اجرا میشود که در نتیجه یک واحد از `k` کاسته شده و مقدار آن ۲ خواهد شد.
کاردستور بعدی فراخوان به خود (ارجاع به خود) اما با ورودیهای `k = ۲` و `x = ۵` است.
مکانیسم این خودخوانی (ارجاع به خود) اینگونه است که:
ابتدا مختصات اجرای جاری کد [متغیرها، مقادیر آنها و شماره (آدرس) کار دستور بعدی] در یک ساختار داده بنام پشته ذخیره میشود. سپس اجرای کد (0) با ورودیهای جدید آغاز میشود.
پشته (Stack) یک ساختار داده با یک درگاه ورودی/خروجی است که ورود و خروج (داشت و برداشت) در آن تنها از یک سو و بر اساس قاعده «آخرین ورودی، اولین خروجی / Last In, First Out (LIFO) » انجام میشود.
شکل ۳. محاسبه بازگشتی توان: درج (push) در پشته (stack) در 1 نیز `k ≠ ۰` . بنابراین کاردستور k - - اجرا میشود که در نتیجه یک واحد از `k` کاسته شده و مقدار آن ۱ خواهد شد. کاردستور بعدی فراخوان به خود (ارجاع به خود) اما با ورودیهای `k = ۱` و `x = ۵` است.
شکل ۴. محاسبه بازگشتی توان: درج (push) در پشته (stack) در 2 نیز `k ≠ ۰` . بنابراین کاردستور `k--` اجرا میشود که در نتیجه یک واحد از `k` کاسته شده و مقدار آن ۰ خواهد شد.
کاردستور بعدی فراخوان به خود (ارجاع به خود) اما با ورودیهای `k = ۰` و `x = ۵` است.
شکل ۵. محاسبه بازگشتی توان: درج (push) در پشته (stack) در 0 `k = = ۰` . بنابراین کد با خروجی ۱ پایان مییابد و ادامه آن از کد فراخوان کننده و از آدرس کاردستور بعد از فراخوانی ادامه مییابد. این روند تا کد آغازین [0] به پس میرود و سرانجام با خروجی ۱۲۵ پایان مییابد.
شکل ۶. محاسبه بازگشتی توان: برداشتن (pop) از پشته (stack)
در نمودار زیر تعمیم محاسبه بازگشتی توان آمده است:
شکل ۷. نمایش رایانش توان به روش بازگشتی: (`x ^ k`)
■ ■ ■ ■ ■
 |
 |