Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Задача. Ключи и замки

Задача. Ключи и замки
Я
   Ненавижу 1С
 
20.07.18 - 13:11
У нас есть N ключей {К1,К2,...,КN} и столько же замков {З1,З2,...,ЗN}. Будем считать, что и те как-то пронумерованы. Каждый ключ подходит ровно к одному замку.
Вы хотите определить какой ключ подходит к какому замку. Для этого разрешается проделывать следующую операцию:
Взять любое количество 1<=r<=N ключей и столько же замков и передать ключнику. Ключник проверяет все ключи и замки, отдает их обратно и говорит число пар ключ-замок, которые удалось подобрать, но не говорит сами пары.

За сколько таких операций можно узнать все пары соответствующих ключей/замков от количества N?

Для N=2 ответ 1.
Для N=3 ответ 3.
 
 
   Fish
 
1 - 20.07.18 - 13:16
(0) А почему для N=3 ответ 3? Вполне можно и двумя обойтись, если первый и второй ключ подойдут с первой попытки.
   Ненавижу 1С
 
2 - 20.07.18 - 13:19
(1) а если не подойдет?
   Ненавижу 1С
 
3 - 20.07.18 - 13:19
+(0) пояснение "можно ГАРАНТИРОВАННО узнать"
   1Сергей
 
4 - 20.07.18 - 13:22
(0)

Для N=2 ответ 1
Для N=3 ответ 2
   1Сергей
 
5 - 20.07.18 - 13:22
хотя, нет. всё-таки 3, да
   Fish
 
6 - 20.07.18 - 13:23
(3) Ну так, если сразу подойдет, то тоже гарантированно узнаешь. Имхо, правильное уточнение должно звучать так: "какое _максимальное_ кол-во операций для определения".
А для усложнения можно добавить "какое _минимальное_ и какое _максимальное_ кол-во операций."
   Малыш Джон
 
7 - 20.07.18 - 13:24
каждый ключ поочередно проверяем с каждым замком(отдаем по одной паре ключ замок). Таким способом первый ключ отыщем гарантированно за N-1 операций(если предпоследний не подошел, последний можно не проверять), второй - за N-2 и т.д.
таким образом имеем арифметическую прогрессию - N-1, N-2, ... 2, 1.
Итого операций: N(N-1)/2
   Малыш Джон
 
8 - 20.07.18 - 13:25
+(7) ааа, и проверку последней пары тоже можно не делать.
Тогда -  N(N-1)/2-1
   Малыш Джон
 
9 - 20.07.18 - 13:26
+(8) хотя нет, все верно - N(N-1)/2
   Fish
 
10 - 20.07.18 - 13:26
(8) Так неинтересно :)
А для минимального кол-ва операций посчитаешь?
 
 Рекламное место пустует
   Малыш Джон
 
11 - 20.07.18 - 13:28
(10) ))))))))
а про минимальное количество условия не было)
я вообще хотел сначала N*N написать, но потом сообразил, что это уж слишком избыточное количество
   Tatitutu
 
12 - 20.07.18 - 13:29
(3)
"которые удалось подобрать"
Ситуация:
ключ1 , ключ3, ключ15
и замок2 , замок8 , замок 28
   Ненавижу 1С
 
13 - 20.07.18 - 13:31
Мое предположение, что при N=4 будет ответ 5
   1Сергей
 
14 - 20.07.18 - 13:32
Что-то не пойму зачем в задачу добавлен выбор R. При R>1 количество операций только увеличивается
   DTX 4th
 
15 - 20.07.18 - 13:33
(7) Тоже по индукции нашёл такое решение, но ведь не факт, что это минимальное число операций.
   Малыш Джон
 
16 - 20.07.18 - 13:39
(13) да, при N=4, попыток будет максимум 5, так что формула из 7 - не минимальное количество
   Ching Woo
 
17 - 20.07.18 - 20:25
(0) Не знаю ответ
   RomanYS
 
18 - 20.07.18 - 20:38
(14) не факт. Проверяя 1 ключ вы получаете 1 бит информации, а проверяя 3 ключа - 2 бита.
   RomanYS
 
19 - 20.07.18 - 20:49
(13) при N=4 меньше чем за 4 точно нельзя. А вот можно ли за 4?
   Ching Woo
 
20 - 20.07.18 - 21:03
(18) откуда там 2 бита?
   RomanYS
 
21 - 20.07.18 - 21:12
(20) 4 результата проверки: 0,1,2,3
Конечно это если N>5.
   Ching Woo
 
22 - 20.07.18 - 21:30
(21) Тогда сколько бит получаем если проверяем два ключа?
   RomanYS
 
23 - 20.07.18 - 21:41
(22)
Если бы три варианта были равновероятны (что в данном случае не так), то log2(3).
Только зря ты этот вопрос задал, сейчас опять срач не по теме будет ;)
   Ching Woo
 
24 - 20.07.18 - 22:15
Короче, максимально много информации получаем если проверяем половину ключей с первого раза.

Нужно теперь понять как получить максимально много информации на второй и последующих проверках.
   RomanYS
 
25 - 20.07.18 - 22:23
(24) Это зависит от того какую задачу мы решаем (N=4 или общую).
В общем случае во второй проверке тоже должна быть половина (только в совершенно другой комбинации)
   Сияющий в темноте
 
26 - 20.07.18 - 22:32
Если обрзначить каждый замок от 1 до н битом в позиции н,и аналогично ключи от 1 до н битом в позиции н
когда мы даем ключнику замки,то есть число из битов А, и ключи,то есть число из битов Б,то ключник вычисляет логическое И этих двух последовательностей битов,и возвращает как результат,количество битов в числе.
далее,требуется построить несколько последовательностей битов,чтобы они различались только одним битом и прогнать их через ключника
   Сияющий в темноте
 
27 - 20.07.18 - 22:35
биты ключей мы знаем,а биты замков спрятаны от нас массивом С[з],массив знает только ключник,для каждого замка он выдает позицию бита
нужно определить этот массив
   Сияющий в темноте
 
28 - 20.07.18 - 22:49
А дальше аналог алгоритма СРС,мы меняем биты блоками,получая последовательности,где изменение битов искажает конрольную сумму и выполняем сравнения
там формула числа операций двоичный логарифм,и так как две последовательности,то нужно умножить на четыре или,наверное,на три,т.к.четвертая определяется

другими словами,делим замки и ключи на две кучи и гоняем 4 раза к ключнику,потом кучи переставляем по алгоритму срс и гоняем снова 4 раза и так по логарифму двух от количества мы прогоним всех по всем
   RomanYS
 
29 - 20.07.18 - 23:20
(26)(27)(28) Звучит красиво, про "алгоритм СРС" правда даже яндекс ничего внятного не говорит.
Идея то на поверхности, проблема с "требуется построить несколько последовательностей битов,чтобы они различались только одним битом и прогнать их через ключника". Т.к. независимых последовательностей не так много, и построить по нужному условию не получится.

Давайте для N=4 решим
   Малыш Джон
 
30 - 21.07.18 - 08:07
(26) Если честно не понял, как ты собрался набор из N ключей(количество перестановок = N!) собрался обозначать двоичным N-значным числом (количество возможных значений = 2^N)...

Может и правда, на примере N=4 продемонстрируешь?)
   Сияющий в темноте
 
31 - 21.07.18 - 09:34
А причем здесь перестановка,перествновка ключей ничего не дает,т.к.проследовательность битов от положения ключей не зависит.
А алгоритм срс простой,первый бит,это сумма всех бито по модулю два,второй бит,сумма блоков по одному биту через такой же блок,следующий бит,это сумма чередующихся блоков по два и т.д.по степени двойки

Для четырех получаются пары сначала к1,к2 и к3,к4 потом пары к1,к3 и к2,к6
так как из испытаний четверток избыточное,то гоняем 6 раз.
к1,к2 з[с[1]],з[c[2]]
к1,к2 и з[с[3]],з[с[4]]
к3,к4 и з[с[1]],з[с[2]]
к1,к3 и з[с[1]],з[с[3]]
к1,к3 и з[с[2]],з[с[4]]
к2,к4 и з[с[1]],з[с[3]]
   Сияющий в темноте
 
32 - 21.07.18 - 09:41
хотя нет,в данном случае гонять первые ключи во вторую группу также не надо,т.к.
к1,к2 и з1,з2 это сколько ключей от первой группы подходит к замкам первой группы.очевидно,что к замкам второй группы подойдут остальные ключи.
к3,к4  з1,з2 сколько ключей из второй группы подходит к замкам первой группы.
   RomanYS
 
33 - 21.07.18 - 12:09
(32) вот про это и говорилось в (29) что не получится
 
 
   Aleksey
 
34 - 21.07.18 - 12:50
(10) А разве минималоьное количество не равно N-1?
   Aleksey
 
35 - 21.07.18 - 12:51
т.е. оно разве не равно "угадал с первой попытки"?
   RomanYS
 
36 - 21.07.18 - 13:08
(34)(35) Тогда уж 0, угадал с первой попытки и не стал проверять.
Естественно в нормальной формулировке вопрос будет содержать
"за какое МИНИМАЛЬНОЕ число попыток можно ГАРАНТИРОВАННО узнать"
   uno-group
 
37 - 21.07.18 - 13:44
Для краткости 1,2,3,4 - замки; А,Б,С,Д ключи.
В простейшем случае. худший вариант
1а -0
1б -0
1с -0 значит 1д подходят +3 для поиска среди 3 ответ 6
более сложный вариант
Отдаем 1а,2б,3с получаем ответ 0,1,2,3
А вот дальше в зависимости от цифры различные действия
   Ching Woo
 
38 - 21.07.18 - 14:06
(36) Слово ГАРАНТИРОВАННО тут не приносит никакой пользы. Тот кто не понял оригинальную формулировку, может так же сказать что если угадать с первой попытки, то ГАРАНТИРОВАННО узнаешь какой ключ от какого замка.
   DTX 4th
 
39 - 23.07.18 - 14:08
(13) Похоже, для N=4 хватит четырёх попыток.
   DTX 4th
 
40 - 23.07.18 - 14:13
Не, тупанул. Но тему надо было поднять :)
   RomanYS
 
41 - 23.07.18 - 14:33
(40) +100))
Для N=4 получается за 5, и вроде получается доказать, что нельзя 4.

ТС колись. Откуда задача? Она должна аналитически решаться для произвольного N?
   Ненавижу 1С
 
42 - 23.07.18 - 15:05
(41) на просторах интернета нашел
решения не знаю
хочется верить в формулу

[log2(N!)]+1 при N>2
   Михаил Козлов
 
43 - 23.07.18 - 15:44
(42) Похоже на энтропию.
К планированию экспериментов отношения не имеет?
   Xapac
 
44 - 23.07.18 - 15:56
(0) а почему нельзя сразу N отдать, он все и подберет.
нет?
   RomanYS
 
45 - 23.07.18 - 15:59
(44) он скажет, что совпало N. Подбирать самому придется)))
   dezss
 
46 - 23.07.18 - 16:05
(42) ну ка при N = 3 посчитай этот факториал)))
   Xapac
 
47 - 23.07.18 - 16:05
а все понял
у меня получилось
(N-1) + (N-2) + ... + (N-(N-1)
для 2 - 1
для 3 - 3
для 4 - 6
   dezss
 
48 - 23.07.18 - 16:06
(47) ИМХО, должно быть меньше...
нужно другую стратеги выбирать, а не просто перебирать пары...
   Ненавижу 1С
 
49 - 23.07.18 - 16:10
(46) 3!=6
2<log2(6)<3
[log2(6)]=2
итого 3
 
 Рекламное место пустует
   dezss
 
50 - 23.07.18 - 16:28
(49) а теперь для 4)
   RomanYS
 
51 - 23.07.18 - 16:47
(50) для 4 тоже сойдется

(48) так это и должна быть другая стратегия. В случае перебора  пар ~N^2 будет.

(42) а алгоритм под формулу есть, хотя бы приблизительный?
   dezss
 
52 - 23.07.18 - 16:49
(51) не сойдется...и для 3 не сходится...для 3-х можно за 2 сравнения все сделать...
формула, вроде, почти правильная...только +1 надо убрать...
   Масянька
 
53 - 23.07.18 - 16:52
(52) Для 3-ех за 2 - докажи...
   RomanYS
 
54 - 23.07.18 - 16:53
(53) тоже интересно))
   Ненавижу 1С
 
55 - 23.07.18 - 17:00
(51)(52) алгоритма пока нет
есть общие соображения

всего вариантов ключ-замок равно N!
вот если мы сможем за каждый раз "увеличивать информацию вдвое", то вот так и получим

в частности при N=3 имеем 6 вариантов и за два хода не удается найти нужную перестановку
   Масянька
 
56 - 23.07.18 - 17:05
У меня получилось:
N = 3 -> 3
N = 4 -> 6
N = 5 -> 10
N = 6 -> 15
N = 7 -> 21
А тут мне сунули таракана... И я испугалась :(((((((((((((((
   Fish
 
57 - 23.07.18 - 17:07
(53) Смотри (1).
   Масянька
 
58 - 23.07.18 - 17:09
(57) Если да кабы во рту росли грибы. (С)
Да, не простые...
   Fish
 
59 - 23.07.18 - 17:12
(58) Просто для любых N ключей и N замков есть максимальное кол-во комбинаций, позволяющих подобрать все пары, а есть минимальное.
Для N = 3, минимум - это 2, а максимум 3.
   RomanYS
 
60 - 23.07.18 - 17:16
(55) Уже при N=4 "увеличивать информацию вдвое" не получается. При проверке двух пар в 16 случаях из 24 мы получим 1, т.е в этом случае область поиска сократится только в полтора раза. Проверять одну пару ещё хуже.
   Масянька
 
61 - 23.07.18 - 17:19
(55) А как ты себе это представляешь?
По любому, нужно или один ключ к каждому замку проверять, или один замок к каждому ключу.
И получается треугольник с катетами N-1.
   Ненавижу 1С
 
62 - 23.07.18 - 17:19
(60) тоже об этом думал, но мы еще автоматически узнаём, что и в другой паре 1.
но пока мало понятно
   RomanYS
 
63 - 23.07.18 - 17:25
(62) "еще автоматически узнаём, что и в другой паре 1" это уже  учтено в том, что 8 вариантов исключены, а 16 осталось.
Правда вторая проверка (тоже 2 пар) позволяет сузить область до 8 вариантов. Т.е. заветный 1бит во второй проверке мы получаем.
   Сияющий в темноте
 
64 - 24.07.18 - 00:45
А почему для четырех четыре нельзя?
гоним к1,к2 и з1,з2
результат 0,1 или 2
(попутно тот же результат получается для к3,к4 и з3,з4)
если ответ 0,то меняем замки местами з1,з2 на з3,з4 и мы как бы получили 2.
Если 1,то гоним пару к1,к3 з1,з3 тут тоже ответ будет 0,1 или 2
если ноль,то к1 для з4,а к4 для з1,к3 остается для з2,а к2 для з3
если 1,то мы уперлись в к1 для з3 или к3 для з1,что то одно,нужно прогнать к1 и з3,чтобы это получить
если 1,то к1 для з3,к3 для з2,к2 для з4 и к4 для з1
то есть,три прогона.

или что то не так?
   Сияющий в темноте
 
65 - 24.07.18 - 09:27
Четыре прогона,т.к.вторую пару точно также нужно гнать.
   Сияющий в темноте
 
66 - 24.07.18 - 09:37
Вообще,максимальная информативность,когда гоним половину,то есть Н/2,всего исходов Н факториал.
то есть грубая оценка ((Н/2)+1)^Х=Н!
наш х число прогонов.
только получается целая часть от Н/2.
когда 3,то 2^Х>=6, то есть х=3
когда 4,то 3^Х>=24,то получается 3, значит,нужно искать способ найти за 3 шага.
   Сияющий в темноте
 
67 - 24.07.18 - 09:41
Для 5 получается 5 вариантов,нужно смотреть.
   RomanYS
 
68 - 24.07.18 - 10:30
(66) Прочитай (60) и (63)
Исходы проверок сильно неравномерно распределены. Для проверки двух пар при N=4 в
четырех случаях вернется "0"
четырех - "2"
шестнадцати(!) - "1".
Твои рассуждения (и оценка) были бы верны, если после каждой проверки число вариантов сокращалось бы втрое.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует