Ступеньки понимания: решаем задачи на массивы

Сколько элементов массива будут иметь положительные значения?

1) 49

2) 28

3) 21

4) 7

Правильный ответ: 21.

Решение

Школьники, как правило, решают эту задачу “в лоб”, они рисуют таблицу (двумерный массив) и вписывают в нужные клетки получаемые значения. Такой способ при решении задач с небольшой размерностью допустим.

Другой способ основывается на анализе выполнения вложенного цикла. При p-м выполнении внутреннего цикла выражение k – n будет положительным при k > n. Так как k и n изменяются от 1 до 7, искомое значение будет равно

6 + 5 + 4 + 3 + 2 + 1 = 21.

2. Задание А8 из ЕГЭ по информатике 2007 года.

Все элементы двумерного массива A размером 10 ? 10 элементов первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы (ниже представлена одна и та же программа, записанная на разных языках программирования).

Сколько элементов массива в результате будут равны 1?

1) 0

2) 16

3) 12

4) 4

Правильный ответ: 12.

2. Базовые технические задачи

К базовым техническим задачам на обработку массивов мы относим следующие задачи:

1. Заполнить массив по возрастанию, по убыванию, случайным образом.

2. Не используя вспомогательных массивов, переставить элементы массива в обратном порядке.

3. Сдвинуть элементы массива влево, вправо на k позиций (это две разные задачи).

4. Циклический сдвиг элементов массива на k позиций влево, вправо.

5. Эффективный алгоритм циклического сдвига элементов массива на k позиций влево, вправо.

6. “Сжатие” массива.

7. Заполнение двумерного массива (по возрастанию, выше главной диагонали, только главную диагональ и т.п.).

8. Вывод двумерного массива на экран в виде таблицы.

Приведем ряд задач на отработку технических навыков работы с массивами.

3. Сформировать массив, элементами которого будут квадраты соответствующих индексов.

Замечание. Это один из способов формирования упорядоченного по возрастанию массива.

4. Требуется создать массив из N случайных целых чисел.

Решение. При отработке технических навыков программирования важно научить школьников не использовать в тексте программы числовые константы в явном виде. Всем таким константам должны быть даны имена в блоке const.

    const N = 10; 
    {количество элементов массива}
               MAX_V = 15; 
              {диапазон случайных чисел}
    var m: array[1..N] of integer; 
             i: integer;
    begin 
         randomize;
         for i := 1 to N do 
        {создание и вывод элементов массива}
         begin
             m[i] := random(MAX_V);
             writeln('m[i]=',m[i])
         end
    end. 

5. Из элементов массива А сформировать элементы массива B по правилу:

b[i] := а[1] + а[2] + ... + а[i].

Замечание. Для решения этой задачи не надо использовать вложенные циклы. Ниже приведен фрагмент программы.

for i := 2 to n do b[i] := b[i - 1] + а[i];

6. Ввести с клавиатуры n чисел и распечатать их в обратном порядке.

Замечание. Поскольку необходимо хранить в памяти введенные значения, то данные организуются в массив. Для решения задачи массив переписывать в обратном порядке не надо, для печати элементов в обратном порядке достаточно использовать оператор цикла

for i := n downto 1 do write(a[i]:4).

7. Не используя других массивов, переставить элементы целочисленного массива в обратном порядке.

Решение. Для всех индексов 1 i (n div 2) необходимо каждый i-й элемент поменять местами с (n – i + 1)-м элементом. При решении этой задачи учащиеся отрабатывают операцию обмена значений элементов массива. Важно обратить внимание учащихся, что для обмена местами левой и правой половин массива цикл должен отработать только (n div 2) раз при любом n (как четном, так и нечетном). Ниже приведен фрагмент программы.

for i := 1 to n div 2 do 
    begin
      k := x[i]; x[i] := x[n + 1 - i]; 
      x[n + 1 - i] := k
    end; 

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

Решение

const n = 10; 
var x: array [1..n] of integer;
    t, i: integer;
begin
  t := x[n];
  for i := n downto 2 do
    x[i] := x[i - 1];
  x[1] := t
end. 

В данной задаче принципиальным является порядок выполнения сдвигов. Так, если цикл downto заменить на for i := 2 to n do, то все элементы получат значение x[1].

9. Значения массива сдвинуть циклически вправо на k позиций.

Решение. Эту задачу можно решить следующим способом: выполнить в цикле k раз тело предыдущей программы. Подсчитаем сложность предложенного алгоритма. Основной операцией при выполнении этой программы является оператор присваивания. Он будет выполнен (n + 1)k раз. При k, близком к n, мы получим квадратичную сложность. Можно ли написать программу с меньшей сложностью алгоритма? Да, можно.

10. Написать эффективную программу циклического сдвига значений массива вправо на k позиций, где k < n.

Решение. Для решения этой задачи можно предложить алгоритм линейной сложности без использования дополнительных массивов. Идея алгоритма состоит в следующем. Запишем в обратном порядке первые n – k элементов. Затем запишем в обратном порядке последние k элементов. А затем перепишем в обратном порядке весь измененный массив.

const n = 10;
var a:array [1..n] of integer;
    k,p,t:integer;
begin
{заполнение массива}
  for p := 1 to (n - k) div 2 do
    begin
       t := a[p];
       a[p] := a[(n - k) – p + 1];
       a[(n - k) – p + 1] := t
      end;
  for p := 1 to k div 2 do
    begin
       t := a[n – k + p];
       a[n – k + p] := a[n – p + 1];
       a[n – p + 1] := t
    end;
  for p := 1 to n div 2 do
    begin
       t := a[p];
       a[p] := a[n – p + 1];
       a[n – p + 1] := t
    end
end. 

Сложность этого алгоритма, вычисленная в операторах присваивания, равна 3n и не зависит от k.

11. Дан целочисленный массив размерности n. “Сожмите” массив, выбросив из него каждый второй элемент. “Освободившиеся” места в правой части массива заполните нулями. Дополнительный массив не использовать.

Решение

const n = 10;
    a: array [1..n] of byte = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
var i, j, k: integer;
begin
    k := 0;
    i := 1;
    while i <= n do
    begin
        a[i – i div 2] := a[i]; 
{перемещаем элемент с четным индексом на "свое" место}
        i := i + 2
    end;
        a[i] := 0; 
{последние (n – n div 2 + 1) элементы обнуляем }
    for i := 1 to n do write(a[i]: 3);
    readln
end.

12. Дан массив, содержащий нулевые элементы. “Сожмите” его, передвинув нулевые элементы в конец массива. Дополнительный массив не использовать.

Решение

const n = 10;
    a: array [1..n] of byte = (1, 0, 0, 2, 
    0, 3, 4, 7, 0, 1);
var i, k: integer;
begin
    k := 0;
    i := 1;
    for i := 1 to n do
    begin
       if a[i] = 0 then inc(k) 
       {подсчитываем количество нулей в части
       массива от 1 до i}
       else a[i - k] := a[i]; 
       {перемещаем ненулевой элемент на
       первое свободное место}
    end;
    for i := n – k + 1 to n do a[i] := 0;
    {освободившиеся места заполняем
    нулями}
    for i := 1 to n do write(a[i]: 2);
    readln
end. 

13. С помощью датчика случайных чисел заполнить двумерный массив A размера n x n числами 1, 4, 7, 10. Подсчитать в нем количество таких четверок

A[i, j], A[i + 1, j], A[i, j + 1], A[i + 1, j + 1],

в которых все элементы различны.

Решение. Искомая четверка элементов должна удовлетворять условию

A[i, j] * A[i + 1, j] * A[i, j + 1] * A[i + 1, j + 1] = 280.

const n = 10;
    max_v = 4;
var m: array[1..N, 1..N] of integer;
    i, j, k: integer;
begin 
    randomize;
    k := 0;
    for i := 1 to n do 
    {создание и вывод элементов массива}
    begin 
       for j := 1 to n do 
        begin
            m[i,j] := random(max_v) * 3 + 1;
          {массив заполняется числами 
           1, 4, 7, 10}
            write(m[i,j]:3)
         end;
       writeln 
    end;
    for i := 1 to n — 1 do
      for j := 1 to n – 1 do
         if A[i,j] * A[i + 1,j] * 
         A[i,j + 1] * A[i + 1,j + 1] = 280 
        then k := k + 1;
    writeln(k)
end. 

14. Двумерный массив размера n x n содержит только положительные значения. Замените на ноль значения всех элементов, расположенных на главной и на побочной диагоналях. Главная диагональ идет из верхнего левого угла в правый нижний угол, побочная диагональ идет из верхнего правого в левый нижний угол.

Решение. Ниже приведен фрагмент программы.

for i := 1 to n do
   begin
      m[i,i] := 0; m[i, n – i + 1] := 0
   end 

15. Двумерный массив размера n x n содержит не равные нулю значения. Замените на ноль значения всех элементов, расположенные выше побочной диагонали.

Решение. Ниже приведен фрагмент программы.

for i := 1 to n do
    for j := 1 to n — i do 
         m[i,j] := 0; 

3. Базовые алгоритмы

Перечислим алгоритмы, которые наиболее часто встречаются в задачах на обработку массивов, именно поэтому их можно назвать базовыми:

1. Поиск максимального (минимального) значения в массиве.

2. Поиск двух максимальных (минимальных) значений массива.

3. Подсчет суммы значений элементов.

4. Проверить, что все элементы в массиве одинаковы.

5. Проверить, что все элементы массива различны.

6. В двумерном массиве подсчитать суммы по столбцам (строкам).

7. В двумерном массиве найти элемент максимальный по строке и минимальный по столбцу.

3.1. Поиск максимального (минимального) значения в массиве

Рассмотрим две задачи.

16. Синоптики фиксировали дневные температуры в течение всего года. Найти максимальную (минимальную) годовую температуру.

17. Синоптики фиксировали дневные температуры в течение всего года. Распечатать все дни, когда температура достигала максимального (минимального) значения.

Решение. Подход к решению этих на первый взгляд подобных задач должен быть различным. Очевидно, что для решения первой задачи совсем не обязательно заводить массив для хранения информации, так как запоминать значения температуры в каждый день года нам вовсе не обязательно. Эти значения можно обработать последовательно и получить требуемый результат.

Вот пример программы для решения подобной задачи.

const n = 365;
var i, a, max: integer;
begin
  read(a);
  max := a;
    for i := 1 to n do 
      begin
        read(a); {считываем данные}
        if max < a then max := a; 
        {при поиске минимального значения
        достаточно заменить условный оператор 
        на следующий: if min > a then min := a}
      end;
    writeln(max)
end.

Вторую задачу решить без использования массивов не представляется возможным. Рассматриваемая задача делится на две подзадачи:

1) поиск максимального значения среди всех годовых температур;

2) определение дней со значением температуры, равной максимальной.

Для выполнения этих подзадач необходимо обработать каждое значение два раза, что требует их хранения в памяти компьютера.

const n = 365;
var mas: array [1..n] of integer;
i, max: integer;
  begin
    randomize;
    for i := 1 to n do 
      mas[i] := -20 + random(40); 
      {инициализация массива}
      max := mas[1];
        for i := 2 to n do 
         if max < mas[i] then max := mas[i];
         for i := 1 to n do 
        if mas[i] = max then write(i: 4);
end.

Обратим внимание, что инициализирование переменной max первым обрабатываемым значением — прием, позволяющий избежать многих ошибок.

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

3.2. Поиск максимального (минимального) и следующего за ним по величине значений массива

18. Синоптики фиксировали дневные температуры в течение всего года. Найти максимальную годовую температуру и следующую за ней по величине температуру.

Решение. Ниже представлен текст программы для этой задачи. Отметим, что эту задачу можно решить без использования массива.

В переменных max1 и max2 будем хранить соответственно максимальный и следующий за максимальным элемент в уже просмотренной части массива.

const n = 365;
var mas: array [1..n] of integer;
i, max1, max2: integer;
begin
 randomize;
    for i := 1 to n do 
       mas[i] := -20 + random(40);
       if mas [1] < mas[2] then
          begin max1 := mas[2]; max2 := mas[1]
          end
       else
          begin max1 := mas[1]; max2 := mas[2]
          end
       for i := 3 to n do 
          if max1 < mas[i] then 
              begin max2 := max1: max1 := mas[i] end
          else if max2 < mas[i] then 
              maх2 := mas[i];
    writeln(max1: 3, max2: 3)
end. 

19. Синоптики фиксировали дневные температуры в течение всего года. Найти два самых холодных дня в году.

20. Синоптики фиксировали дневные температуры в течение всего года. Определить месяц, в котором максимальное число раз дневная температура равнялась первому или второму максимуму. Аналогичная задача есть в демоверсии ЕГЭ по информатике 2008 года.

3.3. Подсчет суммы значений элементов массива и среднего значения для элементов массива

21. Дан целочисленный массив. Подсчитать число элементов, больших среднего значения всех элементов массива.

Решение. Задача делится на две подзадачи: сначала надо найти среднее значение элементов массива (за один проход по массиву), а затем подсчитать количество элементов со значением, превышающим найденное среднее (второй проход по массиву).

22. Магазин обслужил за день 200 покупателей, каждый из которых потратил на покупки не более 1000 рублей. Посчитать дневную прибыль магазина и сумму среднего потребительского чека.

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

const n = 200;
m = 1000;
var mas: array [1..n] of integer;
i, sum: integer;
begin
 randomize;
  for i := 1 to n do 
    mas[i] := 1 + random(m);
    sum := 0;
      for i := 1 to n do sum := sum + mas[i];
  writeln('Прибыль магазина:', sum: 8);
  writeln('Средний чек:', sum/n: 8: 2)
end. 

3.4. Проверить, все ли элементы в массиве одинаковы

23. На атомной электростанции система каждую секунду записывает свои показания. Если хотя бы одно из показаний, записанных в течение минуты, отличается от предыдущих, значит, в системе произошел сбой и необходимо изменить настройки. Проверить, надо ли менять настройки системы.

Решение

const n = 60;
var i: integer;
mas: array [1..n] of integer;
flag: boolean; 
{флаг, который отвечает за равенство элементов}
begin
  randomize;
    for i := 1 to n do mas[i] := random(2);
    flag := true; 
    {предполагаем, что все значения равны}
    i := 2;
        while (i <= n) and flag do 
       {цикл выполняется до тех пор, пока не
        будут обработаны все элементы или пока не
        найдется такой элемент, который не будет равен
        предыдущим}
    begin
    flag := mas[i – 1] = mas[i]; 
    {проверка элементов на равенство
    предыдущему}
    inc(i)
    end;
       if flag then writeln('система работает нормально')
       else writeln('надо проверить систему');
      readln
end.

3.5. Проверить, все ли элементы массива различны

24. В базе данных хранятся номера сотрудников, которым была выписана премия за месяц. Проверить, не попал ли кто-либо из сотрудников в эту базу дважды.

Решение

const n = 10;
a: array [1..n] of byte = (1,2,3,4,5,6,7,8,9,10);
var i, j: integer;
b: boolean;
begin
  i := 1;
  b := true;
    while (i <= n – 1) and b do
     begin
      j := i + 1;
      while (j <= n) and b do begin
      b := b and (a[i] <> a[j]);
      inc(j)
     end;
    inc(i)
    end;
writeln(b);
readln
end.

С помощью внутреннего цикла мы проверяем, не встречается ли обрабатываемый элемент a[i] в подмассиве от (i + 1) до n.

В худшем случае, если все элементы в массиве различны, операция сравнения выполнится n(n – 1)/2 раз.

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

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

Задайте учащимся вопрос: “В каком случае вычислительная сложность задачи будет минимальна, а в каком — максимальна?”

3.6. Подсчет количества различных значений в массиве

26. Диспетчер заносила в базу номера товаров, которые поступали на склад в течение дня. Посчитать, сколько различных видов товаров было привезено на склад за этот день.

Решение. Счетчик различных номеров будем увеличивать тогда, когда элемент a[i] встретился в массиве последний раз. Для этого будем перебирать элементы массива; если элементa[i] совпал с каким-то элементом a[j], где j > i, то мы прекращаем сравнения a[i] с a[j] и переходим к элементу a[i + 1].

Пример 1. Для массива {1 2 2 2 1 1 3 4 5 6} увеличение счетчика для a[i] = 1 произойдет при обработке 6-го элемента, для a[i] = 2 увеличение счетчика произойдет при обработке 4-го элемента, для a[i] = 3 увеличение счетчика произойдет при обработке 7-го элемента и т.д.

Пример 2. Для массива {3 3 3 3 3 3 3 3 3 3} увеличение счетчика произойдет при обработке последнего элемента.

const n = 10;
a: array [1..n] of byte = (1,1,1,1,1,1,7,7,7,1);
var i, j, k: integer;
begin
 k := 1;
 for i := 1 to n — 1 do
   begin
    j := i + 1;
      while (j <= n) and (a[i] <> a[j]) do
      inc(j);
      if j = n + 1 then inc(k) 
       {учитываем элемент, когда встретили
       его последний раз}
      end;
   writeln(k);
   readln
 end. 

3.7. Подсчет суммы по строкам (столбцам) в двумерном массиве

27. На предварительных экзаменах ученики сдавали 5 экзаменов, каждый из которых оценивался по 10-балльной системе. Определить сумму баллов, набранную каждым учеником.

Решение

const n = 5; {количество предметов}
m = 30; {количество учеников}
var mas: array [1..m, 1..n] of integer;
i, j, sumstr: integer;
begin
  randomize;
    for i := 1 to m do
       for j := 1 to n do 
          mas[i,j] := random(11); 
         {инициализация двумерного массива}
            for i := 1 to m do 
                begin
                sumstr := 0; 
               {обнуляем значение переменной — сумма
               по текущей строке}
                     for j := 1 to n do 
                     sumstr := sumstr + mas[i, j];
                     writeln('Сумма баллов ученика ', i, ' равна ',
                     sumstr);
                end
end. 

28. В 10 регионов были отправлены вагоны с 20 различными видами товаров. Подсчитать общий вес продукции, отправленной в каждый регион, и общий вес продукции каждого вида.

Решение. Пусть каждая строка отвечает за отдельный регион, каждый столбец — за определенный вид товаров, тогда на пересечении i-й строки и j-го столбца будет храниться вес продукции j-го вида, отправленной в i-й регион.

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

const m = 11; {количество строк в
    массиве}
    n = 21; 
    {количество столбцов в массиве}
    var mas: array [1..m, 1..n] of integer;
    i, j: integer;
    begin
    randomize;
    for i := 1 to m — 1 do
    for j := 1 to n — 1 do 
    mas[i,j] := random(100); 
    for i := 1 to m – 1 do mas[i,n] := 0;
    {обнуление последнего столбца}
    for j := 1 to n – 1 do mas[m,j] := 0;
    {обнуление последней строки}
    for i := 1 to m — 1 do
    for j := 1 to n – 1 do 
    begin
    mas[m,j] := mas[m,j] + mas[i,j];
    mas[i,n] := mas[i,n] + mas[i,j];
    end
    end.

3.8. В двумерном массиве найти элемент максимальный по строке и минимальный по столбцу

29. Дана таблица a, состоящая из n строк и n столбцов. Требуется определить, есть ли в таблице такой элемент a[i, j], который был бы максимален в i-й строке и минимален в j-м столбце. Если такой элемент есть в таблице, то вывести его координаты. Если таких элементов несколько, то вывести координаты одного из них.

Решение

const n = 4;
a: array [1..n, 1..n] of 
integer = ((10,9,80,7),(11,8,20,11), (9,7,40,1),(13,3,20,6));
var i, j, k, st, min : integer;
flag: boolean;
begin
  i := 1;
  flag := false;
  while (i <= n) and not flag do
    begin
    st := 1;
      for j := 2 to n do
        if a[i, j] > a[i, st] then st := j;
       {нашли максимум по i-й строке, запомним
        его в переменной min}
        min := a[i,st];
       flag := true;
       k := 0;
       repeat
       inc(k);
       flag := flag and (a[k, st] >= min);
    {flag будет равен true, если найденный
    максимальный элемент является минимальным в
    столбце st}
    until (k >= n) or not flag;
    inc(i)
    end;
    if flag then writeln(i-1:3, st:3)
    else writeln('no');
 readln
end.

При решении задачи стоит обратить внимание на следующие моменты:

1) задача распадается на следующие подзадачи. Для каждой строки надо найти максимальный элемент, затем проверить, является ли он минимальным в своем столбце. Эту операцию при необходимости надо проделать со всеми строками;

2) когда мы ищем максимальный элемент в строке, мы должны обязательно запоминать координаты этого элемента, чтобы знать, для какого столбца проверять, является ли найденный элемент минимальным;

3) для поиска максимального элемента в строке целесообразно использовать цикл for, так как мы должны перебрать все элементы строки;

4) для написания эффективной программы операцию поиска минимального элемента в столбце следует заменить на операцию проверки, является ли данный элемент минимальным в столбце. Это позволит не выполнять лишних действий.

4. Задачи на использование метода введения дополнительных данных

На применение метода введения дополнительных данных существует достаточно много интересных и посильных школьникам задач. В использовании этого метода можно выделить задачи, решаемые методом подсчета и методом введения барьерных элементов.

4.1. Метод подсчета

30. Массив размерности n заполнен цифрами. Подсчитать, сколько раз встречается каждая цифра.

Решение. Для решения задачи методом подсчета введем дополнительный массив array [0..9] of word, в k-м элементе которого будем хранить информацию о том, сколько раз встречается цифра k в массиве.

const n = 10;
var a:array [1..n] of byte;
count:array [0..9] of word;
k:word;
begin
    {инициализация массива a}
    {обнуление массива счетчиков count}
    for k := 1 to n do
       inc(count[a[k]]); 
       {подсчет встречаемости цифр}
    for k := 0 to 9 do
    writeln(k, '-',count[k])
 end;

31. Массив размерности n заполнен целыми числами из диапазона от 20 до 55. Подсчитать, сколько раз встречается каждое число.

Решение. Текст программы отличается от текста программы предыдущей задачи только размерностью массива счетчиков count: array [20..55] of word.

32. Массив размерности n заполнен цифрами. Отсортировать его по возрастанию за один проход по массиву.

Решение. После подсчета встречаемости каждой цифры надо организовать заполнение исходного массива цифрами по возрастанию. Ниже приведен фрагмент программы формирования упорядоченного по возрастанию массива.

for i := 0 to 9 do
 begin
  k := 1;
   while k <= count[i] do
    begin
    a[k] := i
    inc(k)
   end
 end;

33 (Минимальное число, см. газету “Информатика” № 2/2008).

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

Пример: дано — 1513, получили — 1135.

Решение задачи приведено в том же номере газеты “Информатика”.

34. Массив размерности n заполнен строчными латинскими буквами. Подсчитать, сколько раз встречается каждая буква (аналогичная задача встречалась в ЕГЭ 2004 года).

Решение. Введем дополнительный массив count: array ['a'.. 'z'] of word, в k-м элементе которого будем хранить информацию о том, сколько раз встречается символ k в массиве.

const n = 30;
var a: array [1..n] of char;
count: array ['a'.. 'z'] of word;
i: word;
c:char;
begin
 {инициализация массива}
    for i := 1 to n do
    inc(count[a[i]]a);
    for c := 'a' to 'z' do
    writeln(c, '—',count[c]:3)
end.

35 (Палиндром, см. газету “Информатика” № 1/2008).

В массиве записан набор больших латинских букв (не обязательно различных). Требуется написать программу, которая из данных букв составит палиндром наибольшей длины, а если таких палиндромов несколько, то первый в алфавитном порядке. Для составления палиндромов можно переставлять буквы, а также удалять некоторые буквы.

Напомним, что палиндром — это строка, которая читается одинаково как справа налево, так и слева направо.

Решение задачи приведено в том же номере газеты “Информатика”.

36 (Шифровка, см. газету “Информатика” № 1/2008).

Мальчик Петя чрезвычайно увлекается различными шпионскими рассказами и недавно от чтения романов со стрельбой и погонями перешел к изучению серьезной литературы. Особенно его заинтересовал один из методов шифровки секретных сообщений, прочитанный им в брошюрке по криптографии “Библиотечка кровавого режима”.

Метод заключается в следующем: среди большого количества чисел спрятано то, которое несет секретную информацию, причем все числа встречаются трижды (или кратное трем число раз), кроме секретного числа, которое встречается некратное трем число раз.

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

Однако в реальности такой шифр легко взламывается компьютерной программой, которую вам предстоит написать.

Замечание. Решение этой задачи для целых чисел из диапазона 1 n 99 приведено в том же номере газеты “Информатика”.

4.2. Метод введения барьерных элементов

37. Массив размерности n заполнен словами, состоящими только из строчных латинских букв. Слова между собой разделены ровно одним пробелом. Подсчитать количество слов в массиве.

Решение. Подсчитывать количество слов будем в переменной count, а использование метода введения дополнительных данных состоит в следующем. Размерность исходного массива увеличим на 1. В (n + 1)-й элемент запишем пробел. Этот прием позволит нам все слова обрабатывать по одному и тому же алгоритму, иначе последнее слово (не оканчивающееся пробелом) пришлось бы обрабатывать отдельно. Смотри текст программы задачи 38.

38. Массив размерности n заполнен словами, состоящими только из строчных латинских букв. Слова между собой разделятся ровно одним пробелом. Вывести на экран длину самого длинного слова.

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

const n = 10;
var a:array [1..n] of char;
k, len, maxlen:word;
begin
  maxlen := 0;
  k := 1;
  len := 0;
  while (a[k]<> ' ') and (k <= n) do 
    begin
    inc(k);
    inc(len)
    end;
  if len > maxlen then 
    begin
    maxlen := len;
    ken := 0
    end;
  while (a[k] = ' ') and (k <= n) do
    inc(k)
  end;
writeln(maxlen)
end. 

5. Приемы решения задач из ЕГЭ по информатике

39. Задание С2 из ЕГЭ по информатике 2006 года

Опишите на русском языке или на одном из языков программирования алгоритм поиска второго по величине (т.е. следующего по величине за максимальным) элемента в числовом массиве из 30 различных элементов.

Указание. Решение этой задачи полностью основано на знании базового алгоритма поиска двух максимальных (минимальных) значений в массиве. Смотри задачу 17.

40. Задание С4 из ЕГЭ по информатике 2006 года

Вступительные испытания в некоторый вуз состоят из трех экзаменов: математика (максимальный балл — 9), информатика (максимальный балл — 9), литература (максимальный балл — 5). На вход программе подаются сведения о сдаче этих экзаменов абитуриентами. В первой строке вводится количество абитуриентов N, во второй — количество мест K (K < N), на которые эти абитуриенты претендуют. Каждая из следующих N строк имеет следующий формат: <Фамилия> <оценка1> <оценка2> <оценка3>, где <Фамилия> — строка, состоящая не более, чем из 20 символов, оценки — числа от 0 до максимальной оценки по предмету соответственно. (Ноль ставится в случае, если экзамен не сдавался, например, после полученной на предыдущем экзамене двойки. Все баллы, большие 2, считаются удовлетворительными.) Пример входных строк:

Иванов 8 9 3

Петров 2 0 0

Требуется написать программу на языке Паскаль или Бейсик, которая определяла бы по имеющимся данным количество абитуриентов, набравших полупроходной балл в данный вуз, или сообщала, что такой балл отсутствует. (Полупроходным называется такой балл, что лишь часть абитуриентов, набравших такой балл и не получивших ни одной неудовлетворительной оценки, попадает в K лучших, которые должны быть зачислены на 1-й курс.) Считается, что абитуриенты, получившие только удовлетворительные оценки, обязательно присутствуют.

Решение. Алгоритм решения этой задачи основан на использовании метода подсчета. Введем массив m:array[0..23] of integer, в p-м элементе которого будем подсчитывать количество абитуриентов, набравших p баллов. Если абитуриент получил хотя бы одну двойку, то удобно считать, что его общий балл равен 0.

Заполнять массив m будем в процессе считывания данных, сами данные хранить не будем. Заметим, что сумма всех элементов массива m равна n — числу абитуриентов. Взять на первый курс могут только k человек. Здесь возможна ситуация, что есть группа абитуриентов, набравших одинаковое количество баллов p, но если их всех зачислить на первый курс вместе с абитуриентами, набравшими больше чем p баллов, то мест не хватит (это и есть полупроходной балл).

Для определения полупроходного балла будем подсчитывать сумму элементов этого массива (т.е. число абитуриентов), начиная с 23-го, до тех пор, пока она не превосходит K (алгоритм подсчета суммы элементов массива также относится к базовым). Индекс первого элемента массива, который не войдет в эту сумму и будет искомым полупроходным баллом. Если проходной балл набрали ровно K абитуриентов, то программа сообщает, что полупроходной балл отсутствует.

Для правильного решения задачи надо грамотно организовать считывание данных.

Пример правильной и эффективной программы на языке Паскаль взят с http://ege.edu.ru:

var m:array[0..23] of integer;
c:char;
i, K, N, S, m1, m2, m3:integer;
begin
readln(N); readln(K);
 for i := 0 to 23 do m[i] := 0;
  for i := 1 to N do
    begin
    repeat
    read(c)
    until c=' '; {считана фамилия абитуриента}
    readln(m1, m2, m3);
      if (m1 < 3)or(m2 < 3)or(m3 < 3) then 
       s := 0
      else s := m1 + m2 + m3;
       m[s] := m[s] + 1 
       {учитываем абитуриента в элементе
       массива, соответствующем его баллам}
      end;
    s := m[23]; i := 23;
    while s + m[i - 1] <= K and (i > 9) 
     {9 — минимально возможный балл} do
      begin
      i := i - 1;
      s := s + m[i]
      end;
    if (s < K)and(i > 9) then
    writeln('полупроходной балл набрали', m[i - 1],
    ' человек')
    else writeln('полупроходной балл
    отсутствует');
 readln
end.

41. Задание С3 из ЕГЭ по информатике 2005 года

Опишите на русском языке или одном из языков программирования алгоритм подсчета числа элементов, равных максимальному в числовом массиве из 30 элементов.

Решение. Алгоритм решения задачи основан на применении базового алгоритма нахождения максимального элемента в массиве. Смотри задачи 16 и 17. Заметим, что задачу можно решить за 1 проход по массиву.

42. Задание С2 из ЕГЭ по информатике 2007 года

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

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

Пример правильной и эффективной программы на языке Паскаль взят с http://ege.edu.ru:

const N = 30;
var a:array[1..N] of integer;
MaxSum, MaxNum, i: integer;
begin
  MaxNum := 1;
  MaxSum := a[1] + a[2];
   for i := 2 to N – 1 do 
    begin
    if a[i] + a[i + 1] > MaxSum then 
      begin
      MaxNum := i;
      MaxSum := a[i] + a[i + 1]
      end
    end;
 writeln(MaxNum)
end.

43. Задание С4 из ЕГЭ по информатике 2007 года

На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат: <Фамилия> <Имя> <оценки>, где <Фамилия> — строка, состоящая не более чем из 20 символов, <Имя> — строка, состоящая не более чем из 15 символов, <оценки> — через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки:

Иванов Петр 4 5 4

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

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

Для решения задачи нам необходимо запомнить все вводимые данные, так как эти данные мы должны обрабатывать два раза: первый раз для нахождения трех максимальных значений, а второй раз — для вывода фамилий учащихся, средний балл которых равен или выше третьему максимальному значению.

Отметим, что для более “красивого” решения в программе целесообразно использовать массив типа record:

end;

Подборки задач на массивы вы можете также найти на следующих сайтах:

http://olympiads.ru — здесь вы можете найти материалы различных олимпиад по информатике, а также задачи, статьи, ссылки на литературу, которая может помочь в изучении или преподавании информатики;

http://informatics.mccme.ru/ — сайт дистанционной подготовки по информатике Московского центра непрерывного математического образования.