Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 21:40

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Задача "модифицируемый ключ"
СообщениеДобавлено: Сб янв 02, 2010 17:57 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Задача "модифицируемый ключ"

Многие вынуждены были чинить простой замок, от которого потерян ключ...
Это не такая сложная задача, выступы на ключе прижимают сдвигающиеся детали в замке
на определённое расстояние, делая возможным поворот.
<pre>

Это может выглядеть так (буква К - ключ, L - замок, '=' - граница, где поворот)
ККККККККККККККККККК
К ККК ККК ККК ККК
К К К К К
L L L L L
L L L L L
=======L===========
L L = L L
L L L L L
В данном случае замок открыть не удастся - средний выступ на ключе "утопил" движущуюся деталь
дальше, чем следует, и она перекрыла границу, однако, если мы удалим одно деление с выступа ключа,
"дав место" движущейся детали,

то замок откроется
ККККККККККККККККККК
К ККК ККК ККК ККК
К К L К К
L L L L L
L L L L L
===================
L L L L L
</pre>
понятно, что в упрощённом случае и замок и ключ можно представить в виде двух
массивов, в которых каждая ячейка показывает высоту выступа
(в целых единицах).

пусть массив, изображающий ключ, содержит РЕАЛЬНЫЕ высоты выступов,
а массив, изображающий замок - ТРЕБУЕМЫЕ (так проще)

понятно, что замок откроется, если соответствующие числа совпадут
23432
23432
такая комбинация ключа и замка откроет замок

а вот для такой
23532
23432
возникнет ситуация, когда средняя деталь "переутоплена" за границу поворота
и замок открыть не удастся.

Но и такая комбинация
23332
23432
создаст проблему - недоутопленная деталь также будет препятствовать вращению


ЗАДАЧА
Пусть у нас есть замок, представленный массивом байтов, содержащих числа от 1 до 8,
и ключ, представленный также массивом байтов; длина ключа больше длины замка - мы можем
произвольно перемещать ключ в замке в поисках подходящей комбинации,
также мы можем подпилить участок(-тки) ключа (на целое число единиц, разумеется), если подходящая
комбинация длин участков не найдена. Доращивать участки невозможно.

Построить алгоритм поиска открывающего замок участка ключа так, чтобы количество удаляемых
единиц с ключа было наименьшим (если найден точно подходящий к замку участок ключа, то количество
удаляемых единиц равно нулю).

Пример
для замка
1 1 1 2
и ключа
2 2 2 1 1 1 3
решение такое: открывающим будет участок ключа начиная с 3 ячейки (считая от 0)
при том, что ячейку 6 неоходимо спилить на 1 единицу.

предполагаемо даны

8 VALUE lock_len
CREATE lock x С, x С, x С, x С, x С, x С, x С, x С,

96 VALUE key_len
CREATE key x С, x С, x С, x С, x С, x С, x С, x С, [ 96 единицы ] ...

где х - произвольные числа от 1 до 8, длина массивов может быть другой, это не так существенно

необходимо закодировать слово
: key? ( lock lock_len key key_len --> position deleted true | false )

;

где position - позиция ключа, подходящая к замку,
deleted - количество подпиленных единиц
true | false - успех-неудача (если участок не нашёлся)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс янв 03, 2010 01:32 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Примечание - слово key уже существует , но в верхнем регистре, в случае если в используемом форте регистронезависимое чтение слов, нужно заменить key и key? на другие слова ...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 06, 2010 11:40 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Отдыхая от отдыха:

Код:
8 VALUE lock_len
CREATE lock  lock_len ALLOT

96 VALUE key_len
CREATE key  key_len ALLOT

: key? ( --> position deleted true | false )
0 PAD C!
key_len lock_len - 0
DO 0 lock_len 0
   DO key J + I + C@ lock I + C@ 2DUP <
      IF 2DROP DROP 64 LEAVE ELSE - + THEN
   LOOP key I + C!
LOOP
64 key_len lock_len - 0
DO key I + C@ SWAP 2DUP <
   IF I PAD C! MIN ELSE NIP THEN
LOOP
64 = IF FALSE ELSE PAD C@ DUP key + C@ TRUE THEN ;



\  ТЕСТЫ

STARTLOG
\ есть ключ
lock lock_len 6 FILL
key key_len 7 FILL
key?

\ нет ключа
lock lock_len 7 FILL
key key_len 6 FILL
key?

лог
Код:
Ok ( 0 8 4294967295(-1) 0 )


ps. для исключения лишних манипуляций на стеке(или введения лок. переменных)
все входные параметры "вбил" в код определения.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 07, 2010 10:07 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
да, это простенькая задачка - два вложенных цикла со сравнениями, единственное, что тут может быть сложно - оптимизация поиска.
Цитата:
Отдыхая от отдыха

Существуют более сложные варианты той же задачи (на самом деле приведенный вариант - пожалуй самый прстой).

Вот такое условие, например: всё то же, но ключ может наращиваться на целое число единиц, однако только весь сразу (приваривается планка сверху) - каждая "нарощенная" единица считается за 1 усилие.

для замка
1 2 3 1

ключ
1 1 2 1
потребует 3 усилия - нарастить до 2 2 3 2, потом спилить до 1 2 3 1

это лучше, чем ключ 2 3 4 2, который требует 4 действия
опять же интересно - возможна ли оптимизация поиска.
Ясно также, что в этом случае ключ всегда находим, только за разное число шагов.

Более "правильный" вариант этой задачи вот: http://fforum.winglion.ru/viewtopic.php ... torder=asc
Существует ещё несколько более сложных.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB