Из одного моего экзамена.

Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов. Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

Удачи.
ЗЫ. Было давно, так что не гарантирую правильность условий, но, вроде, всё правильно.

Здравствуйте fAX, Вы писали:

fAX>Из одного моего экзамена.

fAX>Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов. Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

fAX>Удачи.
fAX>ЗЫ. Было давно, так что не гарантирую правильность условий, но, вроде, всё правильно.

А если сложить все числа в массиве...

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте fAX, Вы писали:

fAX>>Из одного моего экзамена.

fAX>>Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов. Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

KA>А если сложить все числа в массиве...

Это займет как минимум O(n * ]log2(n)[) времени, потому что за 1 раз читается 1 бит.

fAX>>ЗЫ. Было давно, так что не гарантирую правильность условий, но, вроде, всё правильно.

Вроде не все правильно, потому что от n*]log2(n)[ битов этого массива никуда не деться.

Здравствуйте fAX, Вы писали:

fAX>Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов.

Длины чисел в битах в массиве совпадают или нет? На первый взгляд, совпадают, т.к. сказано "каждый из которых состоит из log n битов". Но эта замечание "верхняя граница" несколько сбивает с толку.

fAX>Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

Не понимаю. В первой части условия сказано, что в массиве находятся n элементов. Во второй части сказано, что там находятся все числа от 1 до n, кроме одного, т.е. получается n — 1 элемент. Так сколько же их там? n или n — 1? И если все таки n, то что хранится вместо отсутствующего числа?

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Здравствуйте fAX, Вы писали:

fAX>>Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов.

АТ>Длины чисел в битах в массиве совпадают или нет? На первый взгляд, совпадают, т.к. сказано "каждый из которых состоит из log n битов". Но эта замечание "верхняя граница" несколько сбивает с толку.
Я имел в виду "верхняя граница log n", а не просто "целая часть"ю

fAX>>Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

АТ>Не понимаю. В первой части условия сказано, что в массиве находятся n элементов. Во второй части сказано, что там находятся все числа от 1 до n, кроме одного, т.е. получается n — 1 элемент. Так сколько же их там? n или n — 1? И если все таки n, то что хранится вместо отсутствующего числа?
Да, таки напортачил. От 0 до n без одного числа.

Здравствуйте fAX, Вы писали:

fAX>Из одного моего экзамена.

fAX>Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов. Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

fAX>Удачи.
fAX>ЗЫ. Было давно, так что не гарантирую правильность условий, но, вроде, всё правильно.

Для простоты предположим что n — степень числа 2 (если нет — можем расширить массив, дописав в конец соотвествующие числа, что потребует не более че О(n) времяни и памяти).

1. Просматриваем старшие биты массива, одновременно составляем массив и индексов, тех элементов массва, которые содежат "1" в старшем бите, и массив с "0" в старшем бите. Подсчитываем число элементов у которых в старшем бите — 1. Если число элементов с "1" в старшем бите равно n/2-1, значит нехватает числа в котором этот бит взведен, если n/2, то наоборот.
2. Просматриваем те числа массива, у которых первы бит имеет заданое состояние. (массив положений таких чисел, получен на предыдущем шаге). Просматриваем второй бит, формируе массивы где данный бит взеден и не взведен, подсчитывем число взведенных. ...
3. Анализируем третий бит ...
...


на первом шаге алгоритма n — чтений,
на втором — n/2
всего не более 2n чтений.

Здравствуйте Chorkov, Вы писали:

C>Здравствуйте fAX, Вы писали:

fAX>>Из одного моего экзамена.

fAX>>Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов. Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

fAX>>Удачи.
fAX>>ЗЫ. Было давно, так что не гарантирую правильность условий, но, вроде, всё правильно.

C>Для простоты предположим что n — степень числа 2 (если нет — можем расширить массив, дописав в конец соотвествующие числа, что потребует не более че О(n) времяни и памяти).

C>1. Просматриваем старшие биты массива, одновременно составляем массив и индексов, тех элементов массва, которые содежат "1" в старшем бите, и массив с "0" в старшем бите. Подсчитываем число элементов у которых в старшем бите — 1. Если число элементов с "1" в старшем бите равно n/2-1, значит нехватает числа в котором этот бит взведен, если n/2, то наоборот.
C>2. Просматриваем те числа массива, у которых первы бит имеет заданое состояние. (массив положений таких чисел, получен на предыдущем шаге). Просматриваем второй бит, формируе массивы где данный бит взеден и не взведен, подсчитывем число взведенных. ...
C>3. Анализируем третий бит ...
C> ...


C>на первом шаге алгоритма n — чтений,
C>на втором — n/2
C>всего не более 2n чтений.

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