Қазақстан республикасының бiлiм және ғылым министрлiгi
жүктеу/скачать 0,78 Mb.
|
364bd4d0-c314-11e5-bf37-f6d299da70eeМетод лекцииМСП
| Сызықтық іздеу – қажетті элементті массив элементтерін қарапайым бірінен кейін бірін эталонмен салыстыра отырып іздейтін процедура.
Кедергімен сызықтық іздеу – бұл ізделінді элемент массивтің шекаралық a[n+1] элементі болып қосымша енгізіліп, және іздеу үрдісінде a[i]=x болатындай i табылатын іздеу. Ал егер a[i]=x тек қана i=n+1 болса, онда массивте ізделінді элемент жоқ. Көп жағдайда іздеу реттелген массивте жүргізілген тиімді. Бұл жағдайларда тиімді әдістердің бірі – қақ бөлу бойынша іздеу. Қақ бөліп іздеу әдісінде ізделінді эталонды салыстыру массивтің ортасында орналасқан элементпен жүргізіледі, салыстыру нәтижесіне байланысты (артық немесе кем) ары қарай іздеу массивтің не сол жақ жартысында, не оң жақ жартысында жүргізіледі. Тоғыстыру арқылы сүрыптау (Сортировка слиянием; merge sorting) — бірінші кезеңде жазбалар тобы жедел жадта сүрыпталатын өрі бірнеше таспаға жазылатын, ал екінші кезенде реттелген топтар бірнеше таспадан бір таспаға жинақталатын сыртқы сүрыптау. Ағаштармен байланысты ұғымдар кең таралған және интуитивті түсінікті. Ағаштың бірнеше мүмкін анықтамалары бар. Мысалы, графтар көзқарасы жағынан, ағаш деп жиі жағдайда бағытталмаған ұшы белгіленген, циклдары болмайтын, графты атайды. Бізді тек бағытталған ағаштар қызықтыратын болады, бағдарламаушылар көзқарастары жағынан. Сондықтан біз келесі рекурсивті анықтамамен қолданамыз: Т базалық типті R ағашы – бұл немесе (a) бос ағаш (бір де бір ұшы жоқ ), немесе (b) T типті кейбір ұш (ағаштың түбі) соңғы (мүмкін, нөльдік) Т базалық ағаштармен байланысқан санмен (Бұл ағаштар R ағашының ішіндегі ағаштар деп аталады). Бұл анықтамадан келесіні түсінуге болады, біржақты бағытталған тізім ағаш болып аталады. (Сур. 1). Сурет. 2. Графтың бір түрі Ағаштарды әртүрлі бейнеде көрсетуге болады ( бұл тек бірқалыпты иерархиялық құрылым). мысалы, 2 және 3 суреттерінде бір ағаштың екі бейнеленуі көрсетілген, бұл ағаштың базалық типінде латын алфавитінің әріптерінің көпшілігі бар. 3 суреттегі графтық бейнелеу бағдарламалау спецификасына жақынырақ.
Ағаштардың ішіндегі ағаштардың байланыстарын бұтаұтар деп атаймыз, ал әр ағаштың түбін ұшы деп атаймыз. Реттелген деп бұтақтары реттелген ағаштарды атаймыз. Мысалыр, 4 суретте екі реттелген ағаштар айырылады. Сурет.4. Суретте екі бірдей граф көрсетілген Ұштар саны немесе бұтақтар саны x ұшына жолы деп аталады. Биіктігі немесе тереңдігі деп ұштың максималды ұзындығын атаймыз. Сурет 5. Бұтақтары немесе ұштары көп граф. Бақылау сұрақтары «Іріктеу және іздеу әдістері» пәнінің мақсаттары. Ағаштардың мүмкін болатын анықтамаларын атаңыз. Граф деген не? Ұшқа апаратын жолдың ұзындығы деген не? жүктеу/скачать 0,78 Mb. Достарыңызбен бөлісу:
|