با توجه به مجموعه ای از اعداد صحیح []. پیدا کردن یک عنصر اوج یعنی یک عنصر است که کوچکتر از همسایگان خود نیست.
توجه: برای عناصر گوشه ای باید فقط یک همسایه را در نظر بگیریم.
مثال:
ورودی: مجموعه ای[]= خروجی: 20 توضیح: عنصر 20 دارای همسایگان 10 و 15 است که هر دو کمتر از 20 هستند.
ورودی: مجموعه ای[] = خروجی: 20 یا 90 توضیح: عنصر 20 همسایگان 10 و 15, هر دو کمتر از 20, به طور مشابه 90 همسایه 23 و 67.
موارد گوشه زیر ایده بهتری در مورد مشکل می دهد.
- اگر مجموعه ورودی در یک نظم به شدت افزایش طبقه بندی شده اند, عنصر گذشته است که همیشه یک عنصر اوج. مثلا, 50 عنصر اوج در است .
- اگر مجموعه ورودی در یک نظم به شدت کاهش طبقه بندی شده اند, اولین عنصر است که همیشه یک عنصر اوج. 100 عنصر اوج در است .
- اگر تمام عناصر از مجموعه ورودی یکسان هستند, هر عنصر یک عنصر اوج است.
از مثالهای بالا مشخص است که همیشه یک عنصر اوج در مجموعه ورودی وجود دارد.
رویکرد ساده لوحانه: در زیر ایده حل مشکل وجود دارد
مجموعه ای را می توان طی و عنصر که همسایگان کمتر از این عنصر را می توان بازگشت.
برای اجرای ایده مراحل زیر را دنبال کنید:
- اگر عنصر اول بزرگتر از دوم است یا عنصر گذشته بیشتر از گذشته دوم است, چاپ عنصر مربوطه و خاتمه برنامه.
- دیگر گذشتن از مجموعه ای از شاخص دوم به شاخص دوم یعنی 1 به ن-1
- در صورتی که از هر دو گروه بزرگتر باشد و از هر دو گروه بزرگتر باشد و سپس این عنصر را چاپ کند و خاتمه دهد.
در زیر اجرای ایده فوق است.
پایتون 3
جاوا اسکریپت
پیچیدگی زمانی: یک پیمایش لازم است بنابراین پیچیدگی زمانی ای(ن)است
فضای کمکی: ای(1), هیچ فضای اضافی مورد نیاز است, بنابراین پیچیدگی فضا ثابت است
با استفاده از جستجوی باینری بازگشتی یک عنصر اوج پیدا کنید
در زیر ایده برای حل مشکل است.
با استفاده از جستجوی باینری, بررسی کنید که عنصر میانی عنصر اوج است یا نه. اگر عنصر میانی است که عنصر اوج نیست, سپس بررسی کنید اگر عنصر در سمت راست بزرگتر از عنصر میانی است و سپس همیشه یک عنصر اوج در سمت راست وجود دارد . اگر عنصر در سمت چپ بزرگتر از عنصر وسط است و سپس همیشه یک عنصر اوج در سمت چپ وجود دارد .
برای اجرای ایده مراحل زیر را دنبال کنید:
- ایجاد دو متغیر, ل و ر, مقداردهی اولیه ل = 0 و ر = ن-1
- به صورت بازگشتی مراحل زیر را انجام دهید تا ل , یعنی پایین تر از حد بالا است
- بررسی کنید که ارزش اواسط یا شاخص عنصر اوج است یا نه, اگر بله پس از چاپ عنصر و خاتمه.
- دیگری اگر عنصر در سمت چپ عنصر وسط بیشتر است سپس برای عنصر اوج در سمت چپ بررسی, به عنوان مثال تحقیق به روز رسانی = اواسط-1
- دیگری اگر عنصر در سمت راست عنصر وسط بیشتر است سپس برای عنصر اوج در سمت راست یعنی به روز رسانی را بررسی کنید
در زیر اجرای رویکرد فوق است
پایتون 3
جاوا اسکریپت
پیچیدگی زمانی: ای(ورود به سیستم) جایی که ن تعداد عناصر موجود در مجموعه ورودی است. فضای کمکی: ای (ورود ن), به عنوان پاسخ بازگشتی وجود دارد, از این رو پشته ضمنی استفاده شده است.
با استفاده از جستجوی باینری تکراری یک عنصر اوج پیدا کنید
در زیر ایده برای حل مشکل است.
با استفاده از جستجوی باینری, بررسی کنید که عنصر میانی عنصر اوج است یا نه. اگر عنصر وسط عنصر اوج خاتمه حلقه در حالی که و چاپ عنصر وسط , سپس بررسی کنید اگر عنصر در سمت راست بزرگتر از عنصر وسط است و سپس همیشه یک عنصر اوج در سمت راست وجود دارد . اگر عنصر در سمت چپ بزرگتر از عنصر وسط است و سپس همیشه یک عنصر اوج در سمت چپ وجود دارد .
برای اجرای ایده مراحل زیر را دنبال کنید:
- ایجاد دو متغیر, ل و ر, مقداردهی اولیه ل = 0 و ر = ن-1
- یک حلقه در حالی اجرا کنید تا ل, پایین تر از حد بالا است
- بررسی کنید که ارزش اواسط یا شاخص عنصر اوج است یا نه, اگر بله پس از چاپ عنصر و خاتمه.
- دیگری اگر عنصر در سمت چپ عنصر وسط بیشتر است سپس برای عنصر اوج در سمت چپ بررسی, به عنوان مثال تحقیق به روز رسانی = اواسط-1
- دیگری اگر عنصر در سمت راست عنصر وسط بیشتر است سپس برای عنصر اوج در سمت راست یعنی به روز رسانی را بررسی کنید
کد زیر داده شده نسخه تکراری از بالا توضیح داده شده و نشان داده بازگشتی بر اساس تقسیم و تسخیر روش است.
