Іздеу. Іздеу есептерінің шешілімі. Іздеу: қайтару арқылы теріп алу
Презентация қосу
Іздеу. Іздеу
есептерінің
шешілімі. Іздеу:
қайтару арқылы
теріп алу.
Іздеу - берілген мәні бар
элементтердің орнын табу.
Іздеу
Тізбектеліп іздеу
Бинарлық іздеу
Тізбектеліп іздеу. Тізбектеліп іздеудің
мағынасы элементтерді тізбекпен таңдап
алуды және элементтерді кілт мәнімен
салыстырудан тұрады.
Функция парамертлер ретінде массивті,
элементтер санын және кілт мәнін алады.
Сәйкес элементтің индексін қайталайды, егер
іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп
іздеу кез келген тізбек үшін қолайлы,
тізбектеліп іздеудің орталық тиімділігі O(n)
тең болады.
Бинарлық іздеу.
Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана
қолданылады. Мысалы элементтер тұратын массив берілсін.
Тізімнің басындағы және соңындағы элементтердің
индекстері мынадай low=0 high=n-1 дейін болады.
Бинарлық іздеудің алгоритмі:
Массивтің ортаңғы элементінің индексін табу:
mid=(low+high)/2.
Орталық элементтің мәнін кілтпен салыстыру «Key». Егер
салыстыру нәтижесінде сәйкестік бар болса, онда mid
индексін кілтті табу үшін қолданамыз. Егер орталық
элемент мәні кілттен кіші болса, онда қарастырылып
отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз.
Егер керісінше үлкен болса, онда сол жақтағы бөлігінде
іздеу жүргіземіз.
Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын
береміз.
Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген
элементі бар табу керек.
Мысал элементтері: А
0 1 2 3 4 5 6 7 8
-7 3 5 8 12 16 23 33 55
Low=0
High=8
mid=4
33>A(mid)
0 1 2 3 4 5 6 7 8
-7 3 5 8 12 16 23 33 55
mid
Low=5
High=8
mid=6
33>A(mid)
0 1 2 3 4 5 6 7 8
-7 3 5 8 12 16 23 33 55
Low=7
High=8
mid=7
33=A(mid)
Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық
іздеуде 3 салыстыру жүргізіледі.
Екілік іздеу тармақтары программалауда кең таралған. Екілік
іздеу тармақтарының әрбір төбесінің мәні:
1. Оның сол жағындағы бұтақ төбесінің кез келген мәнінен
үлкен немесе тең.
2. Оның оң жақ бұтағының төбесінің кез келгенінің мәнінен
кіші.
Сызықтық құрылғылар үшін тізбектеліп іздеу алгоритмінің
күрделілігі – О(n) –ға тең. Мұндағы n-құрылым элементтер саны.
Ал аяқталатын бинарлық тармақ үшін күрделілігі – О(log2n)-ға
тең.
Мысалға: 10000 элементтен тұратын тізімде тізбектеп іздеуде
салыстырудың максимальды саны 10000-ға тең болады. Ал
аяқталған тармақта іздеу 14 салыстырудан аспас еді.
Екілік іздеу тармағына элементті осу алгоритмі
(тармақты қарау үнемі түбірден басталады):
1. тармаққа қосылатын мән ағымдағы түйін мәніне
салыстырылады.
2. Егер тармаққа қосылтын мән ағымдағы түйін
мәнінен кіші болса, онда келесілер тексеріледі:
а) егер ағымдағы түйінде ұрпақтар жоқ болса, онда
жаңағы мәні бар түйінді сол жақ ұрпақ ретінде
бекітеміз.
б) әйтпесе, (егер ұрпақ болса) тармақтың сол жақ
бұтағы арқылы бір деңгейге төмендетеміз.
3. Егер тармаққа қосылатын мән ағымдағы түйін
мәнінен үлкен немесе тең болса, келесілер тексеріледі:
а) егер оң жақтағы ағымдағы түйінде ұрпақтар жоқ
болса, онда мәні бар түйінді оң жақ ұрпқ ретінде
бекітеміз.
Екілік іздеу тармағынан элементті алып тастау.
Тармақтан элементті алып тастау алгоритмі тармақтағы
осы элементтің орналасқан орнына тәуелді болады және
келесі төрт жағдайды қамтиды:
1. Мәні х-ке тең болатын элемент жоқ.
2. Мәні х-ке тең болатын элемент терминальды түйін
болып табылады.
3. Мәні х-ке тең болатын элемент бір ғана ұрпақты
болады.
4. Мәні х-ке тең болатын элемент екі ұрпақты болады.
Бір ғана ұрпағы болатын элементті алып тастауда
ешқандай күрделілік жоқ. Мұндай әрекеттер сызықтық
тізімдегі элементті алып тастауға ұқсас болады.
Егер элемент екі ұрпақты болса, онда екі бағытта
бір ғана сілтемемен көрсетуге келмейді. Бұл
жағдайда өшірілетін элементті ауыстыруға тура
келеді. Ауыстыратын элемент үшін оның сол
жақтағы ең оң жақты элемент, ал оң жақтағы сол
жақты элемент таңдап алынады (6 және 8
өшірілетін элементке мәндері жағынан жақын
элементтер).
Назарларыңызға
рахмет!!!!!!
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz