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

жүктеу 1,28 Mb.

бет	33/38
Дата	23.01.2020
өлшемі	1,28 Mb.
	#27192

1 ... 30 31 32 33 34 35 36 37 38

9-10 зертханалық жұмыс. Шекті айқындауыштардың эквиваленттілігі және бірмәнділігі. Контексті-тәуелсіз грамматикаларды келтіру. Мақсаты: Студентерді бағдарламаны кезеңмен құруға үйрету
6.1 Қысқаша теориялық мәліметтер

Бақылау сұрақтары
1 Рекурсивті емес бағдарламаны қалай құру керек?

2 Не өзгереді, егер де екілік бұтақтын төбесін баспаса, ал тек қана оның саның санаса?

9-10 зертханалық жұмыс. Шекті айқындауыштардың эквиваленттілігі және бірмәнділігі. Контексті-тәуелсіз грамматикаларды келтіру.
Мақсаты: Студентерді бағдарламаны кезеңмен құруға үйрету
6.1 Қысқаша теориялық мәліметтер

Бойер-Мура алгоритмы.

Бұл алгоритм жасауға мүмкін емес нәрселерді істейді: ұқсас жағдайда ол сөздердің бір бөлік әріптерін ғана оқиды. Бұл қалай болуы мүмкін? Өте жеңіл. Мысалы біз "

" үлгісін іздестірейік.

Сөздің төртінші әріпіне қарайық: егерде ол "

әріпі болса", бірінші үш әріпті оқу қажеттілігі жоқ. (Негізінде "

" әрпі үлгісінде жоқ, сондықтан ол бесінші әріптен кейін ғана басталады).

Біз осы алгоритмнің ең оңай вариантын көрсетейік, бірақта ол барлық жағдайда жұмыстың шапшандығына кепілдік бере алмайды

болсын - үлгі, оны іздеу керек.

символдың әрқайсысы үшін, оның

сөзінде дұрыс көтерілуін табайық яғни

тең болған жағдайда. Бұл мәліметтер

массивінде сақталады, егерде

символы кездеспесе, онда бізге

қоюға ыңғайлы болады (неге екенің төменде көреміз).

жүктеу 1,28 Mb.

Достарыңызбен бөлісу:

1 ... 30 31 32 33 34 35 36 37 38