ссылка на Алгоритм

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

задан 16 Мар 20:07

10|600 символов нужно символов осталось
1

Нужно доказать, что если в массиве имеется преобладающий элемент, то алгоритм его выявляет. Пусть это элемент x. Свяжем с каждый шагом алгоритма величину s, равную показаниям счётчика, если в первой ячейке находится x (то есть он "кандидат" на преобладание), и -t, если показание счётчика равно t, а в первой ячейке находится не x. Проверим, что при появлении x следующим элементом, величина s всегда увеличивается на 1. Если в первой ячейке x, то s>=0, и при появлении x получается s+1. Если в первой ячейке не x, а счётчик равен t>=0, то при t=0 первый элемент заменяется на x, счётчик становится равен 1. Если t > 0, то при появлении x первая ячейка не меняется, а t меняется на t-1, то есть s=-t заменяется на s=1-t.

Аналогично проверяется, что при появлении очередным элементом не x, в худшем случае s уменьшается на 1. Легко проверить, хотя это излишне, что s может и увеличиваться на 1 при появлении "не своего" элемента. В любом случае, поскольку x преобладает, мы на более чем половине шагов прибавляем 1 к s, а на остальных шагах вычитаем максимум 1. Поэтому сумма положительна, и s > 0 в конце процесса. А из этого следует, что x находится в первой ячейке.

ссылка

отвечен 16 Мар 21:18

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×237

задан
16 Мар 20:07

показан
53 раза

обновлен
16 Мар 21:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru