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

жүктеу 1,28 Mb.

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

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

Егер кіру және шығу алфавиті:

үлгісінде берілсе, және кіру мен шығу тілдері

тізбекшелер ұзындығын қамтиды, олардың арасындағы сәйкестік аудару түрінде сипатталады.

Элементтер саны көп емес соңғы аударуларды аударылымдар түрінде беруге болады.Бірақта, үлкен соңғы және аяғы жоқ аударулар тапсыру үшін формальды тілдерге сияқты тапсырмалар керек. Бір жағдайды қарастырайық, жиынның кіру тізбекшелері (аударудың

кіру тілін)

грамматикасы арқылы және шығу тізбекшелері арқылы беруге болады (

аударымның шығу тілі).

Осындай тапсырманың аударымы болып, оның

"айна сипатын

шығу тізбекшелері үшін анықтайды. Егер де шығу және кіру алфавиті екі символдан тұрса -

, онда осындай аудару ережесінің мынадай түрі бар:
Кіру тізбекшелері                     шығу тізбекшелері           ╝0,                                 ╝0
         ╝1,                                 ╝1
        ╝,                                       ╝

Сәйкес ережені қолданғанда, мынаны аламыз:

Осындай құрылымды құрғанда кіру және шығу тізбекшелерінің құрылым ережесі арасындағы сәйкестікке ерекше көңіл бөлу керек

Бұл тарауда бір есептін бірнеше нұсқаулары қарастырылады. қалалары болсын, ден сандар реттелген. Әр қалалар үшін нөмірлерімен, кестесінде қаласынан қаласына жетудің авиабилет бағасы толық сан сақталған. Әр қалалар арасындағы рейстер бар деп саналады. барлық -дан айрылады. ден маршруттар үшін билеттер сомасы минималды болып саналады. (оның ішінде ауыстырып отырғызу), ден баратын (ол аспайды, және де кем болмау керек).
Төменде берілген тапсырмаларда алгоритмнің жұмыс уақытына және басқа да жиым шектеуіне кейбір қалалар үшін ең төмен жол төлем бағасын табу керек.

жүктеу 1,28 Mb.

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

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