Forth http://fforum.winglion.ru/ |
|
Задача "модифицируемый ключ" http://fforum.winglion.ru/viewtopic.php?f=19&t=2372 |
Страница 1 из 1 |
Автор: | вопрос [ Сб янв 02, 2010 17:57 ] |
Заголовок сообщения: | Задача "модифицируемый ключ" |
Задача "модифицируемый ключ" Многие вынуждены были чинить простой замок, от которого потерян ключ... Это не такая сложная задача, выступы на ключе прижимают сдвигающиеся детали в замке на определённое расстояние, делая возможным поворот. <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 ] |
Заголовок сообщения: | |
Примечание - слово key уже существует , но в верхнем регистре, в случае если в используемом форте регистронезависимое чтение слов, нужно заменить key и key? на другие слова ... |
Автор: | chess [ Ср янв 06, 2010 11:40 ] |
Заголовок сообщения: | |
Отдыхая от отдыха: Код: 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. для исключения лишних манипуляций на стеке(или введения лок. переменных) все входные параметры "вбил" в код определения. |
Автор: | вопрос [ Чт янв 07, 2010 10:07 ] |
Заголовок сообщения: | |
да, это простенькая задачка - два вложенных цикла со сравнениями, единственное, что тут может быть сложно - оптимизация поиска. Цитата: Отдыхая от отдыха
Существуют более сложные варианты той же задачи (на самом деле приведенный вариант - пожалуй самый прстой). Вот такое условие, например: всё то же, но ключ может наращиваться на целое число единиц, однако только весь сразу (приваривается планка сверху) - каждая "нарощенная" единица считается за 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 Существует ещё несколько более сложных. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |