مقدمه
ما در حال پرتاب یک موشک اکتشاف فضای عمیق هستیم و به راهی نیاز داریم که مطمئن شویم سیستم ناوبری روی هدف می‌ماند.
در اولین قدم محاسبه، یک عدد هدف می‌گیریم و «جذر» آن را پیدا می‌کنیم (یعنی عددی که وقتی در خودش ضرب شود، برابر با عدد هدف می‌شود).
سفر بسیار طولانی خواهد بود.
برای اینکه باتری‌ها تا حد امکان دوام بیاورند، مجبور شدیم کامپیوتر داخلی موشک‌مان را خیلی کم‌مصرف بسازیم.
متأسفانه این یعنی نمی‌توانیم به کتابخانه‌ها و توابع پیچیده‌ی ریاضی تکیه کنیم، چون انرژی بیشتری مصرف می‌کنند.
در عوض می‌خواهیم محاسبه‌ی جذر خودمان را پیاده‌سازی کنیم.
دستورالعمل‌ها
وظیفه‌ی شما محاسبه‌ی «ریشه‌ی دوم» یک عدد داده‌شده است.
- بهتر است از کتابخانه‌های ریاضی آماده‌ی زبان خودتان استفاده نکنید.
- به عنوان ورودی، یک عدد صحیح مثبت دریافت می‌کنید، یعنی ۱، ۲، ۳، ۴…
- فقط لازم است مواردی را مدیریت کنید که نتیجه‌شان یک عدد صحیح مثبت است.
چند رویکرد بالقوه:
- جست‌وجوی خطی یا دودویی برای یافتن عددی که وقتی به توان دو می‌رسد، عدد ورودی را به دست می‌دهد.
- تقریب‌های متوالی با روش نیوتون یا هرون.
- محاسبه‌ی یک رقم در هر گام یا یک بیت در هر گام.
می‌توانید صفحه‌های ویکی‌پدیا درباره‌ی ریشه‌ی دوم صحیح و روش‌های محاسبه‌ی ریشه‌ی دوم را ببینید؛ این صفحه‌ها در انتخاب روش محاسبه به شما کمک می‌کنند.
ساختار این تمرین در Python
Python مجموعه‌ی غنی‌ای از توابع ریاضی را در قالب ماژول math و توابع توکار مانند عملگر توان **، pow() و sum() ارائه می‌دهد.
اما از شما می‌خواهیم چالش حل این تمرین را بدون آن توابع توکار یا ماژول‌ها هم در نظر بگیرید.
هرچند فرمولی ریاضی وجود دارد که جذر هر عددی را پیدا می‌کند، ما مسیری را برگزیده‌ایم که در آن فقط اعداد طبیعی (اعداد صحیح مثبت) به‌عنوان پاسخ پذیرفته می‌شوند.
می‌توان جذر هر عدد طبیعی را فقط با استفاده از اعداد طبیعی محاسبه کرد.
