1. Введение
2. Числа и скобки
3. Скобочный ряд
4. Операции на скобках
5. Сервис on-line
СОДЕРЖАНИЕ (показать)

            5. Сервис on-line

В заключительном разделе рассмотрим прилагаемый интерактивный сервис. Разра­ботан­ные прог­раммы сервиса позво­ляют рассчи­тать отдель­ное слово Моцкина или группу слов в произ­воль­ном диапа­зоне линейки скобоч­ного ряда. Прог­рамм­ный комп­лекс позво­ляет рассчи­тывать элементы ряда с индек­сами порядка 1011. Техно­логия поиска наборов харак­теризу­ется следу­ющими двумя момен­тами:

Напом­ним, чита­тель может опера­тивно вывести здесь группу скобоч­ных наборов в произ­воль­ном диа­па­зоне ряда, указав началь­ный индекс и коли­чество эле­ментов. Естес­т­вен­ные ограни­чения связаны с прием­лемым расчетным временем. Прог­рамма позво­ляет вводить числа в удобо­читае­мом формате. Например, можно разде­лять пробе­лами или точками тройки цифр (тысячи, милли­оны и т.д.). В про­цессе работы прог­раммы инфор­мация собира­ется в таблицу и выво­дится в отдель­ной вкладке браузера. Коли­чество столб­цов меня­ется в зависи­мости от длины скобоч­ных наборов. Для лучшей ориен­тации эле­менты первого стол­бца сопро­вожда­ются индек­сами. Если в таблицу попа­дают макси­мальные элементы диапа­зонов скобоч­ного ряда, то для макси­мумов также указы­ваются индек­сы – числа Моцкина. Допол­нительно ячейки таблицы с макси­мальными элемен­тами отме­чаются цветом.

С помощью других программ можно здесь и здесь рассчи­тать произволь­ный элемент скобоч­ного ряда. В первом варианте по скобоч­ной после­дова­тель­ности опреде­ляется индекс элемента, во вто­ром – по задан­ному индексу нахо­дится соот­ветст­вующий набор ско­бок. Прог­раммы исполь­зуют методы уско­рения расчета элементов ряда с боль­шими индек­сами. В длин­ных кодах пользо­ватель может с помо­щью пробе­лов разде­лять блоки скобок или "наре­зать" на порции повто­ряющи­еся нули. Для взаимо­дейст­вия с пользо­вателем прог­рамма исполь­зует времен­ное окно в теку­щей вкладке браузера. Жела­тель­но длину скобок огра­ничи­вать 28 знаками, что соот­ветст­вует значе­нию индекса в райо­не 1011. Если указы­вать вели­чины, превы­шающие эти значе­ния, то время рас­чета может ока­заться непри­емле­мым. Однако, в процессе продол­житель­ных расчетов выда­ются проме­жуточ­ные резуль­таты, которые в даль­нейшем можно исполь­зовать в случае преры­вания или аварий­ного завер­шения расче­тов. Для справки, на бытовом компью­тере со средним быстродействием за 1 сек машин­ного времени выпол­няется прямой перебор до 5×106 элемен­тов скобоч­ного ряда.

Программы интерактивного сервиса для уско­рения расчетов исполь­зуют спра­вочник, который содер­жит около 200 элемен­тов-ориен­тиров на линейке скобоч­ного ряда. В спра­воч­нике содер­жатся мини­мумы и макси­мумы первых 28 диапа­зонов ряда и некоторые пред­вари­тельно прос­читан­ные эле­менты, вклю­чая произ­водные слова Моцкина. На первом этапе расчетов подби­рается мини­маль­ный интер­вал на линейке ряда, внутри кото­рого нахо­дится задан­ный эле­мент. Ниж­няя и верх­няя границы интер­вала пред­став­ляют собой элементы спра­воч­ника, наибо­лее близко распо­ложен­ные к иско­мому эле­менту. Далее опреде­ляется поло­жение элемен­та отно­ситель­но центра интер­вала, чтобы выбрать оптимальное направ­ление поиска – от мень­ших индексов к боль­шим (снизу-вверх) или от боль­ших индексов к меньшим (сверху-вниз). В случае поиска элемента по его индексу, центр интер­вала нахо­дится точно и доста­точно просто (полу­сумма индек­сов границ). Если же для поиска элемента задан скобоч­ный набор, то центр интер­вала опре­деля­ется ориен­тиро­вочно по началь­ным симво­лам кода как в иско­мом наборе, так и в гранич­ных элементах. И в этом случае может быть выб­рано не лучшее направ­ление поиска.

На последнем этапе расчетов выполняется непос­редст­венный поиск задан­ного элемента скобоч­ного ряда. Работа прог­раммы начина­ется с прямого перебора элементов на линейке ряда от нижней или верхней границы интер­вала. Заметим, что верхней гра­ни­цы может и не сущест­вовать, если требу­емый элемент, распо­ложен правее всех ориен­тиров справоч­ника. Такие эле­менты жела­тельно впос­ледс­твии внести в спра­вочник (рекви­зиты для связи с автором см. ниже). Дело в том, что прог­рамм­ное обес­печение инте­рактив­ного сер­виса разра­ботано без прив­лече­ния моду­лей на сто­роне сер­вера. Для уско­рения расче­тов решено отка­заться от файло­вой обра­ботки и баз данных. Поэтому спра­вочник с элемен­тами-ориен­тирами офор­млен в виде набора скрип­тов, которые подклю­чаются к прог­раммам во время рас­четов.

В ходе прямого пере­бора элемен­тов прог­раммы сервиса по мере возмож­ности выпол­няют броски (прыжки) по линей­ке скобоч­ного ряда, что значи­тельно уско­ряет (часто, в разы) пере­борные проце­дуры. Техно­логия прыж­ков свя­зана с обра­боткой скобоч­ных набо­ров, кото­рые имеют в конце кода либо нулевые фраг­менты, либо фраг­менты, харак­терные для макси­мумов диапа­зонов (череда смеж­ных пар­ных скобок с возмож­ным конеч­ным нулем). Нулевые фраг­менты обраба­тыва­ются при пере­боре элемен­тов ряда снизу-вверх, фраг­менты макси­мумов фикси­руются при пере­боре сверху-вниз. Напри­мер, если в проце­ссе пере­бора элемен­тов снизу-вверх встре­тился скобоч­ный набор с конеч­ным нулевым фраг­ментом длиной  k, то возмо­жен прыжок к эле­менту, который распо­ложен на линейке ряда правее теку­щего на  Mk−1  пози­ций (выпол­нение опера­ции скобоч­ное сложе­ние). И та­кой ска­чок выпол­няется, если мы при этом не "пере­прыг­нем" через задан­ный элемент. В про­тив­ном слу­чае даль­ность прыжка регу­лиру­ется под­бором длины нуле­вого фраг­мента. Анало­гичным обра­зом выпол­няются прыжки при пере­боре элемен­тов сверху-вниз, в этом случае подклю­чается опера­ция вычи­тания ско­бок.

 

<<   Операции на скобках  ||