ReSQL.ru
     
powered by simpleCommunicator - 2.0.34     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / из тестового задания
166 сообщений из 166, показаны все 7 страниц
  все  
из тестового задания
    #39149208
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Вы секретный агент, следящий за вражеским шпионом.
Вы следуете за шпионом в отель. В отеле 8 комнат, и шпион остановился в одной из этих 8 комнат.
Ваша цель передать коллеге-агенту номер комнаты, в которой поселился враг.
Коллега прибудет в отель на следующий день после вашего отъезда из отеля.

Передать информацию своему коллеге вы можете, переключив один из переключателей на коммутационной
доске из 40 переключателей. (Любой переключатель на доске может быть как включен, так и выключен.)

Вы заранее договорились с коллегой о методе шифровки.
Ни вы, ни ваш коллега, не знаете начальной конфигурации коммутационной доски.
Чтобы передать сообщение, вы можете переключить только один из переключателей.
Метод должен работать при любой конфигурации коммутационной доски.
До момента передачи сообщения, коммутационная доска будет оставаться в том же состоянии, в котором вы ее оставите.

предлагайте решения :)
...
Рейтинг: 0 / 0
17.01.2016, 22:28
| Ответить | Цитировать | Написать  
из тестового задания
    #39149332
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если переключатели это 0 и 1 (два состояния то их всех можно представить как 40 битное число).

Например

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
01010 
00011 
11111 
00011 
00000 
11011 
01010 
11011



Далее необходимо придумать как закодировать целое число и поместить его
внуть этого шумящего числа.

Поскольку количество комнат кодируется тремя битами (000...111) то
нам нужно минимум три переключения.

Еще можно догориться что номер комнаы будет указывать переход 0 -> 1
в последовательности 40 бит (его позиция слева или справа)
но условие нас ограничивает. Нам нужно минимум два переключения а максимум - ... наверное 8.

Можно еще подмуать о каких нибудь свойствах четности если
рассматривать переключатели как матрику 5 на 8.
Но я пока ничего не придумал.
...
Рейтинг: 0 / 0
18.01.2016, 09:39
| Ответить | Цитировать | Написать  
из тестового задания
    #39149352
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblab, а это точно из тестового задания?

я угадаю эту мелодию с гораздо меньшего числа нот )
...
Рейтинг: 0 / 0
18.01.2016, 10:04
| Ответить | Цитировать | Написать  
из тестового задания
    #39149402
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Под спойлер лучше не смотреть, если вы хотите получить удовольствие от самостоятельного решения задачи.
На мой взгляд, само по себе определение необходимого числа бит - уже довольно интересная задача.
Алгоритм не привожу, чтобы сохранить интригу, пока только таблица переключений.

 
Таблица переключений
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
                     New State For Room
  Old   ----------------------------------------------
 State    0     1     2     3     4     5     6     7
------------------------------------------------------
    0     0     1     4    32    16     8     2   128
    1     0     1    33     5     9    17   129     3
    2     0   130    18    10     6    34     2     3
    3   131     1    11    19    35     7     2     3
    4     0    36     4     5     6   132    20    12
    5    37     1     4     5   133     7    13    21
    6    22    14     4   134     6     7     2    38
    7    15    23   135     5     6     7    39     3
    8     0    24   136    10     9     8    40    12
    9    25     1    11   137     9     8    13    41
   10    42    14    11    10   138     8     2    26
   11    15    43    11    10     9   139    27     3
   12   140    14     4    28    44     8    13    12
   13    15   141    29     5     9    45    13    12
   14    15    14    46    10     6    30   142    12
   15    15    14    11    47    31     7    13   143
   16     0    24    18   144    16    17    20    48
   17    25     1   145    19    16    17    49    21
   18    22    50    18    19    16   146     2    26
   19    51    23    18    19   147    17    27     3
   20    22   148     4    28    16    52    20    21
   21   149    23    29     5    53    17    20    21
   22    22    23    18    54     6    30    20   150
   23    22    23    55    19    31     7   151    21
   24    25    24    56    28    16     8   152    26
   25    25    24    29    57     9    17    27   153
   26   154    24    18    10    58    30    27    26
   27    25   155    11    19    31    59    27    26
   28    60    24    29    28   156    30    20    12
   29    25    61    29    28    31   157    13    21
   30    22    14   158    28    31    30    62    26
   31    15    23    29   159    31    30    27    63
   32     0    36    33    32   160    34    40    48
   33    37     1    33    32    35   161    49    41
   34    42    50   162    32    35    34     2    38
   35    51    43    33   163    35    34    39     3
   36    37    36     4    32    44    52   164    38
   37    37    36    33     5    53    45    39   165
   38   166    36    46    54     6    34    39    38
   39    37   167    55    47    35     7    39    38
   40    42   168    56    32    44     8    40    41
   41   169    43    33    57     9    45    40    41
   42    42    43    46    10    58    34    40   170
   43    42    43    11    47    35    59   171    41
   44    60    36    46   172    44    45    40    12
   45    37    61   173    47    44    45    13    41
   46    42    14    46    47    44   174    62    38
   47    15    43    46    47   175    45    39    63
   48   176    50    56    32    16    52    49    48
   49    51   177    33    57    53    17    49    48
   50    51    50    18    54    58    34   178    48
   51    51    50    55    19    35    59    49   179
   52    60    36   180    54    53    52    20    48
   53    37    61    55   181    53    52    49    21
   54    22    50    55    54   182    52    62    38
   55    51    23    55    54    53   183    39    63
   56    60    24    56    57    58   184    40    48
   57    25    61    56    57   185    59    49    41
   58    42    50    56   186    58    59    62    26
   59    51    43   187    57    58    59    27    63
   60    60    61    56    28    44    52    62   188
   61    60    61    29    57    53    45   189    63
   62    60   190    46    54    58    30    62    63
   63   191    61    55    47    31    59    62    63
   64    64    65    68    96    80    72    66   192
   65    64    65    97    69    73    81   193    67
   66    64   194    82    74    70    98    66    67
   67   195    65    75    83    99    71    66    67
   68    64   100    68    69    70   196    84    76
   69   101    65    68    69   197    71    77    85
   70    86    78    68   198    70    71    66   102
   71    79    87   199    69    70    71   103    67
   72    64    88   200    74    73    72   104    76
   73    89    65    75   201    73    72    77   105
   74   106    78    75    74   202    72    66    90
   75    79   107    75    74    73   203    91    67
   76   204    78    68    92   108    72    77    76
   77    79   205    93    69    73   109    77    76
   78    79    78   110    74    70    94   206    76
   79    79    78    75   111    95    71    77   207
   80    64    88    82   208    80    81    84   112
   81    89    65   209    83    80    81   113    85
   82    86   114    82    83    80   210    66    90
   83   115    87    82    83   211    81    91    67
   84    86   212    68    92    80   116    84    85
   85   213    87    93    69   117    81    84    85
   86    86    87    82   118    70    94    84   214
   87    86    87   119    83    95    71   215    85
   88    89    88   120    92    80    72   216    90
   89    89    88    93   121    73    81    91   217
   90   218    88    82    74   122    94    91    90
   91    89   219    75    83    95   123    91    90
   92   124    88    93    92   220    94    84    76
   93    89   125    93    92    95   221    77    85
   94    86    78   222    92    95    94   126    90
   95    79    87    93   223    95    94    91   127
   96    64   100    97    96   224    98   104   112
   97   101    65    97    96    99   225   113   105
   98   106   114   226    96    99    98    66   102
   99   115   107    97   227    99    98   103    67
  100   101   100    68    96   108   116   228   102
  101   101   100    97    69   117   109   103   229
  102   230   100   110   118    70    98   103   102
  103   101   231   119   111    99    71   103   102
  104   106   232   120    96   108    72   104   105
  105   233   107    97   121    73   109   104   105
  106   106   107   110    74   122    98   104   234
  107   106   107    75   111    99   123   235   105
  108   124   100   110   236   108   109   104    76
  109   101   125   237   111   108   109    77   105
  110   106    78   110   111   108   238   126   102
  111    79   107   110   111   239   109   103   127
  112   240   114   120    96    80   116   113   112
  113   115   241    97   121   117    81   113   112
  114   115   114    82   118   122    98   242   112
  115   115   114   119    83    99   123   113   243
  116   124   100   244   118   117   116    84   112
  117   101   125   119   245   117   116   113    85
  118    86   114   119   118   246   116   126   102
  119   115    87   119   118   117   247   103   127
  120   124    88   120   121   122   248   104   112
  121    89   125   120   121   249   123   113   105
  122   106   114   120   250   122   123   126    90
  123   115   107   251   121   122   123    91   127
  124   124   125   120    92   108   116   126   252
  125   124   125    93   121   117   109   253   127
  126   124   254   110   118   122    94   126   127
  127   255   125   119   111    95   123   126   127
------------------------------------------------------
...
Рейтинг: 0 / 0
18.01.2016, 11:03
| Ответить | Цитировать | Написать  
из тестового задания
    #39149424
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Дико извиняюсь, в процедуру печати вкралась ошибка.
 
Правильная таблица переключений
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
                     New State For Room
  Old   ----------------------------------------------
 State    0     1     2     3     4     5     6     7
------------------------------------------------------
    0     0     1     4    32    16     8     2    64
    1     0     1    33     5     9    17    65     3
    2     0    66    18    10     6    34     2     3
    3    67     1    11    19    35     7     2     3
    4     0    36     4     5     6    68    20    12
    5    37     1     4     5    69     7    13    21
    6    22    14     4    70     6     7     2    38
    7    15    23    71     5     6     7    39     3
    8     0    24    72    10     9     8    40    12
    9    25     1    11    73     9     8    13    41
   10    42    14    11    10    74     8     2    26
   11    15    43    11    10     9    75    27     3
   12    76    14     4    28    44     8    13    12
   13    15    77    29     5     9    45    13    12
   14    15    14    46    10     6    30    78    12
   15    15    14    11    47    31     7    13    79
   16     0    24    18    80    16    17    20    48
   17    25     1    81    19    16    17    49    21
   18    22    50    18    19    16    82     2    26
   19    51    23    18    19    83    17    27     3
   20    22    84     4    28    16    52    20    21
   21    85    23    29     5    53    17    20    21
   22    22    23    18    54     6    30    20    86
   23    22    23    55    19    31     7    87    21
   24    25    24    56    28    16     8    88    26
   25    25    24    29    57     9    17    27    89
   26    90    24    18    10    58    30    27    26
   27    25    91    11    19    31    59    27    26
   28    60    24    29    28    92    30    20    12
   29    25    61    29    28    31    93    13    21
   30    22    14    94    28    31    30    62    26
   31    15    23    29    95    31    30    27    63
   32     0    36    33    32    96    34    40    48
   33    37     1    33    32    35    97    49    41
   34    42    50    98    32    35    34     2    38
   35    51    43    33    99    35    34    39     3
   36    37    36     4    32    44    52   100    38
   37    37    36    33     5    53    45    39   101
   38   102    36    46    54     6    34    39    38
   39    37   103    55    47    35     7    39    38
   40    42   104    56    32    44     8    40    41
   41   105    43    33    57     9    45    40    41
   42    42    43    46    10    58    34    40   106
   43    42    43    11    47    35    59   107    41
   44    60    36    46   108    44    45    40    12
   45    37    61   109    47    44    45    13    41
   46    42    14    46    47    44   110    62    38
   47    15    43    46    47   111    45    39    63
   48   112    50    56    32    16    52    49    48
   49    51   113    33    57    53    17    49    48
   50    51    50    18    54    58    34   114    48
   51    51    50    55    19    35    59    49   115
   52    60    36   116    54    53    52    20    48
   53    37    61    55   117    53    52    49    21
   54    22    50    55    54   118    52    62    38
   55    51    23    55    54    53   119    39    63
   56    60    24    56    57    58   120    40    48
   57    25    61    56    57   121    59    49    41
   58    42    50    56   122    58    59    62    26
   59    51    43   123    57    58    59    27    63
   60    60    61    56    28    44    52    62   124
   61    60    61    29    57    53    45   125    63
   62    60   126    46    54    58    30    62    63
   63   127    61    55    47    31    59    62    63
   64     0    66    72    80    96    68    65    64
   65    67     1    81    73    69    97    65    64
   66    67    66    98    70    74    82     2    64
   67    67    66    71    99    83    75    65     3
   68    76    84     4    70    69    68   100    64
   69    85    77    71     5    69    68    65   101
   70   102    66    71    70     6    68    78    86
   71    67   103    71    70    69     7    87    79
   72    76   104    72    73    74     8    88    64
   73   105    77    72    73     9    75    65    89
   74    90    66    72    10    74    75    78   106
   75    67    91    11    73    74    75   107    79
   76    76    77    72   108    92    68    78    12
   77    76    77   109    73    69    93    13    79
   78    76    14    94    70    74   110    78    79
   79    15    77    71    95   111    75    78    79
   80   112    84    81    80    16    82    88    64
   81    85   113    81    80    83    17    65    89
   82    90    66    18    80    83    82   114    86
   83    67    91    81    19    83    82    87   115
   84    85    84   116    80    92    68    20    86
   85    85    84    81   117    69    93    87    21
   86    22    84    94    70   118    82    87    86
   87    85    23    71    95    83   119    87    86
   88    90    24    72    80    92   120    88    89
   89    25    91    81    73   121    93    88    89
   90    90    91    94   122    74    82    88    26
   91    90    91   123    95    83    75    27    89
   92    76    84    94    28    92    93    88   124
   93    85    77    29    95    92    93   125    89
   94    90   126    94    95    92    30    78    86
   95   127    91    94    95    31    93    87    79
   96   112   104    98    32    96    97   100    64
   97   105   113    33    99    96    97    65   101
   98   102    66    98    99    96    34   114   106
   99    67   103    98    99    35    97   107   115
  100   102    36   116   108    96    68   100   101
  101    37   103   109   117    69    97   100   101
  102   102   103    98    70   118   110   100    38
  103   102   103    71    99   111   119    39   101
  104   105   104    72   108    96   120    40   106
  105   105   104   109    73   121    97   107    41
  106    42   104    98   122    74   110   107   106
  107   105    43   123    99   111    75   107   106
  108    76   104   109   108    44   110   100   124
  109   105    77   109   108   111    45   125   101
  110   102   126    46   108   111   110    78   106
  111   127   103   109    47   111   110   107    79
  112   112   113   116    80    96   120   114    48
  113   112   113    81   117   121    97    49   115
  114   112    50    98   122   118    82   114   115
  115    51   113   123    99    83   119   114   115
  116   112    84   116   117   118    52   100   124
  117    85   113   116   117    53   119   125   101
  118   102   126   116    54   118   119   114    86
  119   127   103    55   117   118   119    87   115
  120   112   104    56   122   121   120    88   124
  121   105   113   123    57   121   120   125    89
  122    90   126   123   122    58   120   114   106
  123   127    91   123   122   121    59   107   115
  124    60   126   116   108    92   120   125   124
  125   127    61   109   117   121    93   125   124
  126   127   126    94   122   118   110    62   124
  127   127   126   123    95   111   119   125    63
------------------------------------------------------
...
Рейтинг: 0 / 0
18.01.2016, 11:24
| Ответить | Цитировать | Написать  
из тестового задания
    #39149504
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, спойлер еще не нажимал. Т.к. интересно подумать.
Правильно-ли я понял что автор имел в виду совершенно-случайное
положение рубильников на панели? Тоесть секретный агент
предварительно ничено не устанавливает а берёт любой
произвольный расклад?
...
Рейтинг: 0 / 0
18.01.2016, 12:33
| Ответить | Цитировать | Написать  
из тестового задания
    #39149521
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Попадалась как-то похожая задача. То ли тут, то ли на хабре. Но как порешалась - не помню :(
...
Рейтинг: 0 / 0
18.01.2016, 12:41
| Ответить | Цитировать | Написать  
из тестового задания
    #39149525
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Для кодирования 8 вариантов должно быть достаточно 8 битов (8 переключателей). А само решение должно базироваться на сетке чётности.
...
Рейтинг: 0 / 0
18.01.2016, 12:44
| Ответить | Цитировать | Написать  
из тестового задания
    #39149528
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

да, верно.

Т.е. когда мы подходим к переключателям, мы видим совершенно случайное их положение.
Если положение переключателей уже кодирует нужную нам комнату, то просто уходим.
В противном случае изменяем положение ровно одного переключателя и тем самым кодируем нужную комнату.
...
Рейтинг: 0 / 0
18.01.2016, 12:45
| Ответить | Цитировать | Написать  
из тестового задания
    #39149533
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, нет ли в этом связи с кодами Хэмминга?
...
Рейтинг: 0 / 0
18.01.2016, 12:48
| Ответить | Цитировать | Написать  
из тестового задания
    #39149534
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton, я не заметил, правда может плохо смотрел )
...
Рейтинг: 0 / 0
18.01.2016, 12:49
| Ответить | Цитировать | Написать  
из тестового задания
    #39149535
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,

это действительно одна из задач тестового задания
объясните пожалуйста, как работать с вашей табличкой и как вы решали
...
Рейтинг: 0 / 0
18.01.2016, 12:50
| Ответить | Цитировать | Написать  
из тестового задания
    #39149536
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я еще пол-дня подумаю над пятёрками битов а потом загляну под ваш спойлер.
...
Рейтинг: 0 / 0
18.01.2016, 12:50
| Ответить | Цитировать | Написать  
из тестового задания
    #39149545
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabAleksandr Sharahov,

это действительно одна из задач тестового задания
объясните пожалуйста, как работать с вашей табличкой и как вы решали

В таком случае возникает вопрос относительно адекватности тестирующего.

С таблицей все просто. Каждая строка содержит:
в первой ячейке - исходное положение переключателей,
в остальных результирующее положение для каждого номера комнаты.

Как решал - чуть позже, а то другим будет неинтересно.
Ну или попробуйте отреверсить таблицу )
...
Рейтинг: 0 / 0
18.01.2016, 12:58
| Ответить | Цитировать | Написать  
из тестового задания
    #39149560
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr SharahovВ таком случае возникает вопрос относительно адекватности тестирующего.


почему?
...
Рейтинг: 0 / 0
18.01.2016, 13:13
| Ответить | Цитировать | Написать  
из тестового задания
    #39149562
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblab,

ну зачем там так много переключателей?
...
Рейтинг: 0 / 0
18.01.2016, 13:14
| Ответить | Цитировать | Написать  
из тестового задания
    #39149563
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Возможно это некая хеш-функция от 40-битного целого которая возвращает нам результат в диапазоне от 1 до 8.
...
Рейтинг: 0 / 0
18.01.2016, 13:14
| Ответить | Цитировать | Написать  
из тестового задания
    #39149572
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

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

С интересом глянул бы на 40-битное решение )
...
Рейтинг: 0 / 0
18.01.2016, 13:19
| Ответить | Цитировать | Написать  
из тестового задания
    #39149573
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahovmini.weblab,

ну зачем там так много переключателей?

просто в данной гостинице такая коммутационная доска
...
Рейтинг: 0 / 0
18.01.2016, 13:20
| Ответить | Цитировать | Написать  
из тестового задания
    #39149579
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabAleksandr Sharahovmini.weblab,

ну зачем там так много переключателей?

просто в данной гостинице такая коммутационная доска

Тогда возникает куда более интересная задача:
какой максимально возможный номер комнаты она позволяет закодировать?

Нормальный тестирующий должен понимать взаимную связь этих чисел.
...
Рейтинг: 0 / 0
18.01.2016, 13:26
| Ответить | Цитировать | Написать  
из тестового задания
    #39149593
jmp_original
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
jmp_original
Гость
Хм... мне в первом приближении мерещится, что для 8 комнат достаточно 11 переключателей. А 40 переключателей могут кодировать 34 комнаты. Для 32 комнат надо 37 тумблеров.
...
Рейтинг: 0 / 0
18.01.2016, 13:38
| Ответить | Цитировать | Написать  
из тестового задания
    #39149601
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov
Тогда возникает куда более интересная задача:
какой максимально возможный номер комнаты она позволяет закодировать?

Нормальный тестирующий должен понимать взаимную связь этих чисел.

какая связь между максимально возможным номером комнаты и нормальностью тестирующего?
очень спорная, тут вам будет сложно что либо доказать :)
...
Рейтинг: 0 / 0
18.01.2016, 13:43
| Ответить | Цитировать | Написать  
из тестового задания
    #39149606
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabAleksandr SharahovТогда возникает куда более интересная задача:
какой максимально возможный номер комнаты она позволяет закодировать?

Нормальный тестирующий должен понимать взаимную связь этих чисел.

какая связь между максимально возможным номером комнаты и нормальностью тестирующего?
очень спорная, тут вам будет сложно что либо доказать :)

Допустим, вам надо переместиться в соседнюю комнату.
В вашем распоряжении самолет, пароход, автомобиль, собственные ноги.
Каким средством передвижения воспользуетесь?
Утрировано, конечно, но суть отражает.
...
Рейтинг: 0 / 0
18.01.2016, 13:49
| Ответить | Цитировать | Написать  
из тестового задания
    #39149688
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,
неочевидно.
немного изменим задачу
Допустим, вам надо переместиться в соседнюю комнату.
В вашем распоряжении самолет, пароход, автомобиль, собственные ноги.
Клиент оплатит все дорожные расходы. Каким средством передвижения воспользуетесь?
Сколько времени займет перемещение?
Утрировано, конечно, но тоже суть отражает.
...
Рейтинг: 0 / 0
18.01.2016, 14:33
| Ответить | Цитировать | Написать  
из тестового задания
    #39149689
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
Попробую предложить.
Каждый выключатель во включенном состоянии имеет свой вес: 1,2,3...40;
если выключен: вес равен 0.
Остаток от деления суммы весов переключателей на 8 и будет искомая комната.
Полагаю, достаточно будет включить или выключить 1 из переключателей, чтобы условие выполнилось.
...
Рейтинг: 0 / 0
18.01.2016, 14:33
| Ответить | Цитировать | Написать  
из тестового задания
    #39149723
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
hclubmk,
просто и со вкусом
=)
...
Рейтинг: 0 / 0
18.01.2016, 14:50
| Ответить | Цитировать | Написать  
из тестового задания
    #39149748
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
hclubmkПопробую предложить.
Каждый выключатель во включенном состоянии имеет свой вес: 1,2,3...40;
если выключен: вес равен 0.
Остаток от деления суммы весов переключателей на 8 и будет искомая комната.
Полагаю, достаточно будет включить или выключить 1 из переключателей, чтобы условие выполнилось.

пусть включены следующие выключатели

[3, 4, 11, 19, 27, 35]
...
Рейтинг: 0 / 0
18.01.2016, 15:08
| Ответить | Цитировать | Написать  
из тестового задания
    #39149749
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
hclubmkПопробую предложить.
Каждый выключатель во включенном состоянии имеет свой вес: 1,2,3...40;
если выключен: вес равен 0.
Остаток от деления суммы весов переключателей на 8 и будет искомая комната.
Полагаю, достаточно будет включить или выключить 1 из переключателей, чтобы условие выполнилось.

пусть включены следующие выключатели
[3, 4, 11, 19, 27, 35]

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

ваши действия?
...
Рейтинг: 0 / 0
18.01.2016, 15:10
| Ответить | Цитировать | Написать  
из тестового задания
    #39149764
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
mini.weblab,
очевидно: включить 37
...
Рейтинг: 0 / 0
18.01.2016, 15:20
| Ответить | Цитировать | Написать  
из тестового задания
    #39149767
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
Отбой
...
Рейтинг: 0 / 0
18.01.2016, 15:27
| Ответить | Цитировать | Написать  
из тестового задания
    #39149799
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
hclubmk,

sum( [3, 4, 11, 19, 27, 35, 37] ) = 136
136 % 8 = 0
0: соответствует комнате номер 8
...
Рейтинг: 0 / 0
18.01.2016, 15:50
| Ответить | Цитировать | Написать  
из тестового задания
    #39149802
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
mini.weblabвключены следующие выключатели
[3, 4, 11, 19, 27, 35]

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

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

Значимыми считаем первые 7 тумблеров. Остальные игнорируем.
Текущая сумма 3+4=7. Требуется получить сумму, которая при делении на 8 даст в остатке 6. Ближайшие такие суммы - 6 и 14. 6 получить одним переключением нельзя. 14 - можно (3+4+7).
Наши действия - включить тумблер 7.
...
Рейтинг: 0 / 0
18.01.2016, 15:52
| Ответить | Цитировать | Написать  
из тестового задания
    #39149824
Apoj_sql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Apoj_sql
Участник
mini.weblabhclubmkПопробую предложить.
Каждый выключатель во включенном состоянии имеет свой вес: 1,2,3...40;
если выключен: вес равен 0.
Остаток от деления суммы весов переключателей на 8 и будет искомая комната.
Полагаю, достаточно будет включить или выключить 1 из переключателей, чтобы условие выполнилось.

пусть включены следующие выключатели
[3, 4, 11, 19, 27, 35]

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

ваши действия?
Предлагаю слегка модифициривать алгоритм: брать не по модулю 8, а по модулю 9 (чтоб 40 нацело не делился на модуль). Ну и результататы, к примеру 0 и 8 считать равными
Ну и соответственно изменять переключатель так, чтобы верной была сумма по модулю:

let test = [3;4;11;19;27;35];;
(List.fold Acc 0 test)%9;;
> val it : int = 0

let test = [3;4;6;11;19;27;35];;
(List.fold Acc 0 test)%9;;

> val it : int = 6
...
Рейтинг: 0 / 0
18.01.2016, 16:01
| Ответить | Цитировать | Написать  
из тестового задания
    #39149853
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Akina,
текущая конфигурация
[3, 4, 11, 19, 27, 35]

если использовать алгоритм hclubmk и включить выключатель 7, то в сумме получим 106
106 % 8 = 2, что соответствует комнате номер 2

если ваш алгоритм отличается (пусть незначительно), то опишите его,
и тогда подумаем над новой конфигурацией и действиями
...
Рейтинг: 0 / 0
18.01.2016, 16:18
| Ответить | Цитировать | Написать  
из тестового задания
    #39149854
Apoj_sql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Apoj_sql
Участник
соотвественно, когда мы делаем аналогичную подставу с mod 9

let Acc acc i = acc + i;;
let test = [3;5;12;21;30;39];;
(List.fold Acc 0 test)%9;;

оно отрабатывает корректно

let Acc acc i = acc + i;;
let test = [3;5;12;13 ;21;30;39];;
(List.fold Acc 0 test)%9;;
...
Рейтинг: 0 / 0
18.01.2016, 16:19
| Ответить | Цитировать | Написать  
из тестового задания
    #39149858
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Apoj_sql,

я подумаю, где-то вечером отпишусь
...
Рейтинг: 0 / 0
18.01.2016, 16:22
| Ответить | Цитировать | Написать  
из тестового задания
    #39149892
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
mini.weblabесли ваш алгоритм отличается (пусть незначительно), то опишите его,
Не отличается по сути, отличается в деталях. Все отличия описаны в решении.
...
Рейтинг: 0 / 0
18.01.2016, 16:38
| Ответить | Цитировать | Написать  
из тестового задания
    #39149906
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Akina,

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

Можете доказать?
...
Рейтинг: 0 / 0
18.01.2016, 16:45
| Ответить | Цитировать | Написать  
из тестового задания
    #39149921
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
AkinaЗначимыми считаем первые 7 тумблеров. Остальные игнорируем. Боюсь, при раскладке [4,5,6,7] комнату 4 при ограниченности в первые 7 тумблеров, указать не получится, увы. 7 тумблеров - это минимально-необходимое, но недостаточное условие.
...
Рейтинг: 0 / 0
18.01.2016, 16:54
| Ответить | Цитировать | Написать  
из тестового задания
    #39149928
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
hclubmkпри раскладке [4,5,6,7] комнату 4 при ограниченности в первые 7 тумблеров, указать не получится
Верно. Это относится к любому случаю, когда бинарная чётность комнаты и текущей суммы равны, но текущая сумма не равна нужной комнате.
Думаю, этих соображений достаточно, чтобы сформулировать решение... если нет - попробуйте построить все возможные варианты для произвольной текущей суммы на числовой прямой.
...
Рейтинг: 0 / 0
18.01.2016, 17:04
| Ответить | Цитировать | Написать  
из тестового задания
    #39149929
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
PS. У меня получается, что потребуется задействовать 8 тумблеров.
...
Рейтинг: 0 / 0
18.01.2016, 17:05
| Ответить | Цитировать | Написать  
из тестового задания
    #39149950
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
Akina,
я не постесняюсь задать вопрос, аналогично заданного мне mini.weblab, при неизменности алгоритма и ограниченности 8-ю тумблерами:

пусть включены следующие выключатели
[4,5,6,7]

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

ваши действия?
...
Рейтинг: 0 / 0
18.01.2016, 17:32
| Ответить | Цитировать | Написать  
из тестового задания
    #39149960
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
hclubmkпри неизменности алгоритма и ограниченности 8-ю тумблерами
Когда нарисуешь, поймёшь, что алгоритм нужно доработать... ибо все точки, если выбросить исходную, отличаются на 2, а не на 1. Кстати, это не только укажет на то, что нужно 8 тумблеров, но и то, что можно модифицировать исходное условие и ввести дополнительное (хотя оно и излишнее) требование, что один тумблер перещёлкивается обязательно.
...
Рейтинг: 0 / 0
18.01.2016, 17:39
| Ответить | Цитировать | Написать  
из тестового задания
    #39149962
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Ну и соответственно делить надо на 16, а не на 8...
...
Рейтинг: 0 / 0
18.01.2016, 17:40
| Ответить | Цитировать | Написать  
из тестового задания
    #39149969
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
Так что я должен понять? Что алгоритм нужно доработать? Это мне понятно. Я пытался понять ход твоего решения, и исходя из частного (приведенного) случая, узнать число. Ну да ладно.
...
Рейтинг: 0 / 0
18.01.2016, 17:51
| Ответить | Цитировать | Написать  
из тестового задания
    #39149974
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Akina и hclubmk,

Кто-нибудь из вас может ответить на 18696977 ?
...
Рейтинг: 0 / 0
18.01.2016, 17:55
| Ответить | Цитировать | Написать  
из тестового задания
    #39149977
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
AkinaЗначимыми считаем первые 7 тумблеров. Остальные игнорируем.
Текущая сумма 3+4=7. Требуется получить сумму, которая при делении на 8 даст в остатке 6. Ближайшие такие суммы - 6 и 14. 6 получить одним переключением нельзя. 14 - можно (3+4+7).
Наши действия - включить тумблер 7.
Все выключены, надо задать комнату 8
Включен 1-й, надо задать комнату 2
...
Рейтинг: 0 / 0
18.01.2016, 18:01
| Ответить | Цитировать | Написать  
из тестового задания
    #39149991
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ХЗ как решать, но я проверялку написал
 
Исходник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
#include <stdio.h>

// Количество переключателей
#define SWITCH_COUNT 30

// выключатели
bool arr[SWITCH_COUNT + 1] = { 0 };

// Алгоритм проверки, возвращает номер комнаты
int algo() {
	int sum = 0;
	for (int i = 1; i <= SWITCH_COUNT; i++) {
		if (arr[i]) sum = sum + i;
	}
	return sum % 11;
}

// Проверка текущей комбинации в arr, возврашает true если возможны все варианты 1 ... 8
bool check() {
	bool res[9] = { 0 };
	int fill = 0;
	// текущее значение массива
	int x = algo();
	if(x >= 1 && x <= 8) {
		res[x] = true;
		fill++;
	}
	// Переключаем все по одному
	for (int i = 1; i <= SWITCH_COUNT; i++) {
		arr[i] = !arr[i];
		x = algo();
		arr[i] = !arr[i];
		if (x >= 1 && x <= 8 && !res[x]) {
			res[x] = true;
			fill++;
			if (fill == 8) break;
		}
	}
	if(fill == 8) {
		return true;
	} else {
		printf("\nAbsent:");
		for (int i = 1; i <= 8; i++) {
			if (!res[i]) printf(" %d", i);
		}
		return false;
	}
}

void test() {
	int max = 0;
	// Перебор всех вариантов
	while(check()) {
		int i = 1;
		for (; i <= SWITCH_COUNT; i++) {
			if(arr[i]) {
				arr[i] = false;
			} else {
				arr[i] = true;
				if(i > max) {
					max = i;
					printf("test: %d switch\n", max);
				}
				break;
			}
		}
		if(i > SWITCH_COUNT) {
			printf("WIN\n");
			break;
		}
	}
	printf("\nSwitch on:");
	for (int i = 1; i <= SWITCH_COUNT; i++) {
		if (arr[i]) printf(" %d", i);
	}
	printf("\n");
}


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

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

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

Формула SUM % N не работает при N от 9 до 13, дальше не тестил.
...
Рейтинг: 0 / 0
18.01.2016, 18:13
| Ответить | Цитировать | Написать  
из тестового задания
    #39150046
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Думаю надо для начала задачу упростить:
Две комнаты кодируются одним выключателем.
Три уже проблема. Надо сначала решать с 3 комнатами. Или с 4 (т.к. степень двойки как и 8). Затем тот же алгоритм применить на 8.

 
Для 3-х у меня уже ничего не придумывается
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
#include <stdio.h>

// Количество переключателей
#define SWITCH_COUNT 25

// Количество комнат
#define ROOM_COUNT 3

// выключатели
bool arr[SWITCH_COUNT + 1] = { 0 };

// Алгоритм проверки, возвращает номер комнаты
int algo() {
	int sum = 0;
	for (int i = 1; i <= SWITCH_COUNT; i++) {
		if (arr[i]) sum = sum + i;
	}
	return sum % 4;
}

// Проверка текущей комбинации в arr, возврашает true если возможны все варианты 1 ... 8
bool check() {
	bool res[ROOM_COUNT + 1] = { 0 };
	int fill = 0;
	// текущее значение массива
	int x = algo();
	if(x >= 1 && x <= ROOM_COUNT) {
		res[x] = true;
		fill++;
	}
	// Переключаем все по одному
	for (int i = 1; i <= SWITCH_COUNT; i++) {
		arr[i] = !arr[i];
		x = algo();
		arr[i] = !arr[i];
		if (x >= 1 && x <= ROOM_COUNT && !res[x]) {
			res[x] = true;
			fill++;
			if (fill == ROOM_COUNT) break;
		}
	}
	if(fill == ROOM_COUNT) {
		return true;
	} else {
		// Список номеров комнат, которые невозможно получить
		printf("\nAbsent:");
		for (int i = 1; i <= ROOM_COUNT; i++) {
			if (!res[i]) printf(" %d", i);
		}
		return false;
	}
}

void test() {
	int max = 0;
	// Перебор всех вариантов
	bool win = true;
	while(1) {
		if(!check()) {
			win = false;
			break;
		}
		int i = 1;
		for (; i <= SWITCH_COUNT; i++) {
			if(arr[i]) {
				arr[i] = false;
			} else {
				arr[i] = true;
				if(i > max) {
					max = i;
					printf("test: %d switch\n", max);
				}
				break;
			}
		}
	}
	if (win) {
		printf("WIN\n");
	} else {
		// Список включенных выключателей
		printf("\nSwitch on:");
		for (int i = 1; i <= SWITCH_COUNT; i++) {
			if (arr[i]) printf(" %d", i);
		}
		printf("\n");
	}
}


Если кто будет запускать: добавил кол-во комнат (ROOM_COUNT)

PS Aleksandr Sharahov, заглянул под спойлер, понятнее не стало.

PPS Это какая-то олимпиадная задачка.
...
Рейтинг: 0 / 0
18.01.2016, 19:26
| Ответить | Цитировать | Написать  
из тестового задания
    #39150048
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

на самом деле это чрезвычайно простая задача,
даже и не задача вовсе,
просто необыкновенно сильно сбивает с толку )
...
Рейтинг: 0 / 0
18.01.2016, 19:34
| Ответить | Цитировать | Написать  
из тестового задания
    #39150058
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima T,

на самом деле это чрезвычайно простая задача,
даже и не задача вовсе,
просто необыкновенно сильно сбивает с толку )
Сбивает непрактичность, т.е. никогда-нигде подобное не требовалось в реале. Мозг закостенел от практики, может утром на свежую голову что-то озарит.
...
Рейтинг: 0 / 0
18.01.2016, 19:44
| Ответить | Цитировать | Написать  
из тестового задания
    #39150083
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TPS Aleksandr Sharahov, заглянул под спойлер, понятнее не стало.

PPS Это какая-то олимпиадная задачка.
Дима +1

Тоже заглянул под спойлер. Я не понял как была получена таблица и как решать эту задачу.

Есть подозрения что условия избыточные (есть отвлекающие н ненужные сведения) или
я просто решаю задачу слишком сложно.
...
Рейтинг: 0 / 0
18.01.2016, 20:06
| Ответить | Цитировать | Написать  
из тестового задания
    #39150095
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonили я просто решаю задачу слишком сложно.
Ты (и я) решаем ее по инерции, по привычке, по классическим алгоритмам. А тут алгоритм из серии "оторви и выбрось", он ненужный, никогда в жизни не пригодиться. Я уже писал что помню что попадалась подобная задача с решением, но даже задумываться не стал из-за отсутствия практического применения алгоритма.
...
Рейтинг: 0 / 0
18.01.2016, 20:19
| Ответить | Цитировать | Написать  
из тестового задания
    #39150103
Apoj_sql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Apoj_sql
Участник
Dima TХЗ как решать, но я проверялку написал

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

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

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

Формула SUM % N не работает при N от 9 до 13, дальше не тестил.
Ещё бы написали алгоритм проверки алгоритма проверки. Было ж указано, что при mod 9 8 и 0 одно и то же. У Вас я это не увидел при проверке.
ЗЫ Мне уныло лезть в c++:
0) надо ставить к студии с++
1) я "туда" лез последний раз 6 месяцев назад (надо было решать тестовое задание для моего нонешнего работодателя)
2) удовольствия при п.1 не получил и лезть туда без особой нужды нет ни малейшего желания.
...
Рейтинг: 0 / 0
18.01.2016, 20:32
| Ответить | Цитировать | Написать  
из тестового задания
    #39150127
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmaytonили я просто решаю задачу слишком сложно.
Ты (и я) решаем ее по инерции, по привычке, по классическим алгоритмам. А тут алгоритм из серии "оторви и выбрось", он ненужный, никогда в жизни не пригодиться. Я уже писал что помню что попадалась подобная задача с решением, но даже задумываться не стал из-за отсутствия практического применения алгоритма.
Ну даже если перевести ее в плоскость чистой математики.

Вам на вход подали целое число. Вам разрешено а нему прибавить или вычесть 2^N (инвертировать любой битик) таким
образом чтобы получить число которое дешифровав таблично или через функцию
получить от 1 до 8.

Честно. Я не знаю. Для меня - это пока задача больше на интерпретацию смыслов.

Мне почему-то она напоминает "бесконечный поезд в космосе" или "самолёт взлетающий
с транспортёра". И проблема их не в том что они не решаются а в том что их условие с дефектом
или неполное.
...
Рейтинг: 0 / 0
18.01.2016, 21:12
| Ответить | Цитировать | Написать  
из тестового задания
    #39150134
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

думал, что только меня одного так поначалу смутили условия,
ну тогда точно задача стоит заметки в бложике )
...
Рейтинг: 0 / 0
18.01.2016, 21:24
| Ответить | Цитировать | Написать  
из тестового задания
    #39150136
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
maytonИ проблема их не в том что они не решаются а в том что их условие с дефектом
или неполное.

а вот это уже нужно доказывать :)
...
Рейтинг: 0 / 0
18.01.2016, 21:29
| Ответить | Цитировать | Написать  
из тестового задания
    #39150138
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,
объясните, пожалуйста, как пользоваться вашей табличкой
=)
...
Рейтинг: 0 / 0
18.01.2016, 21:34
| Ответить | Цитировать | Написать  
из тестового задания
    #39150140
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabAleksandr Sharahov,
объясните, пожалуйста, как пользоваться вашей табличкой
=)

Закодировать:
1. найти строку с номером, равным текущему состоянию выключателей, например, 42 (или 0101010 в двоичной системе).
2. найти столбец, соответствующий номеру комнаты (в диапазоне 0..7, ты ж программист).
3. новое состояние выключателей установить равным содержимому ячейки на пересечении найденных строки и столбца.

Раскодировать:
1. найти в таблице любую ячейку, содержащую наблюдаемое положение переключателей.
2. определить номер комнаты, соответствующий столбцу найденной ячейки.
...
Рейтинг: 0 / 0
18.01.2016, 21:52
| Ответить | Цитировать | Написать  
из тестового задания
    #39150142
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,
попробую :)
Спасибо!

ПС: я задачу решила методом чита, но засомневалась =)
...
Рейтинг: 0 / 0
18.01.2016, 22:01
| Ответить | Цитировать | Написать  
из тестового задания
    #39150158
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,
...
Рейтинг: 0 / 0
18.01.2016, 22:47
| Ответить | Цитировать | Написать  
из тестового задания
    #39150159
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,
еще вопрос
почему используете 7 переключателей и 8 комнат?
...
Рейтинг: 0 / 0
18.01.2016, 22:50
| Ответить | Цитировать | Написать  
из тестового задания
    #39150166
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblabПС: я задачу решила методом чита, но засомневалась =)
Что за метод чита?
...
Рейтинг: 0 / 0
18.01.2016, 23:05
| Ответить | Цитировать | Написать  
из тестового задания
    #39150170
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabAleksandr Sharahov,
еще вопрос
почему используете 7 переключателей и 8 комнат?

Потому, что для 8 комнат необходимо и достаточно 7 переключателей )

И вообще, для 2^N комнат требуется (2^N)-1 переключателей,
что как раз и доказывает, что ваш тестирующий не в ладах с двоичной системой )
...
Рейтинг: 0 / 0
18.01.2016, 23:24
| Ответить | Цитировать | Написать  
из тестового задания
    #39150186
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,

а ссылку на результат можно?
кстати еще момент, по условию вы жили в одной из комнат, и по идее эту комнату можно было бы исключить

mayton,

для шифровки используем первые 3 ячейки.
если наш агент приходит в гостиницу и комната для него заказана, используем колонку Room booked
если наш агент приходит в гостиницу и комната для него предварительно не заказана,
используем колонку Room not booked
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
---------------------------------------------
|Room Number | Room booked | Room not booked|
---------------------------------------------
|Room 1	     |000          |111             |
---------------------------------------------
|Room 2	     |001          |110             |
---------------------------------------------
|Room 3      |010	   |101             |
---------------------------------------------
|Room 4	     |011	   |100             |
---------------------------------------------
|Room 5      |100          |011             |
---------------------------------------------
|Room 6      |101	   |010             |
---------------------------------------------
|Room 7      |110          |001             |
---------------------------------------------
|Room 8      |111          |000             |
---------------------------------------------

PS: в крайнем случае используем жвачку
...
Рейтинг: 0 / 0
19.01.2016, 00:21
| Ответить | Цитировать | Написать  
из тестового задания
    #39150188
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabAleksandr Sharahov,

а ссылку на результат можно?
кстати еще момент, по условию вы жили в одной из комнат, и по идее эту комнату можно было бы исключить



Ссылку дам, как только напишу заметку в бложик.
По идее в той комнате, где я жил, мог жить не только я.

А условия можно очистить от шелухи, например:

Компьютер генерирует 2 случайных числа: первое - в диапазоне 0..7, второе - в диапазоне 0..127.
Необходимо сначала закодировать первое число, а затем по коду восстановить его.
В качестве кодов разрешается использовать числа из диапазона 0..127,
которые отличаются от второго случайного числа не более чем одним битом.
...
Рейтинг: 0 / 0
19.01.2016, 00:29
| Ответить | Цитировать | Написать  
из тестового задания
    #39150193
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kolobok0
Участник
Aleksandr Sharahov...Потому, что для 8 комнат необходимо и достаточно 7 переключателей )
И вообще, для 2^N комнат требуется (2^N)-1 переключателей,...

тут больше комбинаторика кмк. хз.
но для
3 комнат достаточно 2 бита
4 комнат достаточно 3 бита
и т.д..
так что формула не работает. либо не так написали Вы её.

Но ответ похоже правильный во втором топике Вы написали - 7 бит достаточно.

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

в каком именно случае (при каком N) формула не работает?

Замечание. 2^N означает 2 в степени N.
...
Рейтинг: 0 / 0
19.01.2016, 00:48
| Ответить | Цитировать | Написать  
из тестового задания
    #39150200
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kolobok0
Участник
Aleksandr Sharahovв каком именно случае (при каком N) формула не работает?
...

вообще-то и формулу у Вас не вижу...
опишите где и что Вы подразумеваете?

закономерность которую вижу сам:
N = K - 1
где
K = комнаты
N = переключатели.
...
Рейтинг: 0 / 0
19.01.2016, 01:03
| Ответить | Цитировать | Написать  
из тестового задания
    #39150205
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
kolobok0Aleksandr Sharahovв каком именно случае (при каком N) формула не работает?
...

вообще-то и формулу у Вас не вижу...
опишите где и что Вы подразумеваете?

закономерность которую вижу сам:
N = K - 1
где
K = комнаты
N = переключатели.

Если не видите, тогда почему утверждаете, что моя формула не работает или я не так ее написал? )
Что, где, когда: 18698883 .
...
Рейтинг: 0 / 0
19.01.2016, 01:12
| Ответить | Цитировать | Написать  
из тестового задания
    #39150209
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kolobok0
Участник
Aleksandr Sharahov...И вообще, для 2^N комнат требуется (2^N)-1 переключателей...

окейно...
Если
N - это комнаты...
то тогда для 3 комнат:
2 в степени 3 = 8.
8 - 1 = 7 переключателей (что является избыточно).

Если
2 в степени N = комнаты...
То тогда записав выражение
комнаты - 1 = переключатели.

отсюда моё замешательство, отсюда и задал вопрос = что Вы имели ввиду...
...
Рейтинг: 0 / 0
19.01.2016, 01:26
| Ответить | Цитировать | Написать  
из тестового задания
    #39150214
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
kolobok0Aleksandr Sharahov...И вообще, для 2^N комнат требуется (2^N)-1 переключателей...

окейно...
Если
N - это комнаты...
то тогда для 3 комнат:
2 в степени 3 = 8.
8 - 1 = 7 переключателей (что является избыточно).

Если
2 в степени N = комнаты...
То тогда записав выражение
комнаты - 1 = переключатели.

отсюда моё замешательство, отсюда и задал вопрос = что Вы имели ввиду...

Как вы понимаете, в своих рассуждениях,
которые были опубликованы несколько раньше введенных вами обозначений,
я вовсе не был обязан придерживаться ваших обозначений.

В публикациях на (около)математические темы,
если не оговорено противное,
N обычно означает произвольное натуральное число,
а не комнаты, переключатели и т.п.
...
Рейтинг: 0 / 0
19.01.2016, 01:41
| Ответить | Цитировать | Написать  
из тестового задания
    #39150216
MrCat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MrCat
Гость
Подкину вариант.

1) Берём первые три выключателя и называем их "зерно" - S, оно останется неизменным. Берём следующие 7 штук и называем их "маска" - M, одним из них чуть позже щёлкнем. Номер комнаты назовём R.
2) Для i = 1..7: если M[i] включён, то запоминаем новое значение зерна: S = S xor i, полученное преобразованное зерно назовём S*.
3) Щёлкаем переключателем маски номер (S* xor R) (если S* = R, то щёлкать не надо).
Котово! Агент-сменщик повторяет шаги 1 и 2, и получает S* - искомый номер комнаты.

например:
1) пусть S = 010, M = 0010001, R =5.

2) 010 xor 011 = 001
001 xor 111 = 110

3)5 xor 110 = 101 xor 110 = 011 = 3, щёлкаем третьим выключателем.

Приходит сменщик:
1)S = 010, M = 0000001
2)010 xor 111 = 101 = 5.
...
Рейтинг: 0 / 0
19.01.2016, 01:50
| Ответить | Цитировать | Написать  
из тестового задания
    #39150218
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kolobok0
Участник
Aleksandr Sharahov...
В публикациях на (около)математические темы...

определение выражения типа "формула" из вики:

формула — всякая чисто символьная запись

где в дальнейшем идёт расшифровка этих самых символов.
Простите - так привык с того века. Наверное это мои замороты - хз.
В конечном итоге то, что Вы написали вызвало больше вопросов, чем ответов(у меня лично). Чтоб не гадать - я задал Вам вопрос.
На который кстати Вы не ответили (по поводу уточнить Ваше высказывание).

Если Вы пытались записать выражение типа

N = K - 1
где
K = комнаты
N = переключатели.

то нафига степени двоек впрягли? Чтоб типа поболее символов? :)

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


Нет, не для этого.

А для того, чтобы записать утверждение в общем виде для произвольного натурального параметра N.
Дело в том, что я могу доказать справедливость приведенного утверждения лишь
для количества комнат, равного натуральной степени двойки.

Если вы можете доказать нечто подобное для произвольного количества комнат,
то вам, конечно, не за чем "впрягать степени двоек". )
...
Рейтинг: 0 / 0
19.01.2016, 02:08
| Ответить | Цитировать | Написать  
из тестового задания
    #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
| Ответить | Цитировать | Написать  
из тестового задания
    #39150732
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahovmini.weblabAleksandr Sharahov,

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

По фэншую 2 сообщения kealon(Ruslan): 18700090 и 18700779
практически полностью и составляют решение.
Т.е. суть задачи состоит в перечислении всех подмножеств множества из N=3 битов.
Всего их (вспоминаем сумму биномиальных коэффициентов) 2^N=8.
Перейти от одного подмножества к другому можно
за одну операцию объединение или разности (в нашем случае xor).
Для каждого отдельного бита все эти xor'ы выродятся в те самые суммы.
На подмножества можно смотреть как на функции перехода xor'ом от одного значения к другому.
-1 появляется от того, что тождественная функция нам не нужна.

переформулирую, допустим, для беглого ознакомления с вопросом, что гуглить?
основы криптографии? что-нибудь по основам CS? что?
...
Рейтинг: 0 / 0
19.01.2016, 15:36
| Ответить | Цитировать | Написать  
из тестового задания
    #39150735
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabkealon(Ruslan),

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

ПС:
честно говоря, пока не увидела решение Александра, даже в голову не пришло посмотреть на задачу именно в таком ключе
:)

Вы неявно предполагаете, что такая таблица существует для любого количества переключателей.
На самом деле это не доказано и опираться на это нельзя.
Пока лишь доказано, что таблица существует для (2^N)-1 переключателей, где N - любое натуральное.
...
Рейтинг: 0 / 0
19.01.2016, 15:37
| Ответить | Цитировать | Написать  
из тестового задания
    #39150738
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,


хм.., т.е. если у вам будет 3 переключателя, то задачу с 4 комнатами вы не решите?
...
Рейтинг: 0 / 0
19.01.2016, 15:43
| Ответить | Цитировать | Написать  
из тестового задания
    #39150744
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mini.weblabAleksandr Sharahov,
хм.., т.е. если у вам будет 3 переключателя, то задачу с 4 комнатами вы не решите?
правильно будет так:

если у вас будет 4 переключателя, то задачу с 5 комнатами вы не решите?
...
Рейтинг: 0 / 0
19.01.2016, 15:46
| Ответить | Цитировать | Написать  
из тестового задания
    #39150748
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabпереформулирую, допустим, для беглого ознакомления с вопросом, что гуглить?
основы криптографии? что-нибудь по основам CS? что?

Достаточно общих знаний по:
теории множеств (операции, включения-исключения),
двоичной системе (биты, xor),
комбинаторике (биномиальные коэффициенты, основное тождество).

Чтобы досконально разобраться попробуйте по-честному
построить все функции перехода для N=4 бит номера комнаты через xor.
Это не так трудно, поверьте.
...
Рейтинг: 0 / 0
19.01.2016, 15:52
| Ответить | Цитировать | Написать  
из тестового задания
    #39150750
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov,

Спасибо, вы дали отличную подсказку, думаю, теперь я смогу разрулить задачу :)
...
Рейтинг: 0 / 0
19.01.2016, 15:52
| Ответить | Цитировать | Написать  
из тестового задания
    #39150753
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabmini.weblabAleksandr Sharahov,
хм.., т.е. если у вам будет 3 переключателя, то задачу с 4 комнатами вы не решите?
правильно будет так:

если у вас будет 4 переключателя, то задачу с 5 комнатами вы не решите?

Не знаю, но почти уверен, что 6-ти переключателей на 7 комнат не хватит.
...
Рейтинг: 0 / 0
19.01.2016, 15:56
| Ответить | Цитировать | Написать  
из тестового задания
    #39150779
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr Sharahovmini.weblabпропущено...

правильно будет так:

если у вас будет 4 переключателя, то задачу с 5 комнатами вы не решите?

Не знаю, но почти уверен, что 6-ти переключателей на 7 комнат не хватит.
ИМХУ Дверей для алгоритма может быть только 2^N, а не произвольное число. Т.к. алгоритм оперирует двоичными разрядами, т.е. ожидает N двоичных разрядов номера двери. Т.е. для 4х дверей надо 2 разряда (0 ... 3) для 5 дверей надо три разряда, поэтому уже 7 переключателей. Для 9 дверей надо 15 переключателей.
Т.е. если надо 5 дверей, то кодировать все равно 8 дверей, а использовать только первые 5.
...
Рейтинг: 0 / 0
19.01.2016, 16:19
| Ответить | Цитировать | Написать  
из тестового задания
    #39150947
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
да чего там, для 3 дверей уже 2х переключателей не хватит

теперь я не понимаю, как рассчитать достаточное количество переключателей
интересует ход мыслей, как это можно сделать (как получить формулу?)
посмотрела бы на доказательство результата, что привели Александр и Руслан
...
Рейтинг: 0 / 0
19.01.2016, 20:05
| Ответить | Цитировать | Написать  
из тестового задания
    #39150951
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mini.weblabда чего там, для 3 дверей уже 2х переключателей не хватит

теперь я не понимаю, как рассчитать достаточное количество переключателей
интересует ход мыслей, как это можно сделать (как получить формулу?)
посмотрела бы на доказательство результата, что привели Александр и Руслан
Тогда ложись спать. Я постом выше написал больше чем требуется для ответа на этот вопрос. Утром не поймешь - переспроси.
...
Рейтинг: 0 / 0
19.01.2016, 20:15
| Ответить | Цитировать | Написать  
из тестового задания
    #39150956
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dima T,
...
Рейтинг: 0 / 0
19.01.2016, 20:18
| Ответить | Цитировать | Написать  
из тестового задания
    #39150958
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dima T,

я неправильно сформулировала, я могу применить формулу и посчитать по ней нужное количество переключателей,
но я не понимаю, как выводится формула
...
Рейтинг: 0 / 0
19.01.2016, 20:22
| Ответить | Цитировать | Написать  
из тестового задания
    #39150964
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Переведи все в двоичную систему. 1 есть во всех строках, т.е. изменяя 1й выключатель мы получаем X ^= 0b111 т.е. инверсию всех битов. 2 есть в 1 и 3 строке, т.е. изменение 2 выключателя равносильно X ^= 0b101 и т.д.
...
Рейтинг: 0 / 0
19.01.2016, 20:40
| Ответить | Цитировать | Написать  
из тестового задания
    #39150967
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Тут есть еще засада с нумерацией: надо нумеровать с нуля, но по задаче нумеруется с 1, т.е. 5 дверей это с 1 по 5, а не с 0 по 4. Битовая математика работает с нуля, надо это учитывать.
...
Рейтинг: 0 / 0
19.01.2016, 20:43
| Ответить | Цитировать | Написать  
из тестового задания
    #39151006
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabDima T,

я неправильно сформулировала, я могу применить формулу и посчитать по ней нужное количество переключателей,
но я не понимаю, как выводится формула

Доказывается необходимость и достаточность.

Давайте сначала мы докажем в ту сторону, куда проще.
В нашем случае необходимость для 2^N дверей как минимум 2^N-1 переключателей. За одну операцию кодирования двери мы можем переключить только 1 переключатель или не переключать ни одного. Из некоторого исходного положения мы должны иметь возможность закодировать 2^N дверей различных дверей. Значит нужно иметь не менее 2^N-1 различных переключателей.

Теперь в обратную сторону, достаточность.
Мы просто укажем способ кодирования, который всегда позволяет от произвольного случайного значения кода перейти к одному из кодов любой заранее заданной двери (вы, разумеется, понимаете что каждая дверь может имеет несколько двоичных кодов, состоящих из 2^N-1 бит). Нам достаточно найти только один подходящий код.
Вот тут и есть то самое место, которое, как мне кажется, всех сбивает с толку. По счастливой случайности битов в нашем распоряжении ровно столько, сколько нужно чтобы закодировать все подмножества (за исключением пустого) множества из N битов. И мы так и поступим. Т.е. каждый бит у нас будет соответствовать некоторому подмножеству.
Таким образом, у нас будет свой кодирующий бит для каждого исходного бита множества, свой кодирующий бит для каждой пары исходных битов, для каждой тройки, ... и, наконец, кодирующий бит для всех N битов исходного множества. Это важно твердо понимать.
Теперь двинемся дальше. Попробуем понять, что означает некоторый двоичный код, который мы видим перед собой. Давайте посмотрим на все эти подмножества и соответствующие им биты кода как на операции, которые позволяют перейти от пустого множества к тому, которое кодирует эта операция. Но тогда весь код означает суперпозицию операций. С последовательностью применения закодированных операций не возникнет вопросов, если мы выберем XOR над элементами множества (теми самыми N битами). Важно понимать, что код также задает некоторое подмножество, полученное из пустого.
Опять же по счастливой случайности такое определение операции позволит нам изменением всего одного бита случайного кода в получить код, который в результате последовательного применения всех закодированных в нем операций в конце концов позволит получить любое заданное подмножество исходных N бит.
Понятно, что мы всегда сможем найти такой кодирующий бит, т.к. у нас есть свой бит для любого подмножества, в том числе и для подмножества, закодированного упомянутым случайным кодом и подмножеством, которое мы хотим получить.
Вот и все )
...
Рейтинг: 0 / 0
19.01.2016, 23:13
| Ответить | Цитировать | Написать  
из тестового задания
    #39151015
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Сорри, исправлю здесь же самые дикие опечатки:

Доказывается необходимость и достаточность.

Давайте сначала докажем в ту сторону, куда проще.
В нашем случае необходимость для 2^N дверей иметь как минимум 2^N-1 переключателей. За одну операцию кодирования двери мы можем переключить только 1 переключатель или не переключать ни одного. Из некоторого исходного положения мы должны иметь возможность закодировать 2^N различных дверей. Значит нужно иметь не менее 2^N-1 различных переключателей.

Теперь в обратную сторону, достаточность.
Мы просто укажем способ кодирования, который всегда позволяет от произвольного случайного значения кода перейти к одному из кодов любой заранее заданной двери (вы, разумеется, понимаете что каждая дверь имеет несколько двоичных кодов, состоящих из 2^N-1 бит). Нам достаточно найти только один подходящий код.

Вот тут и есть то самое место, которое, как мне кажется, всех сбивает с толку. По счастливой случайности битов в нашем распоряжении ровно столько, сколько нужно чтобы закодировать все подмножества (за исключением пустого) множества из N битов. И мы так и поступим. Т.е. каждый бит у нас будет соответствовать некоторому подмножеству.

Таким образом, у нас будет свой кодирующий бит для каждого исходного бита множества, свой кодирующий бит для каждой пары исходных битов, для каждой тройки, ... и, наконец, кодирующий бит для всех N битов исходного множества. Это важно твердо понимать.

Теперь двинемся дальше. Попробуем понять, что означает некоторый двоичный код, который мы видим перед собой. Давайте посмотрим на все эти подмножества и соответствующие им биты кода как на операции, которые позволяют перейти от пустого множества к тому, которое кодирует эта операция. Но тогда весь код означает суперпозицию операций. С последовательностью применения закодированных операций не возникнет вопросов, если мы выберем XOR над элементами множества (теми самыми N битами). Важно понимать, что код также задает некоторое подмножество, полученное из пустого.

Опять же по счастливой случайности такое определение операции позволит нам изменением всего одного бита случайного кода в получить код, который в результате последовательного применения всех закодированных в нем операций в конце концов позволит получить заданное подмножество исходных N бит.

Понятно, что мы всегда сможем найти такой кодирующий бит, т.к. у нас есть свой бит для любого подмножества, в том числе и для подмножества, полученного XOR'ом подмножества, закодированного упомянутым случайным кодом, и подмножества, которое мы хотим получить.
Вот и все )[/quot]
...
Рейтинг: 0 / 0
19.01.2016, 23:29
| Ответить | Цитировать | Написать  
из тестового задания
    #39151040
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahov, Dima T

Спасибо!
Более менее разобралась.

Меня смутили числа 2^N и 2^N - 1, и я долго думала, откуда они взялись и как их получить.
Насколько я поняла, нужно связывать побитовое инвертирование последовательности чисел
(допустим, от 1 до 8, как в задаче) и заданную кодировку (инвертирование 1 бита в ключе)

Определим ключ как последовательность значимых переключателей

я попробовала переформулировать задачу

Пусть имеются числа от 1 до n.
Требуется закодировать заданное число от 1 до n.
Метод кодировки: изменение одного бита в произвольно заданном ключе
Задача: Рассчитать необходимый и достаточный размер ключа
...
Рейтинг: 0 / 0
20.01.2016, 02:06
| Ответить | Цитировать | Написать  
из тестового задания
    #39151145
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabМеня смутили числа 2^N и 2^N - 1, и я долго думала, откуда они взялись и как их получить.
Насколько я поняла, нужно связывать побитовое инвертирование последовательности чисел
(допустим, от 1 до 8, как в задаче) и заданную кодировку (инвертирование 1 бита в ключе)


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

Второе из чисел - количество подмножеств множества из N элементов,
за исключением пустого подмножества. Оно нам не нужно,
т.к. с его помощью мы не будем задавать никаких операций,
ведь XOR с нулем не меняет числа. Тождественная операция у нас и так
всегда есть по условию - мы имеем право в качестве кода использовать
само исходное случайное значение.

Важно понимать, что инвертирование битов числа является следствием
операции XOR над множеством его битов. Именно поэтому проще всего
программа получится когда интервал возможных значений начинается с 0
и заканчиваться числом, в двоичной записи которого все биты равны 1.
В противном случае если вы хотите получить минимальную длину кода,
вам могут потребоваться дополнительные сдвиги диапазона,
чтобы попасть в указанный интервал.

mini.weblabОпределим ключ как последовательность значимых переключателей
Пусть имеются числа от 1 до n.
Требуется закодировать заданное число от 1 до n.
Метод кодировки: изменение одного бита в произвольно заданном ключе
Задача: Рассчитать необходимый и достаточный размер ключа

Это хороший повод поговорить по душам с тестирующим )
Плюс в том, что разговор может получиться длинным и своем поле.
Минус в том, что при этом его легко обидеть.
Ваши шансы возрастают, если разговор будет на троих )
...
Рейтинг: 0 / 0
20.01.2016, 09:59
| Ответить | Цитировать | Написать  
из тестового задания
    #39151162
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Aleksandr Sharahov, простите, но мне непонятно ваше доказательство, более того, я плохо понял что вы пытались доказать. Думаю что это связано с большим уровнем 'шума'. Не могли бы вы прокомментировать более подробно ваше доказательство, пожалуйста

mini.weblabAleksandr Sharahov, Dima T

Спасибо!
Более менее разобралась.


Вы уверены что понимаете как была построена таблица выше и почему она имеет право быть построенной так ?
...
Рейтинг: 0 / 0
20.01.2016, 10:13
| Ответить | Цитировать | Написать  
из тестового задания
    #39151169
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovПервое из чисел - количество подмножеств множества из N элементов.
Этим ты и запутал. Элементов не N а 2^N
Т.е. N это количество бит, которое необходимо чтобы пронуменовать все элементы. Если дверей 8 то N=3
...
Рейтинг: 0 / 0
20.01.2016, 10:16
| Ответить | Цитировать | Написать  
из тестового задания
    #39151200
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovПервое из чисел - количество подмножеств множества из N элементов.
Этим ты и запутал. Элементов не N а 2^N
Т.е. N это количество бит, которое необходимо чтобы пронуменовать все элементы. Если дверей 8 то N=3

Просьба не навязывать мне свои обозначения.
Можете считать, что мне лень в них вникать.

В моем тексте используются мои обозначения.
Хотите критиковать меня - пожалуйста, но используйте при этом мои обозначения.
...
Рейтинг: 0 / 0
20.01.2016, 10:44
| Ответить | Цитировать | Написать  
из тестового задания
    #39151202
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

см. 18704296 , где написано

Первое из чисел - количество подмножеств множества из N элементов.
В нашем случае элементами являются отдельные биты некоторого числа.
В нашем случае некоторым числом является номер комнаты.
...
Рейтинг: 0 / 0
20.01.2016, 10:48
| Ответить | Цитировать | Написать  
из тестового задания
    #39151205
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovПросьба не навязывать мне свои обозначения.
Можете считать, что мне лень в них вникать.
Ну так будь добр заранее об этом сообщать. Иначе это выглядит как бред
Aleksandr Sharahovmini.weblabМеня смутили числа 2^N и 2^N - 1 , и я долго думала, откуда они взялись ...

Первое из чисел - количество подмножеств множества из N элементов ...
о чем я и написал.
...
Рейтинг: 0 / 0
20.01.2016, 10:50
| Ответить | Цитировать | Написать  
из тестового задания
    #39151216
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima Tпропущено...

Этим ты и запутал. Элементов не N а 2^N
Т.е. N это количество бит, которое необходимо чтобы пронуменовать все элементы. Если дверей 8 то N=3
Просьба не навязывать мне свои обозначения.
Можете считать, что мне лень в них вникать.
Это я больше для mini.weblab писал, на это
mini.weblabМеня смутили числа 2^N и 2^N - 1, и я долго думала, откуда они взялись и как их получить.
Предположил что именно могло ее запутать. Возможно ошибся.

А твои доказательства целиком не читал, много букав.
...
Рейтинг: 0 / 0
20.01.2016, 10:58
| Ответить | Цитировать | Написать  
из тестового задания
    #39151270
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SashaMercuryAleksandr Sharahov, простите, но мне непонятно ваше доказательство, более того, я плохо понял что вы пытались доказать.


Доказывается необходимость и достаточность 2^N-1 переключателей для 2^N дверей.
Какое место в доказательстве непонятно?
...
Рейтинг: 0 / 0
20.01.2016, 11:44
| Ответить | Цитировать | Написать  
из тестового задания
    #39151440
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Изломал всю голову "простым" решением 18700090 от kealon(Ruslan), точнее тем как его объяснить. Как работает - понятно. Не мог придумать как назвать его таблицу, в итоге получилось как всегда - раз нельзя назвать, значит что-то не так.

Тотже алгоритм:
для шифрования: берем номер двери и делаем xor всех номеров включенных переключателей. Получаем номер того который надо переключить.
для дешифрования: xor всех включенных переключателей.

Например: включены переключатели 3,7. Надо указать на 6 дверь.
6 ^ 3 ^ 7 = 2-й переключатель надо переключить
2 ^ 3 ^ 7 = 6-я дверь

Требуемое количество переключателей : должны быть все переключатели используемого битового диапазона, т.к. в результате xor может получиться больше, например 4^3 = 7, т.е. если используется 3 бита, то надо все до 2^3 (=8), т.е. от 1 до 7, ноль не надо т.к. X ^ 0 = X, поэтому всего 2^N - 1, где N количество используемых бит.

Для 8 дверей хватит 3 бит (7 переключателей) если двери нумеровать с нуля, а не с 1. Иначе надо 15 переключателей.
...
Рейтинг: 0 / 0
20.01.2016, 13:59
| Ответить | Цитировать | Написать  
из тестового задания
    #39151462
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TИзломал всю голову "простым" решением 18700090 от kealon(Ruslan), точнее тем как его объяснить.


В 18703610 , не просто доказывается достаточность,
но еще и конструируется алгоритм, основанный на манипуляциях с подмножествами.

А алгоритм 18700090 - это как бы срез (следствие) общего алгоритма
применительно к отдельным битам.
...
Рейтинг: 0 / 0
20.01.2016, 14:10
| Ответить | Цитировать | Написать  
из тестового задания
    #39151614
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
SashaMercury,

как я понимаю (заранее прошу прощение за терминологию)
1)
если взять достаточное число бит, то
операция побитового инвертирования позволяет получить все числа из множества чисел, которые требуется закодировать
2)
пример: нам нужно закодировать числа от 1 до 8
для хранения чисел потребуется 3 бита. Числовой ряд: 000, 001, ..., 111
или
множество чисел {1, 2, ..., 8} отображается 1:1 во множество двоичных чисел {000, 001, ..., 111}

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

- инвертируем 1 бит в числе, получаем С(1, 3) комбинаций (чисел)
- инвертируем 2 бита в числе, получаем С(2, 3) комбинаций (чисел)
- инвертируем все 3 бита в числе, получаем С(3, 3) комбинаций (чисел)

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

4)
я еще не все до конца додумала
...
Рейтинг: 0 / 0
20.01.2016, 16:21
| Ответить | Цитировать | Написать  
из тестового задания
    #39151629
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahovmini.weblabОпределим ключ как последовательность значимых переключателей
Пусть имеются числа от 1 до n.
Требуется закодировать заданное число от 1 до n.
Метод кодировки: изменение одного бита в произвольно заданном ключе
Задача: Рассчитать необходимый и достаточный размер ключа

Это хороший повод поговорить по душам с тестирующим )
Плюс в том, что разговор может получиться длинным и своем поле.
Минус в том, что при этом его легко обидеть.
Ваши шансы возрастают, если разговор будет на троих )
это наезд, да ? :)
вы просто скажите, где неправильно :)
...
Рейтинг: 0 / 0
20.01.2016, 16:30
| Ответить | Цитировать | Написать  
из тестового задания
    #39151668
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabэто наезд, да ? :)
вы просто скажите, где неправильно :)

Наоборот, все правильно.
И это может стать проблемой, если вдруг окажется правильней, чем у экзаменующего )
...
Рейтинг: 0 / 0
20.01.2016, 17:02
| Ответить | Цитировать | Написать  
из тестового задания
    #39151692
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Привет еще раз.

Вобщем 3 часа грыз ручку. Часа два вчера.

И сегодня час. Нарисовал следующее решение.

Прошу прощения коллеги если боян. Я уже не в состоянии осилить трафик
потоков сознания который был написан.

Я приаттачу свои мысли на бумаге. И если у кого-то будут вопросы - отвечу.

Для меня вывод - решение существует. И в 40 переключателях можно закодировать
номера дверей от 1 до 32х.
...
Рейтинг: 0 / 0
20.01.2016, 17:43
| Ответить | Цитировать | Написать  
из тестового задания
    #39151693
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
...
Рейтинг: 0 / 0
20.01.2016, 17:44
| Ответить | Цитировать | Написать  
из тестового задания
    #39151695
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
...
Рейтинг: 0 / 0
20.01.2016, 17:44
| Ответить | Цитировать | Написать  
из тестового задания
    #39151696
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
...
Рейтинг: 0 / 0
20.01.2016, 17:44
| Ответить | Цитировать | Написать  
из тестового задания
    #39151698
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
...
Рейтинг: 0 / 0
20.01.2016, 17:45
| Ответить | Цитировать | Написать  
из тестового задания
    #39151699
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
...
Рейтинг: 0 / 0
20.01.2016, 17:45
| Ответить | Цитировать | Написать  
из тестового задания
    #39151703
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Прошу прощения за сбой в нумерации. Пункты 5,6,7 одной фоткой почти вышло.
...
Рейтинг: 0 / 0
20.01.2016, 17:46
| Ответить | Цитировать | Написать  
из тестового задания
    #39151727
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton, прочитай то что жирным написано 18705910 работа с битами тут не нужна. Надо только определить сколько бит надо использовать.
...
Рейтинг: 0 / 0
20.01.2016, 18:00
| Ответить | Цитировать | Написать  
из тестового задания
    #39151747
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, спасибо. Ты очень любезен.
...
Рейтинг: 0 / 0
20.01.2016, 18:22
| Ответить | Цитировать | Написать  
из тестового задания
    #39151855
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

Переделал у себя в программе нумерацию подмножеств аналогично 18705910 .
В результате избавился от массива констант, т.к. теперь биты номера комнаты,
входящие в подмножество в точности совпадают с битами номера подмножества.
Спасибо за идею.

 
исходник программы
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
function CodeToNumber(Code: cardinal): cardinal;
var
  SetNo: cardinal;
begin;
  Result:=0;
  SetNo:=1;
  while Code<>0 do begin;
    if Code and 1<>0 then Result:=Result xor SetNo;
    Code:=Code shr 1;
    inc(SetNo);
    end;
  end;

function GetNewCode(Code, Number: cardinal): cardinal;
begin;
  Number:=CodeToNumber(Code) xor Number;
  if Number<>0 then Code:=1 shl (Number-1) xor Code;
  Result:=Code;
  end;

const
  BitCount= 2;
  MaxNumber= 1 shl BitCount - 1;
  MaxCode= 1 shl MaxNumber - 1;

procedure TForm1.btnValidateClick(Sender: TObject);
var
  Code, Number, NewCode, NewNumber: cardinal;
begin;
  for Code:=0 to MaxCode do for Number:=0 to MaxNumber do begin;
    NewCode:=GetNewCode(Code, Number);
    NewNumber:=CodeToNumber(NewCode);
    if NewNumber<>Number then begin;
      Memo1.Lines.Add(Format('Error: Code=%d Number=%d NewCode=%d NewNumber=%d',
                              [Code, Number, NewCode, NewNumber]));
      exit;
      end;
    end;
  Memo1.Lines.Add('Done.');
  end;

procedure TForm1.btnTableClick(Sender: TObject);
var
  Code, Number: cardinal;
  s: string;
begin;
  s:='OldCode\No';
  for Number:=0 to MaxNumber do s:=s + Format('%3d  ',[Number]);
  Memo1.Lines.Add(s);
  for Code:=0 to MaxCode do begin;
    s:=Format('%5d   ',[code]);
    for Number:=0 to MaxNumber do s:=s+Format('%5d',[GetNewCode(Code, Number)]);
    Memo1.Lines.Add(s);
    end;
  end;




 
таблица для 4х комнат
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
OldCode\No  0    1    2    3
    0       0    1    2    4
    1       0    1    5    3
    2       0    6    2    3
    3       7    1    2    3
    4       0    6    5    4
    5       7    1    5    4
    6       7    6    2    4
    7       7    6    5    3


...
Рейтинг: 0 / 0
20.01.2016, 22:15
| Ответить | Цитировать | Написать  
из тестового задания
    #39151883
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dima T,
да, идея отличная
...
Рейтинг: 0 / 0
21.01.2016, 00:08
| Ответить | Цитировать | Написать  
из тестового задания
    #39151921
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Aleksandr SharahovSashaMercuryAleksandr Sharahov, простите, но мне непонятно ваше доказательство, более того, я плохо понял что вы пытались доказать.


Доказывается необходимость и достаточность 2^N-1 переключателей для 2^N дверей.
Какое место в доказательстве непонятно?

Для кодирования каким-то способом ? или для чего ? Хотелось бы увидеть точную формулировку того, что вы доказывали
...
Рейтинг: 0 / 0
21.01.2016, 07:08
| Ответить | Цитировать | Написать  
из тестового задания
    #39151930
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Странный код
Aleksandr Sharahov
Код: pascal
1.
2.
  while Code<>0 do begin;
    if Code and 1<>0 then Result:=Result xor SetNo;


В паскале не силен, если правильно понимаю "if Code" дает true при Code<>0, то можно просто
Код: pascal
1.
2.
  while Code<>0 do begin;
    Result:=Result xor SetNo;


Так и задумывалось?
...
Рейтинг: 0 / 0
21.01.2016, 07:34
| Ответить | Цитировать | Написать  
из тестового задания
    #39151941
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TИзломал всю голову "простым" решением 18700090 от kealon(Ruslan), точнее тем как его объяснить. Как работает - понятно. Не мог придумать как назвать его таблицу, в итоге получилось как всегда - раз нельзя назвать, значит что-то не так.

Тотже алгоритм:
для шифрования: берем номер двери и делаем xor всех номеров включенных переключателей. Получаем номер того который надо переключить.
для дешифрования: xor всех включенных переключателей.

Например: включены переключатели 3,7. Надо указать на 6 дверь.
6 ^ 3 ^ 7 = 2-й переключатель надо переключить
2 ^ 3 ^ 7 = 6-я дверь

Требуемое количество переключателей : должны быть все переключатели используемого битового диапазона, т.к. в результате xor может получиться больше, например 4^3 = 7, т.е. если используется 3 бита, то надо все до 2^3 (=8), т.е. от 1 до 7, ноль не надо т.к. X ^ 0 = X, поэтому всего 2^N - 1, где N количество используемых бит.

Для 8 дверей хватит 3 бит (7 переключателей) если двери нумеровать с нуля, а не с 1. Иначе надо 15 переключателей.
называется таблица просто - ключ шифровки-дешифровки
и таблица
автор1, 2, 3, 4

1, 4, 5, 6

1, 6, 7, 2

и простой XOR это два равноценных случая общего решения:
авторвыделим 3 взаимно пересекающиеся группы (оно же и даёт ответ о кол-ве необходимых бит SUM(i=1.. N , C(i,N)) = 2^N - C (0,N) = 2^N - 1 ключей)
для простого XOR разбивка на группы будет такая

1, 3, 5, 7

2, 3, 6, 7

4, 5, 6, 7

общая формула шифровки
M.IndexOf(V XOR со всеми M[ i ] если i-й ключ включён )
расшифровка
V = 0 XOR со всеми M[ i ] если i-й ключ включён
для простого XOR
M=[1, 2, 3, 4, 5, 6, 7]
для
автор1, 2, 3, 4

1, 4, 5, 6

1, 6, 7, 2

M=[7, 5, 1, 3, 2, 6, 4]

любое перемешивание ряда от 1 до (2^N-1) будет ключом, как видно вариантов ключей может быть K!, где K = 2^N -1 (т.е. очень дофига)
PS: нумерация M с 1-ы, нумерация комнат с 0
...
Рейтинг: 0 / 0
21.01.2016, 08:15
| Ответить | Цитировать | Написать  
из тестового задания
    #39151950
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TСтранный код
Aleksandr Sharahov
Код: pascal
1.
2.
  while Code<>0 do begin;
    if Code and 1<>0 then Result:=Result xor SetNo;


В паскале не силен, если правильно понимаю "if Code" дает true при Code<>0, то можно просто
Код: pascal
1.
2.
  while Code<>0 do begin;
    Result:=Result xor SetNo;


Так и задумывалось?

Переменная SetNo хранит номер очередного подмножества.
Оно содержит в точности те биты номера комнаты,
которые есть в двоичной записи значения SetNo.
Поэтому нумерация подмножеств начинается с 1.

В переменной Code содержатся состояния выключателей,
или, что то же самое, "необходимости" операции XOR над всеми под множествами.
Один бит переменной Code - один выключатель, в бите 0 - первый и т.д.

Первая строчка организует цикл по подмножествам.
Сначала текущее подмножество первое (то что в бите 0).
На каждом следующем такте - сдвиг вправо.
Т.к. нас интересуют только непустые операции,
то цикл закончится при Code=0.

Вторая строчка для очередного подмножества с номером SetNo,
если необходимо (Code and 1<>0) выполняет операцию XOR над подмножеством,
включая-исключая его биты (из SetNo) в результирующее подмножество (биты Result),
начальное состояние которого - пустое (Result=0).
...
Рейтинг: 0 / 0
21.01.2016, 08:32
| Ответить | Цитировать | Написать  
из тестового задания
    #39151953
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr Sharahov, понял. Тот код равносилен такому
Код: sql
1.
if (Code and 1)<>0 then Result:=Result xor SetNo;
...
Рейтинг: 0 / 0
21.01.2016, 08:39
| Ответить | Цитировать | Написать  
из тестового задания
    #39152609
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Python code:
 

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
class HotelCodeBoard():   
    def __init__(self, n, rnum):
        # number of switches on the board
        self.n = n
        # number of rooms in the hotel
        self.rnum = rnum
        # number of bits required to represent the room from range
        self.rbits = math.ceil( math.log(self.rnum, 2) )
        # number of switchers required to encode the room
        self.nswitchers = 2**self.rbits - 1
        # number of states for meaningful switchers
        self.nstates = 2**self.nswitchers
        
    def get_room_list(self):
        """
        Returns a list of room numbers
        """
        return list( range(self.rnum) )          

    
    def get_states_list(self):
        """
        Returns a list of states of meaningful switchers
        """
        states = []
        for i in range( self.nstates, 2*self.nstates ):
            states.append( list(bin(i)[3:])  )
        return states
    
    def get_state_value(self, state):
        """
        (list) -> int
        Returns state value for a give state of switchers
        """
        return self.get_states_list().index(state)
    
    def get_state(self, state_value):
        """
        (int) -> list
        Returns state for a given state_value
        """
        return self.get_states_list()[state_value]
    
    def encode_room(self, room_number, state_value):
        """
        (int, int) -> int
        Returns encoded room number
        """        
        # Check the validity of room number    
        if room_number not in self.get_room_list():
            print("This room is not in the hotel,")
            print("and will not be encoded.")
            return
        
        # Check the validity of state_value
        n_states = self.nstates
        if state_value not in range( n_states ):
            print("The state you requested is not available")
            print("and will not be used for encoding")
            return
        
        # get state as combination of switches
        state = self.get_state(state_value)      
        
        # room number encoding       
        switch_position = room_number        
        
        for i in range( len(state) ):
            if state[i] == '1':
                switch_position = switch_position^(i+1)        

        switch_position = switch_position - 1 
        
        # if switch_position = -1 do not change anything       
        if switch_position < 0:
            new_state_value = state_value
            return new_state_value, state                
         
        # switching at switch_position    
          
        if state[switch_position] == '0':
            state[switch_position] = '1'
        else:
            state[switch_position] = '0'
            
        new_state_value = self.get_state_value(state)
        return new_state_value, state
    
    def decode_room(self, state_value):
        
        state = self.get_state(state_value)
        
        switch_position = 0
        
        for i in range( len(state) ):
            if state[i] == '1':
                switch_position = switch_position^(i+1)
        
        room_number = switch_position
        return room_number 
    
    def get_decode_table(self):
        key_table = []
        for i in range( self.nstates):
            key_row = []
            for j in range( self.rnum):
                val = self.encode_room(j, i)[0]
                key_row.append(val)
            key_table.append(key_row)            
        return key_table



Tаблица для 4х комнат
 

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
-------------------------
Rooms:       [0, 1, 2, 3]
-------------------------
State:  0 :  [0, 4, 2, 1]
State:  1 :  [0, 3, 5, 1]
State:  2 :  [0, 3, 2, 6]
State:  3 :  [7, 3, 2, 1]
State:  4 :  [0, 4, 5, 6]
State:  5 :  [7, 4, 5, 1]
State:  6 :  [7, 4, 2, 6]
State:  7 :  [7, 3, 5, 6]
...
Рейтинг: 0 / 0
21.01.2016, 20:01
| Ответить | Цитировать | Написать  
из тестового задания
    #39152614
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mini.weblab,

почитай внимательно что я написал 18705910 , таблиц не надо, кода будет строк 10-15, ну пусть 20 по неопытности.
...
Рейтинг: 0 / 0
21.01.2016, 20:13
| Ответить | Цитировать | Написать  
из тестового задания
    #39152644
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dima T,
так я примерно так и сделала, как ты написал. непосредственно шифровка занимает как раз 15 строк
(метод encode_room() )
расшифровка - 8 строк. остальные функции - для удобства

к примеру, вот удобная для пользования табличка

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
---------------------------------------------
Rooms:                           [0, 1, 2, 3]
---------------------------------------------
State:  0 <-> ['0', '0', '0'] :  [0, 4, 2, 1]
State:  1 <-> ['0', '0', '1'] :  [0, 3, 5, 1]
State:  2 <-> ['0', '1', '0'] :  [0, 3, 2, 6]
State:  3 <-> ['0', '1', '1'] :  [7, 3, 2, 1]
State:  4 <-> ['1', '0', '0'] :  [0, 4, 5, 6]
State:  5 <-> ['1', '0', '1'] :  [7, 4, 5, 1]
State:  6 <-> ['1', '1', '0'] :  [7, 4, 2, 6]
State:  7 <-> ['1', '1', '1'] :  [7, 3, 5, 6]
...
Рейтинг: 0 / 0
21.01.2016, 21:11
| Ответить | Цитировать | Написать  
из тестового задания
    #39152655
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblab,

тоже спрошу )

А почему бы в качестве Encode/Decode не скопировать мои CodeToNumber, GetNewCode?
В питоне нет сдвигов? )
...
Рейтинг: 0 / 0
21.01.2016, 21:41
| Ответить | Цитировать | Написать  
из тестового задания
    #39152742
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Достаточно одной функции для шифрования и расшифровки.
В случае расшифровки просто зашифровать дверь номер 0. В результате будет номер закодированной двери.
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
// door - номер кодируемой двери
// max_door - максимальный номер двери
// switch_board - массив переключателей
// switch_count - количество переключателей
int crypt(int door, int max_door, bool switch_board[], int switch_count) {
	// требуемое количество переключателей (2^N)
	int mask = 1;
	while (mask <= max_door) {
		mask = mask * 2;
	}
	// Проверка достаточности переключателей
	if(switch_count < mask) {
		printf("Error: Too few switches. Need %d\n", mask);
		return -1;
	}
	// Кодирование
	int ret = door;
	for (int i = 1; i < mask; i++) {
		if (switch_board[i]) ret = ret ^ i;
	}
	return ret;
}

// Пример использования
void test() {
	// Исходное состояние переключателей
	bool sw[40] = { 0 };
	sw[2] = true;
	sw[3] = true;
	// Номер двери, на которую надо указать
	int door_num = 7;
	// Номер переключателя для кодирования
	int switch_for_code = crypt(door_num, 8, sw, 40);
	printf("Change switch %d\n", switch_for_code);
	// Переключение выключателя
	sw[switch_for_code] = !sw[switch_for_code];
	// Получение номера двери
	int door_need = crypt(0, 8, sw, 40);
	printf("Need door %d\n", door_need);
}

...
Рейтинг: 0 / 0
22.01.2016, 07:36
| Ответить | Цитировать | Написать  
из тестового задания
    #39152793
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

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

На мой взгляд, это тот случай, когда две лучше, чем одна )
...
Рейтинг: 0 / 0
22.01.2016, 09:43
| Ответить | Цитировать | Написать  
из тестового задания
    #39153122
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Aleksandr Sharahovmini.weblab,

тоже спрошу )

А почему бы в качестве Encode/Decode не скопировать мои CodeToNumber, GetNewCode?
В питоне нет сдвигов? )
я хотела записать решение, так как я его понимаю
с битовыми операциями я не очень-то пока дружу, разберусь - поправлю ( работаю по Agile )

Dima TДостаточно одной функции для шифрования и расшифровки.

согласна
...
Рейтинг: 0 / 0
22.01.2016, 15:19
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
из тестового задания
    #40118594
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
UP. Всё таки отличная задача была.

Я ходил вокруг нее и облизывался. Тоесть я не спешил ее делать. Обычно такие вкусные задачи оставляю
на отпуск на подумать. Но прошло 5 лет и я просто позабыл.

Я помню что последнее я рисовал - фасеты. Для трех комнат - три кружочка с пересечениями и вышло 7 фасетов
по которым нужно было сделать xor.

Но я хотел обобщить этот алгоритм для бОльшего числа комнат. Я помню Шарахов обосновал формулу количества
перключателей и комнат. Давайте добъем задачу и сделаем реализацию для N комнат и произвольного числа
перключателей.

Возможно XOR не единственный вариант и арифметическая сумма - тоже кажется мне идеей интересной хотя-бы
на обсудить.
...
Рейтинг: 0 / 0
09.12.2021, 12:53
| Ответить | Цитировать | Написать  
из тестового задания
    #40118741
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

ну так в 18708203 все решено в общем виде, только задавай нужный тебе BitCount, табличка сама получится

Код: pascal
1.
2.
3.
4.
const
  BitCount= 2;                            //кол. битов для кодирования номера двери - задать нужное
  MaxNumber= 1 shl BitCount - 1;     //макс. номер двери (мин=0) 
  MaxCode= 1 shl MaxNumber - 1;    //макс. значение кода (мин=0)



функции CodeToNumber и GetNewCode от размерности не зависят
...
Рейтинг: 0 / 0
09.12.2021, 20:16
| Ответить | Цитировать | Написать  
из тестового задания
    #40118749
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Опять Delphi
...
Рейтинг: 0 / 0
09.12.2021, 20:23
| Ответить | Цитировать | Написать  
из тестового задания
    #40118751
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

а что с ним не так?
...
Рейтинг: 0 / 0
09.12.2021, 20:26
| Ответить | Цитировать | Написать  
из тестового задания
    #40118754
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да всё нормально. Ворчу.
...
Рейтинг: 0 / 0
09.12.2021, 20:29
| Ответить | Цитировать | Написать  
из тестового задания
    #40118755
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov
mayton,

а что с ним не так?


кстати тут недавно смотрел одну задачку из школы 42,
у этих ваших сишников прямо-таки душераздирающие решения )))
...
Рейтинг: 0 / 0
09.12.2021, 20:31
| Ответить | Цитировать | Написать  
из тестового задания
    #40118757
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Что за школа?
...
Рейтинг: 0 / 0
09.12.2021, 20:34
| Ответить | Цитировать | Написать  
из тестового задания
    #40118762
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Что за школа?


Обучение азам программистов в разных странах,
у нас вроде при поддержке сбера,
точно не знаю, велик не мой.

Сама задача известна давно, привожу в их интерпретации.

The game is composed of 2 stacks named a and b.

To start with:
- a contains a random number of either positive or negative numbers without any duplicates.
- b is empty

The goal is to sort in ascending order numbers into stack a.

To do this you have the following operations at your disposal:
sa : swap a - swap the first 2 elements at the top of stack a. Do nothing if there is only one or no elements.
sb : swap b - swap the first 2 elements at the top of stack b. Do nothing if there is only one or no elements.
ss : sa and sb at the same time.
pa : push a - take the first element at the top of b and put it at the top of a. Do nothing if b is empty.
pb : push b - take the first element at the top of a and put it at the top of b. Do nothing if a is empty.
ra : rotate a - shift up all elements of stack a by 1. The first element becomes the last one.
rb : rotate b - shift up all elements of stack b by 1. The first element becomes the last one.
rr : ra and rb at the same time.
rra : reverse rotate a - shift down all elements of stack a by 1. The last element becomes the first one.
rrb : reverse rotate b - shift down all elements of stack b by 1. The last element becomes the first one.
rrr : rra and rrb at the same time.
...
Рейтинг: 0 / 0
09.12.2021, 20:48
| Ответить | Цитировать | Написать  
из тестового задания
    #40118796
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
А от чего душа раздиралась?
...
Рейтинг: 0 / 0
09.12.2021, 22:26
| Ответить | Цитировать | Написать  
из тестового задания
    #40118799
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98,

от решений, которым не всегда удается
отсортировать 100 случайных чисел даже за 700 ходов.
...
Рейтинг: 0 / 0
09.12.2021, 22:45
| Ответить | Цитировать | Написать  
из тестового задания
    #40118804
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Ясно.
Я не защищаю и не обвиняю, просто вспомнил кубик Рубика. Теоретически там несколько базовых перестановок, и соответственно их комбинации. Казалось бы всё просто, если их расписать подробно.
Но когда берёшь его в руки 1-й раз, 2й, 3-й, то процесс длится о-очень долго, но чаще закончится одной-двумя гранями.
Если воспользоваться готовыми блоками преобразований, то очень часто можно и собрать за несколько минут.
А по телеку видел соревнование - по 10-20 сек, только палцы сверкали. Похожее наблюдал и в транспорте пару лет назад. Как роботы на конвейере. Тренировка.
...
Рейтинг: 0 / 0
09.12.2021, 23:17
| Ответить | Цитировать | Написать  
из тестового задания
    #40118806
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Здесь другое, не зря же вспомнилась эта задача в этом топике )

700 это гораздо более, чем достаточно.
И вариантов решений более, чем 1.
...
Рейтинг: 0 / 0
09.12.2021, 23:26
| Ответить | Цитировать | Написать  
из тестового задания
    #40118816
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov

Обучение азам программистов в разных странах,
у нас вроде при поддержке сбера,
точно не знаю, велик не мой.

Сама задача известна давно, привожу в их интерпретации.

The game is composed of 2 stacks named a and b.

To start with:
- a contains a random number of either positive or negative numbers without any duplicates.
- b is empty

The goal is to sort in ascending order numbers into stack a.

Капец задача. Напоминает ханойские башни но с другим API. Не захотел-бы ее решать.
Просто так. Слишком как-то тоскливо что-ли начинать ее делать. Тут мне кажется
надо как-то сильнее замотивировать или чуть снизить порог вхождения.

Раз в сезон я играю в Klotski. Это настольная игра вроде пентамино и пятнашек.
Нужно двигать геометрические фигурки так чтобы они заняли определенное место.
Иногда кажется что капец. Решения не существует. Психуешь. Отставляешь игру.
Потом возвращаешся. И вдруг... задача решается. И погнал дальше по уровням.
А дальше уровни - еще хуже. Те-же фигурки. Но вместо двух мелких добавляется
еще одна крупная. Больше тупиков или альфа-бета отсечений.
...
Рейтинг: 0 / 0
10.12.2021, 00:45
| Ответить | Цитировать | Написать  
166 сообщений из 166, показаны все 7 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / из тестового задания
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru, Чат Кролика       Пашэ: Рисунки, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1339609]:
 0ms
get settings:
 11ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 31ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 185ms
get tp. blocked users:
 2ms
others: 242ms
total:  509ms
созд. / загр.: 509ms
x
x
Закрыть


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