БOльшая половина

Задача

Дан массив А из n числовых элементов, больше половины которых равны межу собой. Требуется найти их значение за один просмотр массива.

Решение

На СИ - функция ВР возвращает искомое значение:

int BP (int n, int a [ ] )
{  int i, m = 0, x;
   for (i = 0; i<n; i++ )
   { if  (! m) x = A [ i ] ;
     if ( x == A [ i ] ) m ++;
     else m - - ;
   } return x;
}

На Бейсике - подпрограмма заносит в х искомое значение:

500 m = 0
510 for i = 0 to n-1
520 if m = 0 then x = A ( i )
530 if x = A ( i ) then m = m + 1
      else m = m  - 1
540 next
550 return

Наше решение предполагает, что больше половины элементов массива А действительно одинаковы. Если в этом уверенности нет, то нужно (по окончании цикла)
сосчитать, сколько элементов А равны полученному значению х.

Пусть с - любое фиксированное значение. Пусть t = t ( i ) - число элементов, равных с в наборе А [ 0 ] , ..., А [ i ] , а f = f ( i )- не равных с в этом наборе. Тогда при любом i будет выполняться следующее условие.

Условие: Ј і ?   
        если х = с, то t - f  Ј  m,
           если х ? с, то t - f  і  m.

Действительно. В начале наших программ m = t = f = 0 - и условие выполнено.

Проверим что условие сохраняется при выполнении операторов тела цикла. Для этого отметим штрихами значения переменных и пунктов (1) и (2) условия после выполнения этих операторов и рассмотрим все возможные случаи.

1. m = 0. Тогда t Ј f, m' = 1, x' = A[i]. Поэтому

  1.1. Если A[i] = c, то t' = t+1,
         f' = f + 1 и x' = c, t' - f' Ј m', т.е. (1')

  1.2.  Если A[i] ? с , то t' = t,
         f' = f + 1 и x' ? с, f' - t'  і m', т.е. (2')

2. m > 0. Тогда x' =  x. Поэтому

  2.1. Если (1), т.е. x = c,  t - f Ј m,  то
         при A[i] = c, будет  t' = t+1, A[i] = x,
        m' = m + 1 и t' - f' Ј m', т.е.          (1')
         при A[i] ? c, будет  f' = f+1, A[i] ? x,
        m' = m - 1 и t' - f' Ј m', т.е.          (1')

  2.2.  Если (2), т.е. x  ? c,  f - t і m,  то
         при A[i] = c, будет  t' = t+1, A[i] ? x,
        m' = m - 1 и f' - t' і m', т.е.          (2')
         при A[i] ? c, будет  f' = f+1,
        m' = m + 1 и   f' - t' і m', т.е.        (2')

Докажем, что наши программы дают верный результат. По условию нашей задачи больше половины членов массива A имеют одинаковую величину. Обозначим ее с. Тогда по окончании работы оператора цикла будет выполняться неравенство t > f. Это исключает (2). Значит, x = c.

Если (1), т.е. x = c,  t - f Ј m,  то
         при A[i] = c, будет  t' = t+1, A[i] = x,
        m' = m + 1 и t' - f' Ј m', т.е.          (1')

Если A[i] ? с , то t' = t,
         f' = f + 1 и x' ? с, f' - t'  і m', т.е. (2')