Сайтқа презентация қосу

Іздеу. Іздеу есептерінің шешілімі. Іздеу: қайтару арқылы теріп алу

Іздеу.  Іздеу есептерінің шешілімі. Іздеу: қайтару арқылы теріп алу. 

Образец текста
– Второй уровень
Третий уровень
– Четвертый уровень » Пятый уровень

Іздеу  -  берілген мәні бар  элементтердің орнын табу.

Образец текста
Іздеу – Второй уровень
Третий уровень
– Четвертый уровень » Пятый уровень

Тізбектеліп іздеу

Бинарлық іздеу

Образец текста
– Второй уровень Тізбектеліп іздеу. Третий уровень Тізбектеліп іздеудің  мағынасы элементтерді тізбекпен таңдап алуды  – Четвертый уровень » Пятый уровень және элементтерді кілт мәнімен салыстырудан  тұрады. Функция парамертлер ретінде массивті,  элементтер санын және кілт мәнін алады.  Сәйкес элементтің индексін қайталайды, егер  іздеу сәтсіз болса,  -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)
-7 3 5 8

– Второй уровень
Третий уровень
– Четвертый уровень » Пятый уровень
12 16 23 33 55

0              1           2          3           4           5          6           7           8

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  өшірілетін элементке мәндері жағынан жақын  элементтер). 
Третий уровень

Образец текста
– Второй уровень
Третий уровень
– Четвертый уровень » Пятый уровень

Назарларыңызға рахмет!!!!!!


Пән: Математика, Геометрия


Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь