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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Найти экономную заготовку для ключа.
СообщениеДобавлено: Чт янв 07, 2010 10:03 
Не в сети

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

итак, есть "ключ", представленный массивом из 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 - число действий в худшем случае для этого массива (при худшем замке для данной заготовки)

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вс авг 14, 2011 02:41 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
: PREKEY ( lock-arr lock-variants key-arr key_len -- )
2DUP ERASE
ROT 0 ?DO
DUP >R 0 ?DO
OVER C@ OVER I + C@ MAX OVER I + C!
>R CHAR+ R>
LOOP R>
LOOP DROP 2DROP
;


Последний раз редактировалось Ethereal Вс авг 14, 2011 02:52, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вс авг 14, 2011 02:46 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
вопрос писал(а):
Примечание - если бы было невозможно доращивание ключа, решение было бы очевидным - следовало бы просто в каждую ячейку ключа поместить максимальное встреченное в этой позиции значение для замка.

Решение остается тем-же самым очевидным и при возможности доращивания.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вс авг 14, 2011 04:18 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
вопрос писал(а):
будет наименьшим, чем
По русски так не говорят.
А ведь это кусок формулировки условия задачи. Что, если я его не так понял, коли ты так его сформулировал ?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вс авг 14, 2011 19:33 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
Вот, в строгом соответствии с твоим заданием :

: PREKEY ( key-arr key_len lock-arr lock-variants -- greater-modification )
2OVER ERASE
>R SWAP
R@ 0 DO
DUP >R 0 DO
OVER I + OVER C@ OVER C@ MAX SWAP C! CHAR+
LOOP R>
LOOP
1- 0 SWAP
R> 0 DO
>R 0 0 R@ DO
2SWAP CHAR- OVER I + C@ OVER C@ - >R 2SWAP R> +
-1 +LOOP MAX R>
LOOP
DROP NIP NIP
;


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вс авг 14, 2011 23:07 
Не в сети

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт авг 23, 2011 03:53 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
Сказали завтра - значит завтра ... :shuffle;


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт авг 23, 2011 10:05 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
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 ;

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт авг 23, 2011 13:13 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Ethereal писал(а):
Сказали завтра - значит завтра ... :shuffle;
Решение на другом компе - не под рукой


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт авг 23, 2011 14:09 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Найдём ситуацию, когда необходимо доращивание заготовки чисто логически.
Примечание - не так трудно представить себе ситуацию с ключом, у которого есть одна рабочая сторона, которую нужно доводить, и вторая нерабочая, к которой можно что-то приварить или припаять
Начнём с простого варианта - у нас один ключ и один вариант замка.
Тут самая экономная заготовка будет совпадать с замком, т.к. других замков нет и доводить ничего не придётся.
Представим себе, что у нас есть 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 подпиливания (салатовым)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт авг 23, 2011 14:46 
Не в сети
Аватара пользователя

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

В этом доказательстве присутствует геометрия. В самой садаче о геометрии нет ни слова.
Задача должна быть сформулирована без "ключей и замков", то есть в абстрактном виде.
Тогда двусмысленность отпадет.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт авг 23, 2011 15:00 
Не в сети

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

Ну что ж, можно и без ключей и замков, но это хуже.

пусть дан набор N чисел, с которым можно производить операции
1. увеличение всех элементов набора на 1 одновременно
2. уменьшение каждого из элементов набора на 1
и т.д.

Для некоторого множества наборов (МН) найти такой набор О (optimum), чтобы наихудший случай по количеству операций по получению из О путём доступных операций любого из наборов (МН) был наименшим (по количеству операций)

Однако ключи нагляднее, т.к. это позволяет не формулировать условия "максимальная длина зубца", "набор неотрицательных чисел"


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт авг 23, 2011 16:17 
Не в сети
Аватара пользователя

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

Зато меньше двусмысленности. Вот в новом виде сразу виден вопрос к диапазону величины элемента в наборе. Если это байт, то сколько можно допустить групповых операций по наращиванию? До переполнения. А если уже предел, то нельзя.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Ср авг 24, 2011 16:49 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Алгоритм перебора, вообщем полного.
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 ;

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


Последний раз редактировалось chess Ср авг 24, 2011 20:43, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Ср авг 24, 2011 19:08 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
chess писал(а):
Алгоритм перебора, вообщем полного.
Надо же, я тупо не понимаю, как это запускать :shock:


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

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


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

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


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

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