روش پیدا کردن گنج دفینه زیر خاکی طلا عتیقه و اشیاء باستانی با الگوریتم و گنج یاب
الگوریتم پیشنهادی سایت dafineh.4kia برای یافتن گنج این واقعیت را با استفاده از ابزار ها ی ریاضی تبیین می کند که هنگام یافتن گنج به فاصله دو قدم از مرکز مورد حدس در چهار جهت را باید دفن کرد با فاصله بیست سانت بیست سانت
فرض کنید من در حال تلاش برای یافتن گنج پنهان هستم.
گنج در یک موقعیت ناشناخته x پنهان شده است. می دانیم که موقعیت x گنج جایی در محور عدد صحیح است (به عبارت دیگر x یک عدد صحیح است). برای پیدا کردن گنج باید یک آشکارساز با خودم ببرم. آشکارساز می تواند گنج را فقط در صورتی تشخیص دهد که بالای آن باشد.
موقعیت شروع من نقطه صفر است و می توانم تا زمانی که از گنج عبور کنم به عقب و جلو حرکت کنم تا ردیاب من بتواند آن را ردیابی کند. من همیشه روی خط صحیح حرکت می کنم. کارآمدترین راه برای حرکت در محور به منظور ردیابی گنج کدام است؟ من باید الگوریتمی پیدا کنم که به من اجازه دهد گنج را با طی کردن یک فاصله O(|x|) پیدا کنم.
رویکرد من: پس از بررسی، فکر میکنم کارآمدترین راه برای یافتن گنج به صورت زیر است: از 0 شروع میکنم تا به عدد 2 برسم. سپس به عقب برمیگردم تا به عدد 22- برسم. سپس به سمت جلو حرکت می کنم تا به عدد 23 برسم. سپس دوباره برمی گردم تا به عدد 24- و غیره برسم...
با این حال، من در اثبات وجود یک ثابت c (که باید یک کران بالایی برای آن محاسبه کنم) مشکل دارم تا الگوریتم من به من کمک کند گنج را در c|x| پیدا کنم. حداکثر حرکت می کند هر کمکی بسیار قابل تقدیر است! پیشاپیش متشکرم
روش دوم پیدا کردن گنج بوسیله الگوریتم پیشنهادی
من یک استراتژی مشابه را پیشنهاد خواهم کرد. توجه داشته باشید که استراتژی شما یک عامل ثابت را بهتر از آنچه در اینجا ارائه شده است ارائه می دهد، اما اثبات آن فنی تر است.
اجازه دهید استراتژی را به دورهای 1،2،... تقسیم کنیم، جایی که در دور i 2i-1 قدم به سمت راست می رویم، سپس به مرکز برمی گردیم و دقیقاً همان را به سمت چپ تکرار می کنیم. یعنی یک قدم به سمت راست می رویم سپس به وسط برمی گردیم و یکی به چپ و دوباره برمی گردیم سپس دو تا به راست و دو به چپ و سپس 4 به راست و غیره. تعداد کل پلهها با کران بالا مشخص میشود
4∑i=0⌈logx⌉2i
≤4∑i=0logx+12i
≤4∑i=0log(2x)2i
≤4⋅2log(2x)+1
=4⋅2log (4x)
=16x
که در آن ضریب 4 در خط اول به معنای رفتن به گام های 2i سمت راست و سپس بازگشت به مرکز
برچسب های مهم