از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
سرفصلهای مطلب
معرفی
جستجوی فیبوناچی یکی از آن الگوریتم های جالبی است که زیبایی و ظرافت علم کامپیوتر را به ما نشان می دهد. مستقر روی دنباله معروف فیبوناچی، که در آن هر عدد مجموع دو عدد قبلی است، تکنیک جستجوی فیبوناچی یک الگوریتم جستجوی مبتنی بر مقایسه است که این مفهوم ریاضی را برای یافتن یک عنصر در یک آرایه مرتب شده به کار می‌گیرد.
اکنون، ممکن است تعجب کنید که چگونه کار می کند، و حتی مهمتر، و چگونه می توانیم آن را در جاوا اسکریپت پیاده سازی کنیم؟! هدف من در این مقاله کوتاه همین است.
جستجوی فیبوناچی
جستجوی فیبوناچی از رویکرد تقسیم و غلبه برای جستجوی یک عنصر در یک آرایه مرتب شده با استفاده از خواص طلایی دنباله فیبوناچی استفاده می کند. با ایجاد مجموعه ای از اعداد فیبوناچی که به عنوان شاخص عمل می کنند، جستجو مکان های ممکن را با کمک این اعداد محدود می کند.
توجه داشته باشید: الگوریتم جستجوی فیبوناچی به ویژه برای مجموعه داده های بزرگ کارآمد است، زیرا پیچیدگی زمانی متوسط O(log n) را ارائه می دهد.
پیاده سازی جستجوی فیبوناچی در جاوا اسکریپت
بنابراین، اجازه دهید به نوشتن یک تابع برای انجام جستجوی فیبوناچی بپردازیم. در اینجا ممکن است کد ما شبیه به آن باشد:
function fibonacciSearch(arr, x) {
let fibM2 = 0;
let fibM1 = 1;
let fibM = fibM2 + fibM1;
const length = arr.length;
// Create a Fibonacci sequence greater than or equal to the array length
while (fibM < length) {
fibM2 = fibM1;
fibM1 = fibM;
fibM = fibM2 + fibM1;
}
let offset = -1;
while (fibM > 1) {
let i = Math.min(offset + fibM2, length - 1);
if (arr(i) < x) {
fibM = fibM1;
fibM1 = fibM2;
fibM2 = fibM - fibM1;
offset = i;
} else if (arr(i) > x) {
fibM = fibM2;
fibM1 = fibM1 - fibM2;
fibM2 = fibM - fibM1;
} else {
return i;
}
}
if (fibM1 && arr(offset + 1) == x) {
return offset + 1;
}
return -1;
}
شما می توانید این تابع را با فراخوانی آن با آرایه مرتب شده و عنصری که می خواهید پیدا کنید استفاده کنید. سپس باید موقعیت عنصر مورد نظر را برگرداند.
چگونه کار می کند؟
- ایجاد دنباله فیبوناچی: کد دو عدد اول فیبوناچی را مقداردهی اولیه می کند و یک دنباله ایجاد می کند تا زمانی که عددی بزرگتر یا مساوی طول آرایه را پیدا کند.
- تقسیم آرایه: سپس آرایه را به دو قسمت تقسیم می کند و بررسی می کند که آیا عنصر در قسمت اول یا دوم قرار دارد.
- تکرار فرآیند: process سپس با زیرآرایه جدید تکرار می شود، و process تا زمانی که عنصر پیدا شود یا اندازه زیرآرایه صفر شود ادامه می یابد.
جستجوی فیبوناچی آرایه را بر اساس تقسیم می کند روی اعداد فیبوناچی، که تقسیم را به نسبت طلایی نزدیک می کند.
نتیجه
جستجوی فیبوناچی به عنوان یک کاربرد جالب از اصول ریاضی در الگوریتم های کامپیوتری است. پیاده سازی آن در جاوا اسکریپت دیدگاه جدیدی را ارائه می دهد روی مدیریت کارآمد داده های مرتب شده این الگوریتم نه تنها ویژگی های جالب تقارن ریاضی در علوم کامپیوتر را آشکار می کند، بلکه راه حلی قوی برای جستجوی مجموعه داده های بزرگ به ما می دهد.
منتشر شده در 1403-01-03 11:57:03
