|
|
Пишет Oleg Izhvanov (![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small} izh) в ![[info]](http://lj.rossia.org/img/community.gif){kind=small} programming@ 2007-06-24 19:27:00 |
 |
|
 |
|
|
|
|
|
|
 |
|
 |
Простая задачка (с красивым решением)
Имеется последовательность из N объектов,
про любые два из которых можно сказать только
равны они или нет. Известно, что некоторого
объекта в последовательности больше половины.
Придумать алгоритм поиска этого объекта,
который бы завершался за один проход по
последовательности и использовал фиксированный
(то есть не зависящий от N) объем памяти.
Комменты скринятся.
Пояснение:
Понятно, что количество бит, при помощи которых
можно закодировать число N зависит от N, но
конкретно этой зависимостью можно пренебречь.
Также понятно, что от размера объекта зависит
объем используемой памяти. Этой зависимостью можно
также пренебречь. Существенно, чтобы количество
используемой памяти не зависело от количества
элементов в последовательности.
Решение (выделить мышкой):
Имеется последовательность из N объектов,
про любые два из которых можно сказать только
равны они или нет. Известно, что некоторого
объекта в последовательности больше половины.
Придумать алгоритм поиска этого объекта,
который бы завершался за один проход по
последовательности и использовал фиксированный
(то есть не зависящий от N) объем памяти.
Комменты скринятся.
Пояснение:
Понятно, что количество бит, при помощи которых
можно закодировать число N зависит от N, но
конкретно этой зависимостью можно пренебречь.
Также понятно, что от размера объекта зависит
объем используемой памяти. Этой зависимостью можно
также пренебречь. Существенно, чтобы количество
используемой памяти не зависело от количества
элементов в последовательности.
Решение (выделить мышкой):
Одно из возможных решений основывается на том
интересном факте, что из последовательности
можно выкинуть 3 произвольных попарно неравных
элемента. При этом количество искомых элементов
по прежнему будет больше половины в уменьшенной
последовательности. Другое решение (более простое),
предложенное Димой Калединым, также использует
индукцию. Понять, как именно, предоставляется
читателю в качестве упражнения.
Для простоты в решении рассматривается массив из
целых чисел. Алгоритмы, впрочем, будут работать для
любых объектов.
Мой вариант решения:
int find_most_repeatable(int *arr, size_t size)
{
unsigned int i;
int a, b = 0, e, answer_a, answer_b, answer;
answer_a = arr[0];
a = 1;
for (i = 1; i < size; i ++)
{
e = arr[i];
if (answer_a == e && a > 0)
a ++;
else if (answer_b == e && b > 0)
b ++;
else
{
if (a == 0)
{
answer_a = e;
a = 1;
continue;
}
else if (b == 0)
{
answer_b = e;
b = 1;
continue;
}
a --; b --;
}
}
if (a >= b)
answer = answer_a;
else
answer = answer_b;
return answer;
}
Вариант Димы Каледина (исправленный):
int find_most_repeatable2(int *arr, size_t size)
{
unsigned int i;
int answer, e, c;
answer = arr[0];
c = 0;
for (i = 1; i < size; i ++)
{
e = arr[i];
if (answer == e)
{
c ++;
if (c <= 0)
c ++;
}
else if (c >= 0)
c --;
if (c < 0)
answer = e;
}
return answer;
}
