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

F>Здравствуйте, уважаемые. Хочу предложить вам поразмяться :-)

F>Есть массив длинны N. Известно, что больше половины элементов
F>этого массива равны друг другу. Требуется за один (!) проход по
F>массиву выяснить чему же они равны.

F>Ходят слухи, что если массив целочисленный, то существует математическое
F>решение задачи. Но есть решение и в общем виде.

F>Что скажете?

Придумал. Правда массив надо будет преобразовать в список, но если этого не делать, то можно сформировать второй массив флажков.

Решение следующее:
Есть два указателя
1) на последний оставшийся элемент в массиве
2) на текущий элемент.

Если текущий и последний элемент не совпадают, то удаляем их из массива. Соответственно первый и второй указатель увеличиваем на еденицу или для списка смещаем вперёд.

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

В итоге остаётся массив одинаковых элементов. Или пусто, если он не имел таковых.

Пример:

#- первый указатель
*- второй указатель
|- флажок

шаги:

для массивов для списка:

1)1 3 1 1 2 1 4 1 3 1 1 2 1 4
* # * #

2)1 3 1 1 2 1 4 1 1 2 1 4
| | * # * #

3)1 3 1 1 2 1 4 1 1 2 1 4
| | * # * #

4)1 3 1 1 2 1 4 1 1 4
| | | * | # * #

5)1 3 1 1 2 1 4 1 1 4
| | | * | # * #

6)1 3 1 1 2 1 4 1
| | | | | |

Всё. Надеюсь понятно объяснил. Для списка получается ровно один проход и сложность в элементарных операциях 4N(если правильно посчитал:)).

Для двух массивов один проход по первому массиву.

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

L>Сейчас вот пытаюсь обдумать такой вариант:
L>

L>int cnt=0;
L>for(int i=0;i<size_of_a;i++)
L>{
L>   if(!cnt) num=a[i];
L>   if(a[i]!=num) cnt--;
L>   else cnt++;
L>}
L>

Такой вариант похоже действтельно будет работать.

А почему авторы алгортмов не приводят хотя бы схематического доказательства правильности?

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

Блин. Пример криво отображается.
Привожу его есчо раз:


PSP>Пример:

PSP>#- первый указатель
PSP>*- второй указатель
PSP>|- флажок

PSP>шаги:

PSP>для массивов

PSP>1)1 3 1 1 2 1 4
PSP> * #

PSP>2)1 3 1 1 2 1 4
PSP> | | * #

PSP>3)1 3 1 1 2 1 4
PSP> | | * #

PSP>4)1 3 1 1 2 1 4
PSP> | | | * | #

PSP>5)1 3 1 1 2 1 4
PSP> | | | * | #

PSP>6)1 3 1 1 2 1 4
PSP> | | | | | |

для списка:
1)1 3 1 1 2 1 4
* #

2)1 1 2 1 4
* #

3)1 1 2 1 4
* #

4)1 1 4
* #

5)1 1 4
* #

6)1
The End

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

L>>Сейчас вот пытаюсь обдумать такой вариант:
L>>

L>>int cnt=0;
L>>for(int i=0;i<size_of_a;i++)
L>>{
L>>   if(!cnt) num=a[i];
L>>   if(a[i]!=num) cnt--;
L>>   else cnt++;
L>>}
L>>

АТ>Такой вариант похоже действтельно будет работать.

... но несколько расточительно проверяет условия. Неоптимально. Более оптимальная реализация:

int num;

for (unsigned i = 0; i < size_of_a; ++i)
{
  num = a[i];
  unsigned cnt = 1;

  for (++i; i < size_of_a; ++i)
    if (a[i] == num)
      ++cnt;
    else
      if (--cnt == 0)
        break;
}

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

L>>Ну давай еще поспорим. За один проход, может означать только именно за один проход по исходному массиву. Никаких других требований на сложность это не накладывает.
АТ>Ну ну ну! Если так подходить к требованию "за один проход", то тогда собственно и решать нечего: скопируй исходный массив в такой же отдельный массив (это делается за один проход), а затем уже делай все что угодно с копией. Хоть сто раз ее просматривай — все равно задача будет решена "за один проход" исходного массива...

Ну давай только до такой степени не будем опошлять идею.

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

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

L>>Сейчас вот пытаюсь обдумать такой вариант:
L>>

L>>int cnt=0;
L>>for(int i=0;i<size_of_a;i++)
L>>{
L>>   if(!cnt) num=a[i];
L>>   if(a[i]!=num) cnt--;
L>>   else cnt++;
L>>}
L>>

АТ>Такой вариант похоже действтельно будет работать.

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

Потому, что в облом. Доказательство "на пальцах" я в принипе придумал, а на придумывание строгого доказавательства времени жалко. :)

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

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

L>>>Сейчас вот пытаюсь обдумать такой вариант:
L>>>

L>>>int cnt=0;
L>>>for(int i=0;i<size_of_a;i++)
L>>>{
L>>>   if(!cnt) num=a[i];
L>>>   if(a[i]!=num) cnt--;
L>>>   else cnt++;
L>>>}
L>>>

АТ>>Такой вариант похоже действтельно будет работать.

АТ>... но несколько расточительно проверяет условия. Неоптимально. Более оптимальная реализация:

АТ>

АТ>int num;

АТ>for (unsigned i = 0; i < size_of_a; ++i)
АТ>{
АТ>  num = a[i];
АТ>  unsigned cnt = 1;

АТ>  for (++i; i < size_of_a; ++i)
АТ>    if (a[i] == num)
АТ>      ++cnt;
АТ>    else
АТ>      if (--cnt == 0)
АТ>        break;
АТ>}
АТ>

ОК. Тогда еще лучше так:

int num=a[0];
unsigned int cnt=1;
for (unsigned i = 1; i < size_of_a; ++i)
{
    if (a[i] == num)
      ++cnt;
    else
      if (--cnt == 0)
      {
         num=a[++i];
         cnt++;
      }
}

Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые. Если лидер был искомым, то все равно в оставшейся части он должен встречаться больше половины. Задача сводится к той же, но уже начиная с текущего i. Если лидер был не искомым, то тем более. Если лидер никогда не менялся, то для каждого i он встречается больше всех остальных, вместе взятых, значит и для i=n, значит он и есть искомый.

Разрешается ли перестраивать массив, если в ходе перестройки НЕ выполняются никакие вычисления ?

Разрешается ли перестраивать массив, если в ходе перестройки НЕ выполняются никакие вычисления ?

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

F>Здравствуйте, уважаемые. Хочу предложить вам поразмяться

F>Есть массив длинны N. Известно, что больше половины элементов
F>этого массива равны друг другу. Требуется за один (!) проход по
F>массиву выяснить чему же они равны.

F>Ходят слухи, что если массив целочисленный, то существует математическое
F>решение задачи. Но есть решение и в общем виде.

F>Что скажете?

Для целочисленного массива, допустим это n (32, 64) — битные integer. Пробегаемся по массиву и считаем, сколько раз каждый бит (1) попадается. Потом составляем по биту искомое число — если вероятность 1 на этой позиции больше 0.5, ставим 1, иначе 0.

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

lxa>Для целочисленного массива, допустим это n (32, 64) — битные integer. Пробегаемся по массиву и считаем, сколько раз каждый бит (1) попадается. Потом составляем по биту искомое число — если вероятность 1 на этой позиции больше 0.5, ставим 1, иначе 0.

Чтрого говоря, так можно обойтись с любым бинарным представлением
То есть для double метод тоже подоёдёт.

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

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

F>>Здравствуйте, уважаемые. Хочу предложить вам поразмяться

F>>Есть массив длинны N. Известно, что больше половины элементов
F>>этого массива равны друг другу. Требуется за один (!) проход по
F>>массиву выяснить чему же они равны.

F>>Ходят слухи, что если массив целочисленный, то существует математическое
F>>решение задачи. Но есть решение и в общем виде.

F>>Что скажете?

lxa>Для целочисленного массива, допустим это n (32, 64) — битные integer. Пробегаемся по массиву и считаем, сколько раз каждый бит (1) попадается. Потом составляем по биту искомое число — если вероятность 1 на этой позиции больше 0.5, ставим 1, иначе 0.

Супер! Стоило задачке 5 лет провисеть, чтобы ее наконец-то решили!

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

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

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

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

F>>>Здравствуйте, уважаемые. Хочу предложить вам поразмяться

F>>>Есть массив длинны N. Известно, что больше половины элементов
F>>>этого массива равны друг другу. Требуется за один (!) проход по
F>>>массиву выяснить чему же они равны.

F>>>Ходят слухи, что если массив целочисленный, то существует математическое
F>>>решение задачи. Но есть решение и в общем виде.

F>>>Что скажете?

lxa>>Для целочисленного массива, допустим это n (32, 64) — битные integer. Пробегаемся по массиву и считаем, сколько раз каждый бит (1) попадается. Потом составляем по биту искомое число — если вероятность 1 на этой позиции больше 0.5, ставим 1, иначе 0.

V>Супер! Стоило задачке 5 лет провисеть, чтобы ее наконец-то решили!

Ее замечательно решили 5 лет назад.

V>Кстати, таким способом можно не только, в массиве целых найти, можно в массиве любых объектов фиксированного размера, хоть в массиве структур. Его можно обощить и на случай массива с элементами переменной длины.

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

_DA>Ее замечательно решили 5 лет назад.

Но не дали доказательства правильности.

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

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

_DA>>Ее замечательно решили 5 лет назад.

H>Но не дали доказательства правильности.

Хм. Решение:
Пробегаемся по массиву.
Если счетчик равен 0, то счетчику присваиваем 1, запоминаем число.
Иначе сравниваем число с запомненным. Если они равны, то увеличиваем счетчик на 1, иначе уменьшаем на 1.
После работы алгоритма мы получаем наше число, которое встречается в более половины значений в массиве.
Условие существования такого числа для некоторой последовательности обозначим (1).

Примерное доказательство:
Пусть известно, что среди чисел a1,...,ak выполняется условие (1) и счетчик никогда (за исключением начального состояния) не становится равен 0 при работе алгоритма. Тогда очевидно, что число, полученное в результате работы алгоритма, является ответом. И это число = a1.
Возьмем теперь некоторую последовательность b1,...,bn такую что в результате работы алгоритма на этой последовательности счетчик стал равен 0, и до этого нулю равен не был (2). Тогда очевидно, что b1 встречается в этой последовательности столько же раз, сколько и остальные числа.
Рассмотрим теперь последовательность b1,...,bn,a1,...,ak, для которой выполняется (1), а для b1,...,bn выполняется (2), то есть после первых n шагов получили счетчик, равный 0, тогда получаем, что в b1,...,bn искомое число встречается не более чем в половине случаев. Из этого следует, что a1,...,ak также удовлетворяет условию (1).
Таким образом все куски приводящие к обнулению счетчика можно отбрасывать и сводить задачу к задаче над остатком последовательности. Оставшийся кусок будет удовлетворять (1) и ответом будет первое число из этого куска.

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

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

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

_DA>>>Ее замечательно решили 5 лет назад.

H>>Но не дали доказательства правильности.

_DA>Хм. Решение:
_DA>Пробегаемся по массиву.
_DA>Если счетчик равен 0, то счетчику присваиваем 1, запоминаем число.
_DA>Иначе сравниваем число с запомненным. Если они равны, то увеличиваем счетчик на 1, иначе уменьшаем на 1.
_DA>После работы алгоритма мы получаем наше число, которое встречается в более половины значений в массиве.
_DA>Условие существования такого числа для некоторой последовательности обозначим (1).

_DA>Примерное доказательство:

Молодец, а тепрь смотрите мое сообщение от 10.06.06 20:19.

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

H>Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые. Если лидер был искомым, то все равно в оставшейся части он должен встречаться больше половины. Задача сводится к той же, но уже начиная с текущего i. Если лидер был не искомым, то тем более. Если лидер никогда не менялся, то для каждого i он встречается больше всех остальных, вместе взятых, значит и для i=n, значит он и есть искомый.

А когда ситуация меняется?

Пусть N = 2M+1. И в наборе есть M+1 чисел "1", M чисел "2". То есть ответ "1".
И пусть в нашем наборе первые 2M чисел — это поочерёдно "1" и "2". То есть всё решается в последний момент.
Очевидно, что необходимо было запоминать двух лидеров.

Пусть мы рассмотрели первые K (K < N/2) элементов, и они все разные. Кто лидер? Придётся запоминать их всех.

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

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

H>>Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые. Если лидер был искомым, то все равно в оставшейся части он должен встречаться больше половины. Задача сводится к той же, но уже начиная с текущего i. Если лидер был не искомым, то тем более. Если лидер никогда не менялся, то для каждого i он встречается больше всех остальных, вместе взятых, значит и для i=n, значит он и есть искомый.

К>А когда ситуация меняется?

К>Пусть N = 2M+1. И в наборе есть M+1 чисел "1", M чисел "2". То есть ответ "1".
К>И пусть в нашем наборе первые 2M чисел — это поочерёдно "1" и "2". То есть всё решается в последний момент.
К>Очевидно, что необходимо было запоминать двух лидеров.

К>Пусть мы рассмотрели первые K (K < N/2) элементов, и они все разные. Кто лидер? Придётся запоминать их всех.
Тот, кто был последним.

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

К>>Пусть мы рассмотрели первые K (K < N/2) элементов, и они все разные. Кто лидер? Придётся запоминать их всех.
H>Тот, кто был последним.

Это не вяжется с твоим предуловием
H>>>Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые.