АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Метод стрільби

Читайте также:
  1. A) Метод опроса
  2. I. Метод стандартизации
  3. I. Методы выбора инновационной политики
  4. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  5. I. Основные характеристики и проблемы философской методологии.
  6. I.ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
  7. II. ВИРУСОЛОГИЧЕСКИЙ МЕТОД
  8. II. Методологічні засади, підходи, принципи, критерії формування позитивної мотивації на здоровий спосіб життя у дітей та молоді
  9. II. Методы прогнозирования и поиска идей
  10. II. Формальная логика как первая система методов философии.
  11. II. Цитогенетический метод
  12. III. Метод, методика, технология

Якщо у нас немає ніякої додаткової інформації про значення ключів, крім факту впорядкування, то можна припустити, що значення елементів масиву збільшуються від a[1] до a[N-1] більш-меньш "рівномірно". Це означає, що значення x для середнього елементу a[N div 2] буде близьким до середнього арифметичного між найбільшим та найменшим значенням.

Але, якщо шукане значення x відрізняється від указанного, то є деякий сенс для перевірки брати не середній елемент, а "середньо-пропорційний", тобто такий, номер якого пропорційний значенню x (див. рис.).

Тобто ми починаєио поділ масиву не з a[N div 2] –го елемента, а з a[m] –го.

Вираз для m одержано з пропорційності відрізків на малюнку:

В "середньому" цей алгоритм має працювати швидше за двійковий пошук, але у найгіршому випадку буде працювати набагато довше.

2.3. Метод "золотого перерізу"

Деякий ефект дає використання так званого "золотого перерізу". Це число j, що має властивість:

Додатний корень

і є золотим перерізом, a

1 / j = 0.61803398875...

Згідно цього алгоритму відрізок L.. R слід ділити не навпіл, як у двійковому алгоритмі, а на відрізки, пропорційні j та 1, у залежності від того, до якого краю ближче x. Замість оператору

m:=...;

у програму двійкового пошуку слід внести фрагмент

if a[R].key - x < x - a[L].key then m:= L + trunc ((R - L) * (Phi - 1.)) else m:= R - trunc ((R - L) * (Phi - 1.) + 1);

а на початку програми слід задати

const phi = 1.6180339887498948482045868; {(sqrt(5.) + 1)/2; }

Функція Trunc – округляє дробове число до цілого, відкидаючи дробову частину,

функція Round – округляє дробове число до найближчого цілого.


 


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)