Зертханалық жұмыс №4

Тақырыбы:Іздеу есебін шешу.

Жалпы мәлімет

Массивтер көбінесе статистикалық мәліметтер, анықтамалық баслымдар, сөздіктер дайындауда қолданылады. Ақпаратты іздеудің ең қарапайым әдісі бұл жағдайда массивтың барлық элементтерін тізбектеп қарап шығу болып табылады. Іздеуді жеңілдету мақсатында массив мазмұны белгілі әдістермен сұрыпталып, реттеледі.

Мысалы: Реттелген массивте керекті элементті іздеу есебін және оны шешу алгоритмін қарастырайық.

N элементтен тұратын нақты сандардың А реттелген массивы берілген. Массивте В саны бар ма, егер бар болса оның массивтегі номерін анықтау керек.

А массивында В –ға тең элемент бар болып, A[p]=B болатындай қандай да бір p индексі бар болсын. Кез-келген салыстырудың A[s]<B (1<s<n) нәтижесі бойынша біз p 1 ден s ке дейінгі диапазонда жатыр ма, әлде s+1 ден n –ге дейінгі диапазонда жатыр ма жылдам анықтай аламыз. Екінші жағдай A[s]<B теңсіздігі дұрыс болса орындалады, ал біріншісі дұрыс емес болса орындалады. Осы салыстырудың қасиеті ортасынан бөлу алгоритмінде қолданылады.

Ортасынан бөлу алгоритмі

Алдымен массивтың шеткі элементтері 1 мен n – ді элементті іздеу шекраралары ретінде алады да, осы шекараларды қадамнан кейін қадам жүргізе отырып, бір-біріне сәйкес келгенше жалғастыра береді: B ны A[s] пен, мұнда s - шекаралардың арифметикалық ортасының бүтін бөлігі, егер A[s]<B, онда бұрынғы төменгі шекараны s+1 ге ауыстыру керек, ал жоғарғы шекара өзгеріссіз қалады, әйтпесе төменгі шекара өзгеріссіз қалып, жоғарғыны s ке ауыстырады. Программа түрінде бұл былайша беріледі, фрагментте p мен q айтылған жоғарғы және төменгі шекараларды көрсетеді:

p:=1; q:=n;

while p<q do

begin

s:=(p+q) div 2;

if a[s]<b then p:=s+1

else q:=s;

end;

Схема түрінде іздеу процесін келесі схема түрінде бейнелеуге болады:

+-------------------------0-------------------------------+

¦ +---------------1---------------¦

¦ +-------2--------+ ¦

¦ ¦ +----3---¦ ¦

¦ ¦ +--4-+ ¦ ¦

¦ ¦ +-5+ ¦ ¦ ¦

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Ортасынан бөлу алгоритмі жоғары тез әрекеттілікке ие. Негізінен ортасынан бөлу алгоритмінің идеясы көптеген алгоритмдер құруда пайдалы болып табылады. Алгоритмнің негізгі мәні «бөліп ал да, өкіміңді жүргіз» мағынасына келеді.

Бақылау сұрақтары:

1. Ортасынан бөлу әдісімен элементті іздеу идеясы неменеге негізделген?

2. Ортасынан бөлу әдісімен массив элементін іздеу алгоритмін жасаудағы әрекеттер тізбегін сипатта.

Тапсырмалар варианттары:

1. 15 элементті массивті клавиатурадан енгізген бүтін сандардан сақтау программасын жаса. Массивтың мазмұны өсу реті бойынша сұрыпталады. Осыдан кейін, клавиатурадан бақылау саны енгізіледі де, массивте бар-жоғы тексеріледі. Бар болса, массивтің элементі номері монитор экранына шығарылады.

2. Массивте 10 әртүрлі бүтін сандарды сақтауды ұйымдастыратын программа жаса. Массивтың мазмұны өсу реті бойынша сұрыпталады. Осыдан кейін, клавиатурадан бақылау саны енгізіледі де, массивте бар-жоғы тексеріледі. Бар болса, массивтың бақылау санына тең элементі нольмен ауыстырылады да, массив монитор экранына шығарылады.

3. Массивте 15 әртүрлі бүтін сандарды сақтауды ұйымдастыратын программа жаса. Массивтың мазмұны кему реті бойынша сұрыпталады. Осыдан кейін, клавиатурадан бақылау саны енгізіледі де, массивте бар-жоғы тексеріледі. Бар болса, экранға бақылау санына дейінгі массив мазмұны шығарылады.