برای اینکه درسنامهٔ الگوریتم حریصانهٔ تولید کسرهای مصری به‌خوبی بیاموزید، حتماً روی لینک زیر کلیک کنید و از روش ارائه شده در آن استفاده کنید.

چگونه درسنامه‌های سایت تکمیلی را بخوانیم؟


الگوریتم حریصانه
در قرن سیزدهم میلادی، لئوناردو فیبوناچّی برای تبدیل هر عدد گویای بین صفر و یک به کسر مصری، روشی ارائه کرد. این روش را که به الگوریتم حریصانه مشهور است، با یک مثال شرح می‌دهیم.
می‌خواهیم \(\frac{7}{15}\) را با الگوریتم حریصانه به کسر مصری تبدیل کنیم.
مرحلهٔ اول. بزرگ‌ترین کسر واحد کوچک‌تر از \(\frac{7}{15}\) را پیدا می‌کنیم:
\[\begin{aligned}&{\color{red}\frac{1}{2}\,>\,}\frac{7}{15}\\[7pt]&{\color{green}\frac{1}{3}\,<\,}\frac{7}{15}\cdot\end{aligned}\] پس: \[\begin{aligned}&\frac{7}{15}-\frac{1}{3}=\frac{7}{15}-\frac{5}{15}=\frac{2}{15}\\[7pt]&\Rightarrow\frac{7}{15}=\frac{1}{3}+\frac{2}{15}\cdot\quad(1)\end{aligned}\] مرحلهٔ دوم. در این مرحله باید \(\frac{2}{15}\) را به‌صورت کسر مصری بنویسیم. برای این کار، بزرگ‌ترین کسر واحد کوچک‌تر از \(\frac{2}{15}\) را پیدا می‌کنیم: \[\begin{aligned}&{\color{red}\frac{1}{4}\,>\,}\frac{2}{15}\\[7pt]&{\color{red}\frac{1}{5}\,>\,}\frac{2}{15}\\[7pt]&{\color{red}\frac{1}{6}\,>\,}\frac{2}{15}\\[7pt]&{\color{red}\frac{1}{7}\,>\,}\frac{2}{15}\\[7pt]&{\color{green}\frac{1}{8}\,<\,}\frac{2}{15}\cdot\end{aligned}\]
پس:
\[\begin{aligned}&\frac{2}{15}-\frac{1}{8}=\frac{16}{120}-\frac{15}{120}=\frac{1}{120}\\[7pt]&\Rightarrow\frac{2}{15}=\frac{1}{8}+\frac{1}{120}\cdot\quad(2)\end{aligned}\]
چون \(\frac{1}{120}\) یک کسر واحد است، الگوریتم متوقف می‌شود. پس با توجه به رابطه‌های \((1)\) و \((2)\) داریم:
\[\begin{aligned}\frac{7}{15}&=\frac{1}{3}+\frac{2}{15}\\[7pt]&=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}\cdot\end{aligned}\]بنابراین، \(\frac{7}{15}\) به‌صورت یک کسر مصری با \(3\) جمله نوشته شد.

مثال. ابتدا با الگوریتم حریصانه، هریک از کسرهای زیر را به‌صورت کسر مصری بنویسید. سپس تعداد جمله‌های هر کسر مصری را بشمارید.

الف) \(\dfrac{11}{25}\)

از ما بپرسید

بله! می‌توان یک رابطهٔ ساده ساخت، که با استفاده از آن کسر واحد مورد نظر را پیدا کرد. برای اینکه راحت‌تر بتوانیم چنین رابطه‌ای را معرفی کنیم، ابتدا سقف یک عدد را تعریف می‌کنیم.
سقف عدد \(x\)، کوچک‌ترین عدد صحیح بزرگ‌تر یا مساوی \(x\) است که آن را با \(\lceil x\rceil\) نمایش می‌دهند. (برای پیدا کردن سقف عدد \(x\)، کافی است عدد \(x\) را به بالا رُند کنیم.)
برای مثال، سقف عدد \(2.3\) برابر \(3\)، سقف عدد \(3.8\) برابر \(4\)، سقف \(\frac{5}{3}\) برابر \(2\)، و سقف عدد \(\sqrt{28}\) برابر \(6\)، و سقف عدد \(13\) برابر \(13\) است که آنها را به‌صورت زیر نیز می‌توان نمایش داد:
\[\begin{aligned}\lceil2.3\rceil&=3\\\lceil3.8\rceil&=4\\\Big\lceil\frac{5}{3}\Big\rceil&=2\\\big\lceil\sqrt{28}\big\rceil&=6\\\lceil13\rceil&=13.\end{aligned}\]
به مسئلهٔ خودمان برگردیم! بزرگ‌ترین کسر واحد کوچک‌تر از عدد گویای \(\frac{m}{n}\) برابر است با:
\[\frac{1}{\lceil\frac{n}{m}\rceil}\cdot\]
برای مثال، بزرگ‌ترین کسر واحد کوچک‌تر از \(\frac{2}{15}\) برابر است با:
\[\frac{1}{\lceil\frac{15}{2}\rceil}=\frac{1}{\lceil7.5\rceil}=\frac{1}{8}\cdot\]
یا بزرگ‌ترین کسر واحد کوچک‌تر از \(\frac{8}{75}\) برابر است با:
\[\frac{1}{\lceil\frac{75}{8}\rceil}=\frac{1}{\lceil9.3\rceil}=\frac{1}{10}\cdot\]

ب) \(\dfrac{16}{25}\)

ج) \(\dfrac{23}{32}\)

د) \(\dfrac{19}{49}\)

از ما بپرسید

بله. هر عدد گویای بین صفر و یک را به‌ حالت‌های متفاوتی می‌توان به‌صورت کسر مصری نوشت. برای مثال:
\[\frac{3}{4}=\frac{1}{2}+\frac{1}{4}\cdot\]
از طرفی، داریم:
\[{\color{red}1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}\cdot}\]
بنابراین:
\[\begin{aligned}\frac{3}{4}&=\frac{1}{2}+\frac{1}{4}\times{\color{red}1}\\[7pt]&=\frac{1}{2}+\frac{1}{4}\times\big({\color{red}\frac{1}{2}+\frac{1}{3}+\frac{1}{6}}\big)\\[7pt]&=\frac{1}{2}+\frac{1}{8}+\frac{1}{12}+\frac{1}{18}\cdot\end{aligned}\]
البته، روش بالا باعث می‌شود که تعداد جمله‌های کسر مصری بیشتر شود. روش‌های دیگری نیز هست که (در برخی موارد) با استفاده از آنها می‌توان تعداد جمله‌های کسر مصری را کمتر کرد. برای نمونه، برای هریک از موارد مثال ۳، می‌توان کسرهای مصری زیر را ساخت.
\[\begin{aligned}\frac{11}{25}&=\frac{1}{3}+\frac{1}{15}+\frac{1}{25}\\[8pt]\frac{16}{25}&=\frac{1}{2}+\frac{1}{10}+\frac{1}{25}\\[8pt]\frac{23}{32}&=\frac{1}{2}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}\\[8pt]\frac{19}{49}&=\frac{1}{3}+\frac{1}{21}+\frac{1}{147}\cdot\end{aligned}\]

چون این الگوریتم حریص است و در هر مرحله بزرگ‌ترین کسر واحد مربوطه را انتخاب می‌کند. در برخی موارد، چنین حرصی باعث می‌شود که تعداد جمله‌های کسر مصری زیاد شود و مخرج کسرهای آخر، بسیار بزرگ شوند. برای مثال، اگر با الگوریتم حریصانه، \(\frac{31}{311}\) را به‌صورت کسر مصری بنویسیم، ده‌تا کسر واحد تولید می‌شود که مخرج کسر آخر، \(537\) رقم دارد! در تصویر زیر، الگوریتم حریصانه برای کسر \(\frac{31}{311}\) اجرا شده است. اعداد آبی‌رنگ، مخرج هریک از کسرهای واحد تولید شده در الگوریتم حریصانه هستند.کسر مصری
اگر در پیدا کردن کسر مصری \(\frac{31}{311}\)، حرص نزنیم و در ابتدا به‌جای \(\frac{1}{11}\) از \(\frac{1}{12}\) استفاده کنیم، و در مراحل بعد نیز حریص نباشیم، می‌توانیم کسر مصری زیر را بسازیم:
\[\begin{aligned}\frac{31}{311}=\frac{1}{12}+\frac{1}{63}+\frac{1}{2799}+\frac{1}{8708}\cdot\end{aligned}\]

اولاً، با استفاده از الگوریتم حریصانه می‌توان ثابت کرد که هر عدد گویای بین صفر و یک را می‌توان به‌صورت کسر مصری نوشت(؟).
ثانیاً، فرض کنید \(\frac{m}{n}\) یک عدد گویا بین صفر و یک باشد و کسر مصری آن را با استفاده از الگوریتم حریصانه تولید کرده باشیم. در این‌صورت تعداد جمله‌های این کسر مصری حداکثر \(m\)تاست(؟).

ماشین‌حساب حریصانه

اگر به زبان‌های برنامه‌نویسی مسلط باشید، با چند خط برنامه‌نویسی، به‌سادگی می‌توانید یک ماشین‌حساب کسر مصری تولید کنید. البته، با جستجوی “Egyptian fraction calculator” در گوگل نیز، می‌توانید از ماشین‌حساب‌های آنلاین کسر مصری استفاده کنید. در زیر، لینک یکی از این ماشین‌حساب‌ها قرار داده شده است.

ماشین‌حساب حریصانه

پرسش‌هایی دربارهٔ کسرهای مصری

پرسش ۱. چه کسرهایی را می‌توان به‌صورت مجموع دو کسر واحد نوشت؟
پرسش ۲. چه کسرهایی را می‌توان به‌صورت مجموع سه کسر واحد نوشت؟
پرسش ۳. آیا روشی برای ساختن کسر مصری وجود دارد که تعداد جمله‌های آن، کمترین تعداد ممکن باشد؟
پرسش ۴. آیا روشی برای ساختن کسر مصری وجود دارد که مخرج کوچک‌ترین کسر واحد به‌کار رفته در کسر مصری، کمترین مقدار ممکن باشد؟
پرسش ۵. فرض کنید \(n\) یک عدد طبیعی بزرگ‌تر از \(2\) باشد. اگر با الگوریتم حریصانه، کسر مصری \(\frac{2}{n}\) را تولید کنیم، آیا این کسر مصری، همیشه \(2\) جمله دارد؟
پرسش ۶. فرض کنید \(n\) یک عدد طبیعی بزرگ‌تر از \(3\) باشد. آیا روشی وجود دارد که برای \(\frac{3}{n}\) یک کسر مصری با \(3\) جمله تولید کند؟ با \(2\) جمله چطور؟
پرسش ۷. فرض کنید \(n\) یک عدد طبیعی بزرگ‌تر از \(4\) باشد. آیا روشی وجود دارد که برای \(\frac{4}{n}\) یک کسر مصری با \(4\) جمله تولید کند؟ با \(3\) جمله چطور؟

در جلسه‌های بعد به برخی از پرسش‌های بالا پاسخ داده می‌شود.

معمای کسرهای مصری

ویدئوی زیر دربارهٔ تاریخچه، کاربردها، و الگوریتم تولید کسرهای مصری است.

تمرین‌های بیشتر

برای درک عمیق‌تر الگوریتم حریصانه، حتماً تمرین‌های این جلسه را حل کنید.

تمرین‌های الگوریتم حریصانه

 

اشتراک
اطلاع از
5 Comments
Inline Feedbacks
مشاهده همه نظرات

ببخشید در الگوی بالا در قسمتی که اعداد واحد را عدد ورد نظر مقایسه می کنیم ،عددی مساوی آمد چی کار کنیم؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

ممنون

سلام دیگه اشتراک 6 ماهه ندارید همش یه ماهس؟!