«Информатиканың теориялық негіздері»
K – Тьюриг машинасы лента тартатын механизімінің командасы (солға, оңға, тоқтау) q
жүктеу/скачать 363.46 Kb.
|
| K – Тьюриг машинасы лента тартатын механизімінің командасы (солға, оңға, тоқтау)
q – Тьюринг машинасының жаңа қалып-күйі. Дәріс №14-15. Тақырыбы: Алгоритмдерге талдау жасау негіздері Іздеу алгоритмі мысалы, массив элементін қажет қасиеті бойынша іздеуде қолданылады. Әдетте енгізілген бірінші және соңғы элементтерді табу үшін қойылған есептерді шығаруда ерекшелігін көруге болады. Төменде көрсетілген барлық алгоритмдерде N элементтен және бүтін сандардан тұратын А массивінен Х-қа тең санды іздеу туралы мысалдар келтіреміз. Тізбектік іздеу Іздеу алгоритімі, мысалы жиым ішінен белгілі бір қасиеттері бар элементті тауып алу үшін қолданылады. Төменде келтірілген барлық мысалдар нақты N элементтен тұратын A жиымының X-қа тең элеметін табу үшін орындалады. Тізбектік іздеу алгоритімі екі шарты бар цикл көмегімен іске асырылады (while немесе repeat - until). Бірінші шарт индекстің жиымға кіретіндігін (i<=N) қадағалайды. Екінші шарт – бұл іздеу шарты. Біздің жағдайымызда while циклында іздеуді жалғастыру шарты жазылады: (A[i]<>X), ал repeat - until циклында іздеуді тоқтату шарты: (A[i]=X). Цикл денесінде тек бір ғана оператор жазылады: индекстің жиым ішінде өзгеруі. Циклдан шыққаннан кейін, қандай шарт бойынша шыққанымызды тексеру керек. If операторында, әдетте циклдың бірінші шарты тексеріледі. Егер цикл while шарты бойынша аяқталса, онда іздеудің ойдағыдай аяқталғандығы жайлы айтуға болады. Ал егер repeat - until шарты бойынша аяқталса, онда іздеудің орындалмағаны. Мысал: Тізбектік іздеу program Poisk1; var A:array[1..100] of integer; N, X, i:integer; begin read(N); {N<=100} for i:=1 to N do read(A[i]); read(X); i:=1; {i:=0;} while (i<=N) and (A[i]<>X) do i:=i+1; {repeat i:=i+1; until (i>N) or (A[i]=X);} if i<=N then write(X,' санының A жиымна бірінші енуі ',i,' орында') else write('табылмады'); end. Соңғы енуіді іздеу кезінде енгізу операторынан кейін келесіоператорлар жазылу тиіс: i:=N; {i:=N+1;} while (i>=1) and (A[i]<>X) do i:=i-1; {repeat i:=i-1; until (i<1) or (A[i]=X);} if i>=1 then write(X,' санының A жиымына соңғы енуі ',i,' орында') else write('табылмады'); Сұрыптау. Қарапайым сұрыптау есебі - жиым элементтерін өсу не кему реті бойынша реттеу болып табылады. Сұрыптаудың тағы бір түрі – жиым элементтерін берілген критерилерге байланысты реттеу. Әдетте мұндай критерийлер ретінде мәндері жиым элементтері болып келген белгілі бір функцияның алынады. Бұндай функцияны реттеуші функция деп атайды. Сұрыптаудың түрлі тәсілдері бар: Таңдап сұрыптау, Алмастырып сұрыптау ("көпіршік" тәсілі), Қосып сұрыптау жүктеу/скачать 363.46 Kb. Достарыңызбен бөлісу:
|