الگوریتم تقسیم

[nafise sadeghi]

فرض کنید a و b دو عدد صحیح باشند و b مخالف صفر باشد. در این صورت اعداد صحیح و یکتایی مانند q و r وجود دارند که a = bq + r؛ r را باقیمانده تقسیم a بر b می‌نامند.

می‌دانیم عددی زوج است که بر 2 بخش‌پذیر باشد،‌و عددی که بر 2 بخش‌پذیر نباشد فرد است. بنابر الگوریتم تقسیم هر عدد صحیح را می‌توان به شکل 2q+r نوشت، که در آن . بنابراین یا r = 0 یا r = 1 . به این ترتیب هر عدد زوج به شکل 2q و هر عدد فرد به شکل 2q + 1 است.

مساله. ثابت کنید مربع هر عدد فرد به شکل 8k + 1 است.
راه‌حل: فرض کنید a عددی فرد باشد. در این صورت عددی صحیح مانند t‌ وجود دارد که a = 2t + 1. در نتیجه

از طرف دیگر، چون از هر دو عدد صحیح متوالی حتماً یکی زوج است، .بنابراین .. در نتیجه عددی صحیح مانند k وجود دارد که 4t(t + 1) = 8k. بنابراین

[صبا محمدي]

تاریخچه جالب الگوریتم تقسیم و حل (تقسیم و غلبه)
اگر تاکنون سری به کتاب های ریاضیات گسسته و ترکیبیاتی زده باشید، حتماً عنوان «روش تقسیم و حل» یا «روش تقسیم و غلبه» را برای حل برخی از مسائل دیده اید. از این روش در طراحی و تحلیل الگوریتم ها بیشتر و کاربردی تر استفاده می شود. در زیر تاریخچه ای جالب درباره این روش که در کتاب طراحی الگوریتم ها نوشته نیپولیتان خوانده ام آورده ام.
راهبرد تقسیم و حل اولین بار توسط ناپلئون، امپراطور فرانسه، در نبرد اوسترلیتز در 2 دسامبر 1805 به کار برده شد. ارتشی مرکّب از سربازان اتریشی و روسی به جنگ با ناپلئون آمده بود که تعداد آنها 15 هزار نفر از افراد ناپلئون بیشتر بود. سپاه اتریشی-روسی حمله ای گسترده علیه فرانسویان آغاز کرد. ناپلئون به قلب سپاه حمله کرد و نیروها را به دو بخش تقسیم کرد. از آنجا که هر یک از دو بخش سپاه به تنهایی از پس ناپلئون بر نمی آمدند، بر آنها تلفات سنگینی وارد آمد. ناپلئون با تقسیم سپاه بزرگ به دو سپاه کوچکتر و پیروز شدن بر تک تک آنها توانست بر سپاه بزرگ غلبه کند.
روش تقسیم و حل از همین راهبرد، روی نمونه ای از یک مسأله استفاده می کند. یعنی نمونه ای از یک مسئله را به دو یا چند نمونه کوچک تر تقسیم می کندو نمونه های کوچک تر معمولاً نمونه هایی از مسئله اصلی هستند. اگر حل نمونه های کوچکتر به راحتی به دست آید، حلّ مسئله اصلی با ترکیب این حل ها به دست خواهد آمد. اگر نمونه های کوچکتر باز هم بزرگتر از آن باشند که به راحتی قابل حل باشند، می توان آنها را به نمونه های کوچکتری تقسیم نمود. این فرآیند آنقدر ادامه می یابد که حل آنها به راحتی امکان پذیر گردد