Конспект лекций по программированию для начинающих. Гладков В.П. - 154 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

156
4. n=9, a={1,0,2,0,0,3,0,0,0}. Ответ: максимальное количество нулей, следующих
подряд 3. Начало последовательности 7.
5. n=9, a={1,0,1,0,1,0,1,0,1}. Ответ: максимальное количество нулей, следующих
подряд 1. Начало последовательности 2.
6. n=9, a={3,0,0,0,2,0,0,1,0}. Ответ: максимальное количество нулей, следующих
подряд 3. Начало последовательности 2.
Упражнение. Проведите трассировку для каждого из приведенных тестов.
Исправим алгоритм так, чтобы он указывал номер позиции, с которой
начинается максимальная последовательность нулей. В тот момент, когда
обнаруживается максимальное значение s, индекс i указывает на последний
элемент последовательности подряд идущих нулей, s хранит количество нулей в
этой последовательности. Отсюда, номер первого элемента можно определить по
формуле i+1-s или, поскольку m и s равны, i+1-m. Обозначим номер первого
элемента в последовательности подряд идущих нулей через j. Соответствующий
фрагмент алгоритма приведен ниже:
{пример 11.12, вариант 1 с определением j}
m:=0; {нулей пока не обнаружено}
s:=0;
j:=0;
for i:=1 to n do
begin if a[i]=0
then s:=s+1
else s:=0;
if m<s then begin m:=s; j:=i+1-m end
end;
write('максимальное количество нулей, следующих подряд ',m,' ',j).
Анализ первого варианта алгоритма показывает, что нет необходимости
проверять значение s на максимум после каждого элемента
массива. Это
достаточно делать только для ненулевых элементов. Для этого нужно перенести
второй условный оператор в ветку else первого условного оператора. Кроме того,
нужно вынести этот же оператор за цикл, чтобы проверить m и s, когда массив
заканчивается нулем. В новом алгоритме проверка осуществляется, когда i
указывает на первый ненулевой элемент после последовательности нулей, поэтому
номер начала последовательности нулей определится по формуле j=i-m или для
последнего элемента j=n+1-m.
{пример 11.12, вариант 2 с определением j}
m:=0; {нулей пока не обнаружено}
s:=0;
j:=0;
for i:=1 to n do
if a[i]=0
then s:=s+1
else begin if m<s then begin m:=s;j:=i-m end;
s:=0
end;
{массив может закончиться нулем, поэтому нужно проверить на максимум} 
                                      156

   4. n=9, a={1,0,2,0,0,3,0,0,0}. Ответ: максимальное количество нулей, следующих
подряд 3. Начало последовательности 7.
   5. n=9, a={1,0,1,0,1,0,1,0,1}. Ответ: максимальное количество нулей, следующих
подряд 1. Начало последовательности 2.
   6. n=9, a={3,0,0,0,2,0,0,1,0}. Ответ: максимальное количество нулей, следующих
подряд 3. Начало последовательности 2.
   Упражнение. Проведите трассировку для каждого из приведенных тестов.
   Исправим алгоритм так, чтобы он указывал номер позиции, с которой
начинается максимальная последовательность нулей. В тот момент, когда
обнаруживается максимальное значение s, индекс i указывает на последний
элемент последовательности подряд идущих нулей, s хранит количество нулей в
этой последовательности. Отсюда, номер первого элемента можно определить по
формуле i+1-s или, поскольку m и s равны, i+1-m. Обозначим номер первого
элемента в последовательности подряд идущих нулей через j. Соответствующий
фрагмент алгоритма приведен ниже:
   {пример 11.12, вариант 1 с определением j}
   m:=0; {нулей пока не обнаружено}
   s:=0;
   j:=0;
   for i:=1 to n do
   begin      if a[i]=0
              then s:=s+1
              else s:=0;
              if m

Страницы