Forth http://fforum.winglion.ru/ |
|
Найти экономную заготовку для ключа. http://fforum.winglion.ru/viewtopic.php?f=19&t=2378 |
Страница 1 из 3 |
Автор: | вопрос [ Чт янв 07, 2010 10:03 ] |
Заголовок сообщения: | Найти экономную заготовку для ключа. |
см. также Задача "модифицируемый ключ" итак, есть "ключ", представленный массивом из N байт и есть несколько ( V ) варантов замка, каждый также N байт, лежащих в массиве , массив состоит из V блоков по N байт массив, представляющий варианты замка дан до решения, массив "ключ" не заполнен, его необходимо заполнить в процессе решения - найти "заготовку" для ключа, которая позволит как можно меньше "доводки" в худшем из вариантов. Т.е. найти такой ключ, что какой бы мы вариант замка ни избрали, количество модификаций ключа для худшего варианта будет наименьшим, чем для любой другой заготовки в худшем для нее случае. Модификации ключа - 2 типов - наращивание - одновременно всех байтов подпиливание (байта) это можно вообразить так - "зубцы" ключа подпиливаются по отдельности, а наращивание происходит привариванием планки единичной поверх всего ключа ПРИМЕР Пусть есть ключ из 2 байт и массив из двух вариантов замка по 2 байта и диапазон значений байтов от 1 до 8 для такого массива замков 71 17 тут решение почти очевидно: ключ должен быть 77, т.к. число меньше 7 в любом з двух байтов делает необходимым доращивание ключа, а число большее 7 - 8 делает избыточным модификацию ключа в худшем случае. 8 VALUE key_len CREATE key_arr key_len ALLOT 8 VALUE lock_variants CREATE lock_arr ..... [ далее заполнения массива ] ЗАДАЧА закодировать слово : prekey ( key_arr key_len lock_arr lock_variants --> greater_modification ) ; в результате работы слова должен оказаться заполненным массив key_arr greater_modification - число действий в худшем случае для этого массива (при худшем замке для данной заготовки) Примечание - если бы было невозможно доращивание ключа, решение было бы очевидным - следовало бы просто в каждую ячейку ключа поместить максимальное встреченное в этой позиции значение для замка. |
Автор: | Ethereal [ Вс авг 14, 2011 02:41 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
: PREKEY ( lock-arr lock-variants key-arr key_len -- ) |
Автор: | Ethereal [ Вс авг 14, 2011 02:46 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
вопрос писал(а): Примечание - если бы было невозможно доращивание ключа, решение было бы очевидным - следовало бы просто в каждую ячейку ключа поместить максимальное встреченное в этой позиции значение для замка. Решение остается тем-же самым очевидным и при возможности доращивания. Не согласен ? Приведи хотя бы один пример, когда наилучший ключ требует хотя бы одного доращивания. |
Автор: | Ethereal [ Вс авг 14, 2011 04:18 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
вопрос писал(а): будет наименьшим, чем По русски так не говорят.А ведь это кусок формулировки условия задачи. Что, если я его не так понял, коли ты так его сформулировал ? |
Автор: | Ethereal [ Вс авг 14, 2011 19:33 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
Вот, в строгом соответствии с твоим заданием : : PREKEY ( key-arr key_len lock-arr lock-variants -- greater-modification ) |
Автор: | вопрос [ Вс авг 14, 2011 23:07 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
Замечательно добуду своё проложное решение и сравню результаты |
Автор: | Ethereal [ Вт авг 23, 2011 03:53 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
Сказали завтра - значит завтра ... |
Автор: | chess [ Вт авг 23, 2011 10:05 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
Ethereal писал(а): Не согласен ? Приведи хотя бы один пример, когда наилучший ключ требует хотя бы одного доращивания. Я тоже считаю что в задаче не нужен поиск решения, поэтому решение тривиально: Код: : PREKEY ( ka kl la lvar -- bestkey ) lvar! la! kl! ka!
kl 0 DO 0 lvar 0 DO la I kl * J + + C@ MAX LOOP I ka + C! LOOP ka kl ; |
Автор: | вопрос [ Вт авг 23, 2011 13:13 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
Ethereal писал(а): Сказали завтра - значит завтра ... Решение на другом компе - не под рукой
|
Автор: | вопрос [ Вт авг 23, 2011 14:09 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
Найдём ситуацию, когда необходимо доращивание заготовки чисто логически. Примечание - не так трудно представить себе ситуацию с ключом, у которого есть одна рабочая сторона, которую нужно доводить, и вторая нерабочая, к которой можно что-то приварить или припаять Начнём с простого варианта - у нас один ключ и один вариант замка. Тут самая экономная заготовка будет совпадать с замком, т.к. других замков нет и доводить ничего не придётся. Представим себе, что у нас есть 2 замка, предположим также, что для начала и простоты, мы сделали заготовку для ключа, совпадающую с одним из замков. Тут у нас уже появляются 2 ситуации - форма второго замка может или быть достижимой из такой заготовки за 1 шаг (иначе замки не отличались бы) или за большее количество шагов. Недостижимой она быть не может, т.к. доращивание позволяет произвольную модификацию ключа. Внимательно посмотрев, мы видим, что нужно выделить даже 4 ситуации - 1. второй замок достижим для заготовки за 1 "спиливание" 2. второй замок достижим для заготовки за 1 "доращивание" 3. второй замок достижим для заготовки за более чем одно "спиливание" без доращиваний 4. второй замок недостижим для заготовки без доращиваний, т.е. нужно комбинировать Для доказательства нетривиальности решения задачи достаточно и первых двух случаев, точнее только второго - вообразим себе, что замок номер 1 имеет сложную форму из многих зубцов, но эта форма такова, что каждый из зубцов второго замка на 1 единицу длины больше чем аналогичный элемент первого. В этом случае, если бы мы выбрали заготовкой форму первого замка (как указано выше), то одним доращиванием достигали бы форму вторго замка, а вот в случае, если бы выбрали заготовкой форму второго замка, должны были бы подпилить на 1 единицу каждый зубец, которые, как мы помним, учитываются по отдельности. Таким образом, если в ключе более одного зубца, спиливание неизбежно займёт более одного действия, тогда как "доращивание" - 1 ВОт достаточно ключа из 2 зубцов левая колонка - первый замок, правая - второй (2-4) первая строка соответствует ситуации, когда мы выбрали в качестве заготовки ключа форму первого замка (отмечено в случае 1 чистым жёлтым) вторая строка соответствует ситуации, когда в качестве заготовки выбрана форма второго замка (отмечено в случае 4 чистым желтым) т.е. там, где чистый жёлтый цвет - случаи 1 и 4 - это формы замков (первого и второго) соответственно если заготовка совпадает с тем, что мы видим в случае 1, то для получения ключа к второму замку достаточно одного доращивания - малиновым - случай 2 если заготовка совпадает с тем, что мы видим в случае 4 - т.е. с формой второго замка. то для перехода к замку первому, понадобится 2 подпиливания (салатовым) |
Автор: | chess [ Вт авг 23, 2011 14:46 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
вопрос писал(а): Для доказательства нетривиальности решения задачи достаточно.. В этом доказательстве присутствует геометрия. В самой садаче о геометрии нет ни слова. Задача должна быть сформулирована без "ключей и замков", то есть в абстрактном виде. Тогда двусмысленность отпадет. |
Автор: | вопрос [ Вт авг 23, 2011 15:00 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
геометрии нет, обычная комбинаторика операции с наборами чисел - уменьшение - по одному, прибавление - только все вместе. Ну что ж, можно и без ключей и замков, но это хуже. пусть дан набор N чисел, с которым можно производить операции 1. увеличение всех элементов набора на 1 одновременно 2. уменьшение каждого из элементов набора на 1 и т.д. Для некоторого множества наборов (МН) найти такой набор О (optimum), чтобы наихудший случай по количеству операций по получению из О путём доступных операций любого из наборов (МН) был наименшим (по количеству операций) Однако ключи нагляднее, т.к. это позволяет не формулировать условия "максимальная длина зубца", "набор неотрицательных чисел" |
Автор: | chess [ Вт авг 23, 2011 16:17 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
вопрос писал(а): Однако ключи нагляднее, т.к. это позволяет не формулировать условия "максимальная длина зубца", "набор неотрицательных чисел" Зато меньше двусмысленности. Вот в новом виде сразу виден вопрос к диапазону величины элемента в наборе. Если это байт, то сколько можно допустить групповых операций по наращиванию? До переполнения. А если уже предел, то нельзя. |
Автор: | chess [ Ср авг 24, 2011 16:49 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
Алгоритм перебора, вообщем полного. 1. определяем нач. ключ(по минимумам длины зубцов во всех позициях замков и конечный ключ соответственно по максимумам 2. определяем суммарное кол-во операций для текущего ключа на всех замках 3. переходим к следующему ключу 4. запоминаем по минимуму операций текущий лучший ключ 5. ключи не кончились к п.3, кончились на выход с лучшим ключом как часть этого тривиального решения - общее кол-во операций для конкретной пары l(замок) k(ключ) Код: : nOpkl ( l k d -- n )
d! k! l! 0 n! 0 cg! 0 co! 0 cop! d 4 * 0 DO I l + @ I k + @ - is n n 0 > IF n cg MAX is cg THEN 4 +LOOP \ кол-во групповых операций для пары l k d 4 * 0 DO cg I l + +! 4 +LOOP d 4 * 0 DO I k + @ I l + @ - 0 > IF co 1+ is co THEN 4 +LOOP \ кол-во одиночных операций для пары l k cg co + is cop ; |
Автор: | вопрос [ Ср авг 24, 2011 19:08 ] |
Заголовок сообщения: | Re: Найти экономную заготовку для ключа. |
chess писал(а): Алгоритм перебора, вообщем полного. Надо же, я тупо не понимаю, как это запускать
|
Страница 1 из 3 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |