ReSQL.ru
     
powered by simpleCommunicator - 2.0.35     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / из тестового задания
25 сообщений из 166, страница 4 из 7
  4  все
из тестового задания
    #39150225
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kolobok0
Участник
Aleksandr Sharahov...Если вы можете доказать...

ок. понял.

Тупое разложение, на маленьком кол-ве, даёт возможность так сказать(N=K-1).
типа практически. Мне пока не получилось подойти универсально к разложению в матрицу.
Есть мысли, но пока занят :( попробую позже осуществить второй подход к снаряду...

(круглый)
ЗЫ
у Вас сообщений три шестёрки - явно намёк на пора спать:)
...
Рейтинг: 0 / 0
19.01.2016, 02:21
| Ответить | Цитировать | Написать  
из тестового задания
    #39150226
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Akinamini.weblabвключены следующие выключатели
[3, 4, 11, 19, 27, 35]

шпион в комнате номер 6

ваши действия?

Значимыми считаем первые 7 тумблеров. Остальные игнорируем.
Текущая сумма 3+4=7. Требуется получить сумму, которая при делении на 8 даст в остатке 6. Ближайшие такие суммы - 6 и 14. 6 получить одним переключением нельзя. 14 - можно (3+4+7).
Наши действия - включить тумблер 7.


Aleksandr Sharahov Akina,

Это не очевидно, что ваш алгоритм (перебор?) всегда найдет решение.

Можете доказать?

3 4 6
room 3
...
Рейтинг: 0 / 0
19.01.2016, 02:40
| Ответить | Цитировать | Написать  
из тестового задания
    #39150232
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вообще линейная комбинация, в данном случае, не зависимо от количества элементов, 7,8, или 40 бит, судя по всему не будет давать решение. Доказать это можно достаточно просто:
Пусть значение линейной комбинации на определенном наборе единичных бит даёт нам число t. Пусть t%8!=n(номер комнаты). В таком случае, мы должны либо добавить один элемент из линейной комбинации, либо убрать из неё определённый элемент. Однако, достаточно легко допустить что в текущем наборе элементов уже присутствуют все элементы которые можно было добавить для требуемого результата, и в этом же наборе отсутствуют все элементы которые можно было бы убрать для требуемого результата. Таким образом, изменением положения одного бита мы не добьёмся требуемого результата.

Aleksandr Sharahovmayton,

это первое, что приходит в голову,
второе - забубенить модульную арифметику,
но это все из пушки по воробьям,
надо ж и голову иметь.

С интересом глянул бы на 40-битное решение )

маловероятно что оно существует
...
Рейтинг: 0 / 0
19.01.2016, 04:25
| Ответить | Цитировать | Написать  
из тестового задания
    #39150255
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
От блин, вы сделали мой день !!!
как теперь работать ???????
...
Рейтинг: 0 / 0
19.01.2016, 07:32
| Ответить | Цитировать | Написать  
из тестового задания
    #39150312
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblabдля шифровки используем первые 3 ячейки.
если наш агент приходит в гостиницу и комната для него заказана, используем колонку Room booked
если наш агент приходит в гостиницу и комната для него предварительно не заказана,
используем колонку Room not booked
Код: plaintext
1.
2.
3.
4.
---------------------------------------------
|Room Number | Room booked | Room not booked|
---------------------------------------------
|Room 1	     |000          |111             |

PS: в крайнем случае используем жвачку


Хм... здесь нет чита и нет решения. Вы привели табличку декода 8-ричной системы.
И что дальше с этим делать?
...
Рейтинг: 0 / 0
19.01.2016, 09:53
| Ответить | Цитировать | Написать  
из тестового задания
    #39150327
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Честно говоря у меня - масса решений. Но все они требуют чтобы изначальное
состояние тумблеров было - не случайным. Случайность "обламывает" все поиски
по 40 битами. С ней пока можно гарантировать только "чет-нечет" или ДА/Нет.
...
Рейтинг: 0 / 0
19.01.2016, 10:12
| Ответить | Цитировать | Написать  
из тестового задания
    #39150344
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Да тут Aleksandr Sharahov уже всё сделал вроде-бы, только на собеседование вместо автора не сходил
...
Рейтинг: 0 / 0
19.01.2016, 10:30
| Ответить | Цитировать | Написать  
из тестового задания
    #39150349
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

У меня их тоже вроде бы много: ((2^N)-1)! решений для 2^N комнат.
Но это лишь одно решение с точностью до перестановки битов в кодах.
...
Рейтинг: 0 / 0
19.01.2016, 10:36
| Ответить | Цитировать | Написать  
из тестового задания
    #39150365
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Apoj_sqlDima TХЗ как решать, но я проверялку написал

Тупо генерит все варианты и проверяет что из каждого можно получить все 8 комнат одним переключением.

Алгоритм в методе algo(), менять только его.

SWITCH_COUNT - кол-во переключателей. 40 это очень долго 10^13 вариантов.
Тестил на 30.

Формула SUM % N не работает при N от 9 до 13, дальше не тестил.
Ещё бы написали алгоритм проверки алгоритма проверки. Было ж указано, что при mod 9 8 и 0 одно и то же. У Вас я это не увидел при проверке.
ЗЫ Мне уныло лезть в c++:
0) надо ставить к студии с++
1) я "туда" лез последний раз 6 месяцев назад (надо было решать тестовое задание для моего нонешнего работодателя)
2) удовольствия при п.1 не получил и лезть туда без особой нужды нет ни малейшего желания.
Тоже проверял.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
int algo() {
	int sum = 0;
	for (int i = 1; i <= SWITCH_COUNT; i++) {
		if (arr[i]) sum = sum + i;
	}
	int x = sum % 9;
	if (x == 0) x = 8;
	return x;
}


При 32х переключателях выдал нельзя получить 6 при включенных 6, 15, 24.

PS Не нравиться С - портируй на то что нравиться, код простейший, специально ничего специфичного из С не использовал. На любой ЯП перенесется легкой правкой синтаксиса.
...
Рейтинг: 0 / 0
19.01.2016, 10:54
| Ответить | Цитировать | Написать  
из тестового задания
    #39150385
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ну ё моё, всё просто

для описания номера до 8-ми комнат нужно 3 бита (доказывать не буду)

для решения задачи достаточно 3 + 3 +1 = 7 ключей
 

выделим 3 взаимно пересекающиеся группы

1, 2, 3, 4

1, 4, 5, 6

1, 6, 7, 2
каждый бит номера комнаты будет равен чётности количества включеных ключей в конкретной группе: чётно - 1, нечетно - 0

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

1-й бит измененяем 3-й ключ
2-й бит - 5-й ключ
3-й бит - 7-й ключ
1-й и 2-й - 4-й ключ
2-й и 3-й - 6-й ключ
3-й и 1-й - 2-й ключ
все - 1-й ключ

...
Рейтинг: 0 / 0
19.01.2016, 11:11
| Ответить | Цитировать | Написать  
из тестового задания
    #39150404
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
kealon(Ruslan),

эх, рановато... каждому интересно ж самостоятельно дойти )
...
Рейтинг: 0 / 0
19.01.2016, 11:25
| Ответить | Цитировать | Написать  
из тестового задания
    #39150415
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
kealon(Ruslan),

Заглянул под спойлер и немного успокоился )
Систематическое решение выглядит иначе.
...
Рейтинг: 0 / 0
19.01.2016, 11:32
| Ответить | Цитировать | Написать  
из тестового задания
    #39150419
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Aleksandr Sharahov,

ну не обязательно спойлер открывать ;-)
...
Рейтинг: 0 / 0
19.01.2016, 11:32
| Ответить | Цитировать | Написать  
из тестового задания
    #39150434
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Ломать голову ближайшие пару дней некогда, заглянул под спойлер, затестил решение kealon(Ruslan), правильно работает на 7 переключателях. На любом большем количестве тоже заработает.
...
Рейтинг: 0 / 0
19.01.2016, 11:42
| Ответить | Цитировать | Написать  
из тестового задания
    #39150463
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)ну ё моё, всё просто

для описания номера до 8-ми комнат нужно 3 бита (доказывать не буду)

для решения задачи достаточно 3 + 3 +1 = 7 ключей

Мне кажется в этом есть связь с Матричным Кодированием или Исправлением ошибок.
Точно не вспомню термин но лет 15 назад мы проходили по Теории Передачи Сигналов.
...
Рейтинг: 0 / 0
19.01.2016, 12:19
| Ответить | Цитировать | Написать  
из тестового задания
    #39150502
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonkealon(Ruslan)ну ё моё, всё просто

для описания номера до 8-ми комнат нужно 3 бита (доказывать не буду)

для решения задачи достаточно 3 + 3 +1 = 7 ключей

Мне кажется в этом есть связь с Матричным Кодированием или Исправлением ошибок.
Точно не вспомню термин но лет 15 назад мы проходили по Теории Передачи Сигналов.
не могу сказать, у нас только у радиофизиков вроде было что-то с устойчивостью сигналов, либо я прогулял
в общем виде для шифровки N бит таким способом нужно (как и написал Aleksandr Sharahov)
SUM(i=1.. N , C(i,N)) = 2^N - C (0,N) = 2^N - 1 ключей
где
С(k,n) = n! / [k! (n-k)!]
...
Рейтинг: 0 / 0
19.01.2016, 12:53
| Ответить | Цитировать | Написать  
из тестового задания
    #39150556
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton,

почему не решение?
пусть вы агент-сменщик, приходите в гостиницу
1) смотрите на коммутационный щит и записываете первые 3 позиции в блокнотик
2) спрашиваете портье, заказана ли для вас комната в гостинице
3)
а) комната заказана: смотрите в таблицу, в колонку 'Room booked', находите комбинацию из блокнотика и получаете номер комнаты
б) комната не заказана: смотрите в таблицу, в колонку 'Room not booked', находите комбинацию из блокнотика и получаете номер комнаты

( все по ТЗ )
...
Рейтинг: 0 / 0
19.01.2016, 13:24
| Ответить | Цитировать | Написать  
из тестового задания
    #39150568
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahovkealon(Ruslan),

эх, рановато... каждому интересно ж самостоятельно дойти )

так вы же уже все объяснили. нет?
=)
...
Рейтинг: 0 / 0
19.01.2016, 13:29
| Ответить | Цитировать | Написать  
из тестового задания
    #39150584
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mini.weblabAleksandr Sharahovkealon(Ruslan),

эх, рановато... каждому интересно ж самостоятельно дойти )

так вы же уже все объяснили. нет?
=)
от вас же требуют суть рассказать (а именно как получилась эта табличка)
...
Рейтинг: 0 / 0
19.01.2016, 13:41
| Ответить | Цитировать | Написать  
из тестового задания
    #39150607
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov
Если вы можете доказать нечто подобное для произвольного количества комнат,
то вам, конечно, не за чем "впрягать степени двоек". )

пробую:

пусть у нас N переключателей,
Идея метод шифрования (как я его поняла):
из текущего состояния, поменяв один переключатель, мы можем перейти в N отличных от начального состояний
(что даст в сумме 1+(N) = N+1 различных состояний системы)


Итог: с помощью вашего метода, используя N переключателей, можно зашифровать номер N+1 комнату
...
Рейтинг: 0 / 0
19.01.2016, 13:57
| Ответить | Цитировать | Написать  
из тестового задания
    #39150611
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
kealon(Ruslan),
Александр уже все объяснил
18698560
...
Рейтинг: 0 / 0
19.01.2016, 14:01
| Ответить | Цитировать | Написать  
из тестового задания
    #39150633
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,

для вас, как я поняла, - это типовая задача
а предметную область обозначить можно?
( в смысле куда копать, чтоб по фэншую? =) )
...
Рейтинг: 0 / 0
19.01.2016, 14:16
| Ответить | Цитировать | Написать  
из тестового задания
    #39150702
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mini.weblabkealon(Ruslan),
Александр уже все объяснил
18698560
это называется "как кнопки нажимать", а не решение :-)
...
Рейтинг: 0 / 0
19.01.2016, 15:07
| Ответить | Цитировать | Написать  
из тестового задания
    #39150714
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabAleksandr Sharahov,

для вас, как я поняла, - это типовая задача
а предметную область обозначить можно?
( в смысле куда копать, чтоб по фэншую? =) )

По фэншую 2 сообщения kealon(Ruslan): 18700090 и 18700779
практически полностью и составляют решение.
Т.е. суть задачи состоит в перечислении всех подмножеств множества из N=3 битов.
Всего их (вспоминаем сумму биномиальных коэффициентов) 2^N=8.
Перейти от одного подмножества к другому можно
за одну операцию объединение или разности (в нашем случае xor).
Для каждого отдельного бита все эти xor'ы выродятся в те самые суммы.
На подмножества можно смотреть как на функции перехода xor'ом от одного значения к другому.
-1 появляется от того, что тождественная функция нам не нужна.
...
Рейтинг: 0 / 0
19.01.2016, 15:19
| Ответить | Цитировать | Написать  
из тестового задания
    #39150726
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
kealon(Ruslan),

ну когда табличку привели, объяснили, что и как нужно нажимать, то решение додумать уже не проблема :-)
идея метода в 18701187 (это в моем понимании, хотя, может, Александр и не согласится)

ПС:
честно говоря, пока не увидела решение Александра, даже в голову не пришло посмотреть на задачу именно в таком ключе
:)
...
Рейтинг: 0 / 0
19.01.2016, 15:28
| Ответить | Цитировать | Написать  
25 сообщений из 166, страница 4 из 7
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / из тестового задания
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru, Чат Кролика       Пашэ: Рисунки, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&startmsg=39150225&tid=1339609]:
 0ms
get settings:
 11ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 39ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 66ms
get tp. blocked users:
 1ms
others: 253ms
total:  406ms
созд. / загр.: 406ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]