def multiply(a, b): # اگر یکی از اعداد صفر باشد، حاصل صفر است if a == 0 or b == 0: return 0 # اگر بی منفی باشد، علامت را تغییر میدهیم if b < 0: return -multiply(a, -b) # حالت پایه: اگر b برابر 1 باشد، a را برمیگردانیم if b == 1: return a # بازگشت: a را به حاصل ضرب a در (b - 1) اضافه میکنیم return a + multiply(a, b - 1) # آزمایش تابع print(multiply(7, 7)) # باید 49 را چاپ کند print(multiply(7, 0)) # باید 0 را چاپ کند print(multiply(3, 30)) # باید 90 را چاپ کند print(multiply(1, 30)) # باید 30 را چاپ کند print(multiply(-2, 3)) # باید -6 را چاپ کند print(multiply(2, -3)) # باید -6 را چاپ کند
کد بالا به زبان پایتون از یک روش بازگشتی ساده برای ضرب دو عدد استفاده میکند. تابع `multiply` به صورت بازگشتی عمل میکند تا عملیات ضرب را به صورت جمعهای متوالی انجام دهد.
- اگر یکی از اعداد `a` یا `b` برابر صفر باشد، تابع بلافاصله مقدار `0` را بازمیگرداند، چرا که هر عددی ضرب در صفر برابر با صفر است.
- اگر `b` منفی باشد، تابع با تغییر علامت `b` آن را به حالت مثبت تبدیل میکند و سپس نتیجه ضرب را منفی میکند (این کار برای سادگی و جلوگیری از پیادهسازی مستقیم ضرب با اعداد منفی انجام شده است).
- اگر `b` برابر 1 باشد، مقدار `a` بازگردانده میشود، زیرا در این صورت `a` باید بدون تغییر برگردد.
- اگر هیچ یک از شروط بالا برقرار نباشد، تابع با کم کردن 1 از `b` و افزودن `a` به نتیجه بازگشت، ضرب را شبیه سازی میکند. این فرآیند شبیه به جمع کردن `a` به تعداد `b` بار است.
این کد به نوعی از الگوریتم تقسیم و غلبه (Divide and Conquer) استفاده میکند. هر بار که تابع بازگشتی فراخوانی میشود، مقدار `b` یک واحد کاهش مییابد، و مسئله به یک مسئله کوچکتر تقسیم میشود تا در نهایت به یک مسئله ساده (ضرب عدد در 1) برسیم.
1. بازگشت (Recursion):
- این کد یک پیادهسازی ساده از بازگشت است. هر مرحله از تابع `multiply` مسئله اصلی را به مسئلهای کوچکتر (با کاهش `b`) تبدیل میکند و در نهایت با رسیدن به شرط پایه نتیجه نهایی را محاسبه میکند.
2. ضرب به صورت جمعهای متوالی (Repeated Addition):
- این روش بازگشتی مبتنی بر جمع متوالی است، که خود یک روش پایه برای ضرب است. در این روش، به جای انجام عملیات ضرب مستقیم، عدد `a` به تعداد `b` بار به خودش اضافه میشود. این روش یک الگوریتم ساده برای شبیهسازی ضرب است.
الگوریتم بهینه تر:
هرچند که این روش صحیح و ساده است، اما از نظر زمانی O(b) زمان میبرد، زیرا باید `b` بار جمع انجام شود. الگوریتمهای بهینهتری برای ضرب دو عدد وجود دارد، مانند الگوریتم ضرب کاراتسوبا (Karatsuba Algorithm) یا ضربهای سریعتر که از تقسیم عدد به بخشهای کوچکتر و ضرب بیت به بیت استفاده میکنند تا زمان ضرب را کاهش دهند.
خلاصه: این کد از روشی ساده و قابل فهم برای ضرب دو عدد استفاده میکند که بر اساس بازگشت و جمعهای متوالی استوار است. این روش در الگوریتمهای پایهای مانند ضرب به روش دانشآموزی کاربرد دارد، اما برای ضرب مقادیر بزرگتر، الگوریتمهای سریعتری نیز وجود دارد.
اکنون کد زیر را به زبان جاوا اسکریپت میتوانید ببینید:
// javascript program to Multiply two integers without // using multiplication, division and bitwise // operators, and no loops /* function to multiply two numbers x and y*/ function multiply( x, y) { /* 0 multiplied with anything gives 0 */ if(y == 0) return 0; /* Add x one by one */ if(y > 0 ) return (x + multiply(x, y-1)); /* the case where y is negative */ if(y < 0 ) return -multiply(x, -y); } // Driver code ( multiply(5, -11)); // This code is contributed by todaysgaurav
