а~ашты~ т~бесін береміз 25 саны жиымны~ ал~аш~ы элементі; 2 кейінгі элементті оны~ а~аш т~бесінен кіші бо
Работа добавлена на сайт samzan.net:
10. Бинарлы ағаш тұрғызу алгоритмі және олардың арнайы ерекшеліктері.
Бинарлы ағаш массивті реттеу үшін қолданылады.
Мысал арқылы түсіндірейік: 25,31,7,4,10,18,5,13 сан жиымы берілсін.
Алгоритм:
1) ағаштың төбесін береміз 25 саны (жиымның алғашқы элементі);
2) кейінгі элементті оның ағаш төбесінен кіші болса сол жақтан, үлкен болса оң жақтан бұтақ арқылы орналастырамыз;
3) кейінгі элементтердің орындары да олардың түбірден кіші немесе үлкен болуына байланысты сол жаққа немесе оң жаққа бұтақ арқылы орналастырып отырамыз.
31 25-тен үлкен оң жақта, ал 7 кіші ол сол жақта орналасады:
25
7
31
4-ті 25 пен салыстырамыз, 4 кіші 25-тен 25-тің сол жағына, 4-ті 7-мен салыстырамыз, 4 кіші 7-ден 7-нің сол жағына орналастырамыз. 10-ды 25-пен салыстырамыз, 10 кіші 25-тен 25-тің сол жағына, 10-ды 7-мен салыстырамыз, 10 үлкен 7-ден 7-нің оң жағына орналастырамыз.
25
7
31
4
10
18, 5, 13 сандары 25-тен кіші болғандықтан сол жақта орналасады. 18 7-ден үлкен және 10-нан да үлкен, 18 7-нің оң жағына және 10-ның оң жағына орналасады. 5 7-ден кіші және 4-тен үлкен, 5 7-нің сол жағына және 4-тің оң жағына орналасады. 13 7-ден үлкен, 10-нан үлкен, 18-ден кіші, 13 7-нің оң жағына, 10-ның оң жағына және 18-дің сол жағына орналасады.
25
7
31
4
10
18
5
13
Ескере кетейік, сол жақ бұтақта белгіленген түбірден кіші элементтер, ал оң жақ бұтақта белгіленген түбірден үлкен элементтер орналасады.
11.Толықтау бинарлы ағаш.
Анықтама. Бинарлы ағаштың өсу нүктесі деп вакантты бағыт бойынша жаңа қабырға тұрғызуға болатын төбені айтады.
1 1-ші деңгей
2 3 2-ші деңгей
3-ші деңгей
Егер бинарлы ағаштың барлық өсу нүктелері соңғы деңгейде орналасса, онда ол толық деп аталады. Толық ағаштың ақырғыларынан өзге әрбір төбесі екі тікелей ұрпаққа ие болады, ал түбірден басталатын және ақырғы төбеде аяқталатын барлық жолдардың ұзындығы бірдей болады және бұл кезде мұндай жолдағы әрбір қабырға бір ғана рет өтіледі.
Толық бинарлы ағаштың k деңгейіндегі төбелердің саны n мынаған тең болады:
Толық ағаштағы элемент іздеу жылдам орындалады, ең көп дегенде log 2 n салыстыру жасалады, бірақ бастапқы массивте «екінің дәрежесі минус бір» тең элементтер саны болады деген үміт үлкен емес. Осыған байланысты толықтау ағаш түсінігін қарастырайық, бұл типті ағашты теңестірілген дейді және оны элементтер саны еркін алынатын массив үшін тұрғызуға қолдануға болады.
Бинарлы ағашты толықтау дейміз, егер оның барлық өсу нүктелері осы ағаштың тек соңғы және соңғының алдындағы деңгейлерде орналасса.
Кейде мұндай ағашты толықтау баланстандырылған деп те атайды.
Егер толықтау ағашта m деңгейінен жоғары төбелер жоқ десек, онда элементті іздеуге қажетті салыстырулардың максималды саны былай бағаланады:
log 2 n < m≤ log 2 n+1
яғни, толықтау ағаш үшін іздеу есебі оптималды болса – минималды уақытта шешіледі, яғни салыстыру саны минималды болады. Толықтау ағаш тұрғызу алгоритмі күрделі емес, бірақ бұл ағаштардың айтарлықтай кемшіліктері бар. Егер массив статикалы болса, яғни, элементтер саны да , элементтің өзі де өзгермесе, онда толықтау ағашты іздеуге қолдану негізді болып табылады. Мұндай ағашты ұйымдастыруға бір рет уақыт жұмсаса, ары қарай тек іздеу есебі ғана жүргізіледі және ол тиімді болады. егер массивтің элементтері периодты түрде өзгерсе н/е қосылса н/е алынатын болса, онда бұл басқа бір мәселе.
2-блок.
20.Шелл сұрыптауы (Shell_sort) және оның ерекшеліктері.
Айырбастаумен сұрыптайтын алгоритм. Бұл сұрыптау алгоритмнің класының өкілдері ретінде бұдан бұрын қарастырылған көпіршікпен сұрыптау, сонымен қатар Шеллдың сұрыптау алгоритмі, тез реттеу алгоритмі, т.б. алгоритмдер мысал бола алады. Шеллдың реттеу алгоритмін қарастырсақ. Шеллдың реттеу алгоритмі көпіршіктік сұрыптау алгоритмін жалпылайды. Салыстырылатын бастапқы массивтің екі жақын орналасқан элементтерін ғана емес, бекітілген d қашықтықта орналасқан элементтерді де салыстырады. Бірінші қадамда массивтің жарты ұзындығына орналасқан элементтерді салыстырады, яғни тең. Келесі қадамда деп есептелінеді., ары қарай қашықтықтағы элементтер салыстырылып қажет жерде алмастырылып отырады. Осы процедураның соңғы кезеңдерінде элемент/ арасында қашықтық болған кезде алмастыру қажет етпеуі мүмкін, себебі алғашқы кезеңдерде салыстырылып ж/е алмастырылған элементтер өз орындарында орналасқанынан болады. Яғни кезеңдердің айналуына байланысты алмастыру саны төмендей береді екен. Шеллдың реттеу алгоритмінің жұмысын мысалмен көрсетсек:
Шеллдың реттеу алгоритмінің модификацияланған нұсқасы:
Procedure q.Shellsort(a,n);
……
begin
k:=n div 2;
while k 1 do
begin for i:=k+1 to n do
if a[i-k]>a[i] then
begin
r:=a[i]; j:=i-k;
L: a[j+k]:=a[j];
if a[j-k]>r then
begin
j:=j-k; goto L;
end; end;
a[j]:=r;
end;
k:=k div 2;
end; end;
Тәжірибе жүзінде қарастырылған бастапқы массив үшін Шеллдың реттеу алгоритмі үш қадамнан кейін реттелген массив құрады:
Тәжірибе жүзінде Шеллдың модификацияланған сұрыптау алгоритмін басқа сұрыптау алгоритмдерімен салыстыру нәтижесінде, оның өнімділігінің есептелінген бағасы жоғары екендігіне көз жеткізуге болады. Программадағы қолданылған L белгісіне қатысты оператор аз өзгерістерге ұшырайды. L белгісінен кейін орналасқан 2 ішкі шарт/ды процедураның модификацияланған вариантында жекелеп жазуға болады және go to операторын қолданбай өзгертуге болады. Кез келген жағдайда шартымен шартты операторды while операторымен алмастыруға болады. Алмастырған кезде 2ші шарт өзгермейді.
Shellsort процедурасы үшін d мән/ң тізбегін тандау өте маңызды және алгоритмнің эффективтілігін атнықтайды. Айтылып отырған эффективтілігін бағалау салыстыруларына тең. боолған жағдайда стандартты Шелл сұрыптау процедурасының бағасы O(n3/2) салыстыруға тең болады. Осы баға процедураның шапшаңдығының бағасы ретінде анықталады[2].
2. Основні теги і атрибути. Встановлення параметрів сторінки сайту
3. Варианты понимания способов получения знания- 1
4. Значения выражений
5. Борьба с русским языком
6. ТЕМАТИЧНА МОДЕЛЬ ТА МЕТОД ПРОГНОЗУ ГАЗОСПОЖИВАННЯ З УРАХУВАННЯМ ЦИКЛІЧНОСТІ 01
7. тема управления охраной труда
8. реферат дисертації на здобуття наукового ступеня кандидата економічних наук Житом
9. Анализ ассортимента и экспертиза качества растительных масел на материалах магазина Мария-Ра г Новосибирска
10. 12 901 10
11. 1все вещи состоят из частиц 2 частицы движутся беспорядочно 3 Частицы взаимодействуют друг с другом
12. Салон красоты рядом прейскурант с ценами реклама изречение Красота страшная сила
13. Некробактериоз коров- лечение и профилактика
14. Варианты планировочных решений до 4х План расстановки мебели План пола с указанием типа напольного покры
15. Предприятие и предпринимательство в экономике переходного периода
16. Реферат по информатике на тему- Архитектура персонального компьютера
17. техническое разграничение доступа к данным и ресурсам вычислительных систем
18. Педагогическая психология
19. Всі дні Святковий Період понеділокнеділя 28
20. Тема- Совершенствование технологии обслуживания туристических групп в службе приема и размещения на приме