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

жүктеу 1,28 Mb.

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

1 ... 13 14 15 16 17 18 19 20 ... 38

10 Тапсырма

N=7, root=3, l және r жиымдары мынадай:

i | 1 2 3 4 5 6 7

l[i] | 0 0 1 0 6 0 7

r[i] | 0 0 5 3 2 0 7

Сәйкес бұтақты жазыңыз.

11 Тапсырма

Бұтақтағы төбелер санының бағдарламалар есебін жазыңыз.

Шешім.

функциясын қарастырайық, x нөмір төбесіндегі түбірмен бұтақ асты төбелер санына тең.

(сәйкес бұтақтын бос), және де

мазмұнына көңіл бөлмейміз төбелер нөмірлеріне жатпайтын s сандары жатады. s үшін рекурсивтік бағдарлама мынадай:
function n (x:integer):integer;

begin

| if x = nil then begin
| | n:= 0;
| end else begin
| | n:= n(l[x]) + n(r[x]) + 1;
| end;
end;
Бұтақ асты төбелер саны x төбесінен оның ұлдары мен өзін қосқандағы төбелер санының сомасына тең. Рекурсия тереңдігі соңғы, себебі әр қадам сайын тиісті бұтақ асты биіктік төмендейді.
Бақылау сұрақтар

Сөздік және алфавит деп нені атаймыз?
формальды грамматиканың анықтамасы нені білдіреді?
Терминалды символ әріптері қандай?

5-6 зертханалық жұмыс. Жіктеу ағашы. Грамматикалардың эквиваленттілігі және бір мәнділігі.
Мақсаты: студенттерді сұрыптау алгоритмын шешу үшін әр -түрлі тәсілді таба білуге үйрету
4.1 Қысқаша теориялық мәліметтер

Жалпы алғанда аудару немесе таратуды алфавит сөзіндегі

және

сөздері арасындағы сәйкестік деп білеміз. Егер

тізбекшелері,

тізбекшелері, олар шығу және кіру тізбекшелері деп аталады. Егер

кіру алфавиті мен шығу алфавиті, онда

тілінен аударғанда,

жиынының тізбекшелерінен тұратын,

_, тілінде тізбекшелерден тұрады

жиыны,

жиынының қос тізбекшелері деп аталады

, олар

жүктеу 1,28 Mb.

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

1 ... 13 14 15 16 17 18 19 20 ... 38