Vladimir
Лол, это осоновы теории информации
Дима
А ещё мне нравится издеваться над некорректными задачами
Дима
Если ты кодируешь информацию временем (что невозможно), то ты передаешь больше информации
Я тебе только что рассказал как кодировать информацию временем, лол
Evgeny
Но так же входит возможность не передавать два бита, что тоже увеличивает битность вариантов
Дима
Конечно же
Roman
оох.. задача про передачу информации о тех 4х объектах, которые защищать не надо.
Vladimir
Roman
10 объектов, защитить можно 6. как раз 4 объекта остаются.
Vladimir
Я не прочитал условия (
Vladimir
Думал там надо защищать 8
Дима
Она не предполагает такого варианта решения, так что в каком-то смысле ты конечно же прав
Roman
>есть возможность защитить средствами ПВО только любые шесть объектов
Vladimir
Вот вам, задачка достойная могучих умов разработчиков:
Могущественная террористическая организация СПЕКТР собирается нанести ракетный удар по каким-то двум из десяти секретных объектов разведывательной службы МИ-6, у которой есть возможность защитить средствами ПВО только любые шесть объектов: если атакован будет любой из них, то ракеты будут сбиты на подлете. Но если атакован будет какой-то из незащищенных объектов, то он будет полностью уничтожен.
К счастью, Джеймс Бонд сможет в день атаки узнать, какие именно объекты будут атакованы, и после этого сможет передать в штаб МИ-6 два бита информации. Помогите штабу и Бонду договориться о таком способе передачи информации, чтобы ни один из атакуемых объектов не пострадал.
пронумеруем атакуемые объекты от 1 до 10
если первый бит 1 - первый атакуемый объект между 1 и 4 включительно
если второй бит 1 - второй атакуемый объект между 3 и 6 включительно
соответственно:
00 - достаточно защитить 7,8,9,10
10 - защищаем 1,2,7,8,9,10
01 - защищаем 5,6,7,8,9,10
11 - защищаем 1,2,3,4,5,6
Vladimir
А не, я все правльно прочитал
Vladimir
Не понял вопроса
Vladimir
мне все равно кажется, что это невозможно
Vladimir
Хмм
Vladimir
Видимо 2 имеет значение
Vladimir
То что я атакую две
Vladimir
Не, я просто произвел расчет, но он неявно подразумевает, что можно атаковать 4
Vladimir
Смотри, логика следующая
Vladimir
да, да)
Vladimir
но все же
Vladimir
нужно передать информацию о 4 выбранных объектах
Vladimir
пронумеруем атакуемые объекты от 1 до 10
если первый бит 1 - первый атакуемый объект между 1 и 4 включительно
если второй бит 1 - второй атакуемый объект между 3 и 6 включительно
соответственно:
00 - достаточно защитить 7,8,9,10
10 - защищаем 1,2,7,8,9,10
01 - защищаем 5,6,7,8,9,10
11 - защищаем 1,2,3,4,5,6
Немного неверно сформулировал, вот так:
если первый бит 1 - один из атакуемых объектов между 1 и 4 включительно
если второй бит 1 - второй атакуемый объект между 3 и 6 включительно
Vladimir
всего их 10
Vladimir
количество комбинаций 10! / 4!(10 - 4)!
Vladimir
= 210
Vladimir
log 2 210 = ~7.7
Vladimir
итого 8 бит
Vladimir
но, фишка в том что конкретная комбинация не нужна
Vladimir
А стоп
Vladimir
В твоем решении
Vladimir
1, 7 например
Vladimir
а, понял, группы незащищенных
Vladimir
3, 7?
Vladimir
не
Vladimir
похоже на правду
Vladimir
Осталась в рамках комбинаторики и теории информации показать
Vladimir
необходимое количество информации
Дмитрий
да не за что :)
Vladimir
чет сходу не получается
Дмитрий
у нас тут пол офиса над ней упарывалось
Vladimir
Показать, что допустим достаточно <2 бит теоретически
Дмитрий
разными, тестировщики, разработчики...
Дмитрий
хых
Дмитрий
от вашего стола нашему?
Дмитрий
Ну можно, только я буду в пути через несколько минут
Дмитрий
Очередь шредингера
Дмитрий
:)
Alexander
с каких пор логарифм от длины — константа?)
Alexander
если тоже включить зануду, то константа не может зависеть от длины по определению, очевидно же)
Alexander
ага, тогда любая задача решается за константное время, только константа порядка n! :)
Vladimir
а в чем проблема? или очередь в конце должна остаться целой?)
Alexander
ограничения по времени нет?)
Alexander
числа произвольные?)
Alexander
больше интересует их знаки)
Vladimir
хм, то есть не существует значения которое можно использовать в качестве тэга
Максим
@arealit , как ты это сделал
Alexander
ох, долго расписывать алгоритм тогда придётся)
будем считать, что первый элемент положительный
инвертируем его
двигаемся вправо по очереди, пока не найдём отрицательный элемент, попутно считая шаги
находим, инвертируем, и двигаемся отсчитанное количество шагов назад
если там положительный элемент — мы нашли длину
если нет, повторяем алгоритм, пропуская предыдущее количество шагов
Alexander
как кончится?) у нас же она всегда остается постоянной длины
достаём элемент сначала, пихаем в конец, и наоборот
Alexander
да, про ноль забыл)
можно дробные числа добавлять
Alexander
да и на ноль можно забить
Alexander
у нас же индикатором итерации служат отрицательные
Alexander
вообще очень похоже на задачу про вагоны, но там попроще, там сохранять состояния вагонов не надо)
Alexander
а вообще задачка прикольная, жаль у многих на собеседованиях бомбит от таких)
Владимир
да ну, скучная
andrei
Vitaly
да ну, скучная
А вот такая?
Есть 2 игральные кости(2 куба), нужно пронумеровать так, чтобы при броске выпадали числа от 2 до 13 включительно, с нормальным распределением.
Denis
Во, отлично :) работа с YAML в Node.js, теперь можно тулзы для CoreOS, Kubernetes и Concourse писать)
Denis
Статья
Работаем с YAML в Node.js.
Ссылка
#Article #YAML #NodeJS
Джон
минута?
Alexander
да, минута
если нужно доказать, то по индукции должно прокатить
наверняка, есть решение проще, но лень думать)
Джон
да, минута
если нужно доказать, то по индукции должно прокатить
наверняка, есть решение проще, но лень думать)
я в математике не силен, на бумажке нарисовал просто, получилось, что за минуту максимум
Джон
а можете пояснить по двум битам?
Джон
1234 3456 5678 7890 я правильно понимаю?
Джон
не понятно, это безопасные объекты передаются?
Джон
я понимаю, решил для себя как смог )