Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Сентябрь 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по дискретной математике


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Академик
Рейтинг: 8461
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Профессор
Рейтинг: 2716
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2139
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная

Номер выпуска:252
Дата выхода:13.09.2011, 18:00
Администратор рассылки:Асмик Гаряка (Академик)
Подписчиков / экспертов:56 / 65
Вопросов / ответов:1 / 1

Консультация # 183993: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Условие: Задача: Дано число в единичном код...

Консультация # 183993:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:

Условие:


Задача:


Дано число в единичном коде унарного счисления, ограниченное точкой справа. Если оно кратно 3, то поставить после точки !, иначе - ?. Исходное число сохранить.

Дата отправки: 08.09.2011, 17:32
Вопрос задал: Дмитрий (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Лысков Игорь Витальевич (Старший модератор):

Здравствуйте, Посетитель - 380186!
Идея решения следующая: строим для единиц три состояния, соответствующие остаткам от деления на 3.
Пока не дойдем до точки, переходим по циклу по этим состояниям.
Другими словами, если мы будем находиться перед точкой в состоянии qs, то остаток от деления = 0
в состоянии q1 остаток от деления = 1, в состоянии q2 остаток от деления = 2
На точке переходим в состояния q3 или q4, формируем нужный символ.
Ну и возвращаемся на начало (до пустой ячейки) в состоянии q5

Для решения задачи строим следующую таблицу состояний:

1
.
_
!
?
qsq1 1 Rq 3 . R
q1q2 1 Rq4 . R
q2qs 1 Rq4 . R
q3 q5 ! L
q4 q5 ? L
q5q5 1 Lq5 . Lqf _ R


1) Имеем следующую систему продукций:
1.1) q{s 1 2}1 → q{1 2 s}1R - переход от состояния, соответствующему одному остатку от деления на 3 равного 0 к другому
1.2) q{s {1 2}}. → q{3 4}.R - закончилось число либо кратное 3 ( qs) с переходом в q3, либо НЕкратное 3 (q1, q 2) с переходом в q4
1.3) q{3 4}_ → q5{! ?}L - ставим либо ! (q3), либо ? (q4). Начинаем движение в начало ленты
1.4) q5{1 .} → q5{1 .}L - ищем начало ленты
1.5) q5 _ → qf _R - встали в начало, останов

2) Алфавит A = {1, ., !, ?, _}

3) Состояния устройства управления Q = {qs, q1, q2, q3, q4, q5, qf}

4) Проверочная последовательность конфигураций для контрольного примера исходных данных: 14. = 1111.
(qs)1111. ⇒(1) 1(q1)111. ⇒(1) 11(q2)11. ⇒(1) 111(qs)1. ⇒(1) 1111(q1). ⇒(2) 1111.(q4)_ ⇒(3) 1111(q5).? ⇒(4)
⇒(4) 111(q5)1.? ⇒(4) 11(q5)11.? ⇒(4) 1(q5)111.? ⇒(4) (q5)1111.? ⇒(4) (q5)_1111.? ⇒(5) (qf)1111.?
(qi) обозначают текущее состояние и позицию, ⇒(i) обозначают переходы из одной конфигурации в другую, число - номер продукции.

5) Вычислительная сложность всегда равна 2*n+4, т.к. задача решается за 2*n+4 шага (в одну сторону за n+2 шагов и обратно за столько же)

Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 08.09.2011, 23:17
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2011, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.33 от 10.09.2011
В избранное