2011-gre-cs-practice-book.pdf/Q37 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 15: Строка 15:
  
 
=== Объяснение ===
 
=== Объяснение ===
 +
 +
Для начала определим количество возможных различных хеш-значений. Так как хеш-функция возвращает 8-битовые значения, у нас есть <m>2^8 = 256</m> возможных уникальных хешей.
 +
 +
Теперь рассмотрим задачу. Нам нужно найти максимальное число <m>k</m>, которое гарантирует, что среди любых 1000 входных значений найдется хотя бы <m>k</m> таких, которые имеют одинаковое хеш-значение.
 +
 +
Чтобы решить эту задачу, мы можем использовать принцип Дирихле. Этот принцип гласит, что если у вас больше объектов, чем ячеек, в которых они могут находиться, то хотя бы одна ячейка будет содержать более одного объекта.
 +
 +
В нашем случае объекты — это входные значения (всего их 1000), а ячейки — это возможные хеш-значения (всего их 256).
 +
 +
Применяя принцип Дирихле, мы хотим распределить 1000 объектов между 256 ячейками таким образом, чтобы хотя бы одна ячейка содержала максимально возможное количество объектов. Для этого мы вычислим минимальное количество объектов, которое должно попасть в каждую ячейку, если бы распределение было равномерным:
 +
 +
<m>\text{{Минимальное количество объектов в каждой ячейке}} = \left\lfloor \frac{\text{{Всего объектов}}}{ \text{{Количество ячеек}}} \right\rfloor = \left\lfloor \frac{1000}{256} \right\rfloor = 3</m>
 +
 +
Это означает, что каждая ячейка гарантированно получит минимум 3 объекта. Однако нам нужно учесть, что некоторые ячейки могут получить больше объектов, поскольку общее количество объектов не делится ровно на количество ячеек. Чтобы найти максимальное количество объектов в одной ячейке, мы добавляем остаток от деления:
 +
 +
<m>\text{{Максимальное количество объектов в одной ячейке}} = 3 + 1 = 4</m>
 +
 +
Таким образом, гарантируется, что хотя бы одна ячейка содержит 4 объекта. Следовательно, наибольшее значение <m>k</m>, при котором в любом множестве из 1000 входных значений обязательно найдутся хотя бы <m>k</m> элементов с одним и тем же хеш-значением, равно 4.
 +
 +
 +
 
{{cstest-source|2011-gre-cs-practice-book.pdf|33|37}}
 
{{cstest-source|2011-gre-cs-practice-book.pdf|33|37}}
  
  
 
{{question-ok|}}
 
{{question-ok|}}

Версия 15:19, 19 декабря 2024

Задача зарезервирована: Ydanyok 15:11, 19 декабря 2024 (UTC)

Вопрос: Q37-08c765

Хеш-функция h отображает 16-битовые входные значения на 8-битовые хеш-значения. Каково наибольшее значение k, такое что в любом наборе из 1000 входных значений существует хотя бы k входных значений, которые функция h отображает на одно и то же хеш-значение?

(A) 3 (B) 4 (C) 10 (D) 64 (E) 256


Ответы

  • Правильный ответ: 4
  • 3
  • 10
  • 64
  • 256

Объяснение

Для начала определим количество возможных различных хеш-значений. Так как хеш-функция возвращает 8-битовые значения, у нас есть возможных уникальных хешей.

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

Чтобы решить эту задачу, мы можем использовать принцип Дирихле. Этот принцип гласит, что если у вас больше объектов, чем ячеек, в которых они могут находиться, то хотя бы одна ячейка будет содержать более одного объекта.

В нашем случае объекты — это входные значения (всего их 1000), а ячейки — это возможные хеш-значения (всего их 256).

Применяя принцип Дирихле, мы хотим распределить 1000 объектов между 256 ячейками таким образом, чтобы хотя бы одна ячейка содержала максимально возможное количество объектов. Для этого мы вычислим минимальное количество объектов, которое должно попасть в каждую ячейку, если бы распределение было равномерным:

Это означает, что каждая ячейка гарантированно получит минимум 3 объекта. Однако нам нужно учесть, что некоторые ячейки могут получить больше объектов, поскольку общее количество объектов не делится ровно на количество ячеек. Чтобы найти максимальное количество объектов в одной ячейке, мы добавляем остаток от деления:

Таким образом, гарантируется, что хотя бы одна ячейка содержит 4 объекта. Следовательно, наибольшее значение , при котором в любом множестве из 1000 входных значений обязательно найдутся хотя бы элементов с одним и тем же хеш-значением, равно 4.


Исходники — вопрос 37 на 33 странице книги «2011-gre-cs-practice-book.pdf»

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q37&oldid=34170»