Безопасный интернет
жүктеу/скачать 82,62 Kb.
|
Lek 12 Syriptau
- Бұл бет үшін навигация:
- 4. Таңдау әдісі бойынша сұрыптау 5. Ауыстыру әдісі бойынша сұрыптау 6. Шейкер сұрыптау 7. Енгізу әдісі бойынша сұрыптау
- Ізделініп отырған мәндеріміз
- Бинарлы іздеу алгоритмінің негізі
- Мысал1.
|
Іздеу және сұрыптау алгоритмдері Жоспар 1. Сызықты іздеу алгоритмі 2. Бинарлы іздеу алгоритмі 3. Бекіту мысалдары 4. Таңдау әдісі бойынша сұрыптау 5. Ауыстыру әдісі бойынша сұрыптау 6. Шейкер сұрыптау 7. Енгізу әдісі бойынша сұрыптау 1 Сызықтық іздеу алгоритмінің негізі: X [1…n] сандық массиві берілген. (n-элементтер саны) X массивінде w элементі бар ма, соны анықтауымыз керек. X массивінің элементтерін w элементімен тізбектей салыстырамыз. Іздеуді массив элементтері аяқталғанға немесе ізделінді элементіміз табылғанға дейін жүргіземіз. Есеп аргументтері: n -берілген элементтер саны X[1…n] -сандық массиві W – ізделінді элемент Есеп нәтижесі: m – мәні ізделінді элементке тең массив элементінің нөмірі. Мысалы. 12, -4.5, 8,0,-0.02,35.1,5,1 сандары берілсін. Ізделініп отырған мәндеріміз: -0. 02, 32 «-0.02» элементін іздесек, жауабы – берілген сандар арасында мәні осыған тең сан бар, оның реттік нөмірі m=5 32 іздесек, жауабы - мұндай сан жоқ, m=0 Бинарлы іздеу алгоритмінің негізі: X[1…n] - сұрыпталған массиві берілген. (n – элементтер саны). X массивінде w-элементі бар ма, соны анықтауымыз керек. Бинарлы іздеу алгоритмінің негізі мынада: А) массив ортасы болып табылатын элементтің индексін анықтаймыз; Б)осы элементті ізделінді w мәнімен салыстырамыз; В) егер орта элемент мәні w-ге тең болса, ізделінді санымыз табылды, іздеуді аяқтаймыз. Әйтпес, w- орта элементтен кіші болса, массивтің бірінші бөлігін аламыз, егер w-орта элементтен үлкен болса, массивтің екінші бөлігін аламыз да іздеуді а) және б) пункттері бойынша жалғастырамыз. m=0 a=1 b=n for i in range (n+1): k=(a+b)/2 if x[k]=w: m=k else: if (w else: a=k+1 if (m!=0 or a>b) exit Мысал1. Бүтін сандардан тұратын В(m) массивінде ең үлкен элементті табыңыз және соңғы орынға қойыңыз. Мысал2. Кему реті бойынша сұрыпталған А(n) сандық массивінде S элементі бар ма, соны анықтаңыз. Сұрыптау (немесе реттеу) деп, массив элементтерін белгілі бір ретпен орналастыруды айтамыз. Сұрыптаудың негізгі мақсаты реттелген массивте іздестіруді жеңілдету. Реттелген объектілердің мысалына мыналарды жаткызуға болады: а) кітапхана қоймасына кітаптардың орналау реті; б) қоймада тауарлардың орналасуы; в) анықтамадағы телефон номерлер т.с.с Олимпиадалық есептерде сұрыптау негізгі мақсат болмайды, бірак кейбір жағдайда оны қолдану программаның жұмыс жасау уакытын азайтумен қатар, программаның тиімділігіне де айтарлықтай әсер етеді. Таңдау әдісі бойынша сұрыптау Сұрыптаудың бұл әдісі келесі қағидаларға негізделген: Ең үлкен элемент таңдалынып алынады. Ол бірінші А[1] элементімен ауыстырылады, яғни бірінші орында ең үлкен элемент тұрады. Содан кейін массивтің сұрыпталмаған бөлігі қарастырылып, Осы іс-әрекет қалған (N-l), (N-2) элементтері үшін орындалады т.с.с, соңында ең кіші элемент қалады. Ауыстыру әдісі бойынша сұрыптау Сұрыптаудың бүл әдісі екі элементті салыстыруға негізделген: Алғашқы екі элементті салыстырамыз. Егер біріншісі екіншісінен кіші болса, онда элементтердің орнын ауыстырамыз. Екіншімен үшінші, үшінші мен төртінші т.с.с. Элементтерді салыстырып, қажет болса элементтердің орнын ауыстырамыз. Ең кіші элемент соңғы орынға орналасады. 3. Массивтің басынан бастап шолу жасап, қарастырылатын элементтер санын бір бірлікке кемітіп отырамыз. Массив тек бірінші және екінші элемент қатысатын шолудан кейін сұрыпталады. Шейкер сұрыптау Ауыстыру әдісі бойынша сүрыптағанда ең кіші элемент өз орнына бірінші шолудан кейін, ал ең үлкен мәнді элемент, жалпы жағдайла өз орнына алгоритм жұмысының соңында орналасады. Әрбір шолудан кейін қарастыру бағытын өзгертіп көрелік, яғни қарастыруды массивтің басынан бастап, ең кіші элементті аныктасак. енді қарастыруды соңғы элементтің алдынан бастап, ең үлкен элемент таңдау арқылы, сұрыптауды массивтің басына қарай жүргіземіз. Бұл сұрыптау Шейкер әдісі деп аталады. Яғни сұрыптау екі бағытта жүргізіледі. Енгізу әдісі бойынша сұрыптау А массивтің элементтерін екіншісінен бастап қарастырамыз. Әрбір жаңа А[і] элементін реттелген А[і],..., А[і-1] жиынтығындағы қажетті орынға орналастырамыз. Бұл орын А[і] элементін ретгелген тізбектей А[і],..., А[і-1] элементтерімен салыстыру арқылы анықталады. Сұрыптаудың бұл әдісі қарапайым енгізу арқылы сұрыптау деп аталады. Элементті қажетті орынға орналастыру үшін, одан кейінгі элементтерді енгізілетін элемент тұрған орынға дейін ығыстырамыз жүктеу/скачать 82,62 Kb. Достарыңызбен бөлісу:
|