ГДЗ: Параграф § 8 / Информатика 11 класс

Неоднократный просмотр массива требуется, поскольку многие алгоритмы, такие как сортировка (например, «пузырьком» или выбором) или сложные операции поиска и проверки, должны работать с элементами массива циклически. В сортировке, например, необходимо сравнить и, возможно, обменять пары элементов множество раз до достижения упорядоченности.

Примеры задач поиска информации в больших массивах данных включают:

• Поиск конкретного товара в каталоге интернет-магазина.
• Поиск необходимого рейса в расписании транспорта.
• Нахождение максимальной или минимальной температуры за период времени.
• Поиск всех сотрудников, удовлетворяющих определенным критериям (например, стаж > 5 лет).

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

Замена значения элемента с индексом \( k \) (например, \( a[k] := \text{новое значение} \)) изменяет только значение одного элемента и не меняет размерность массива.

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

Суть «пузырьковой» сортировки заключается в последовательном сравнении и обмене соседних элементов. В результате каждой итерации максимальный (или минимальный) элемент «всплывает» («тонет») на свое правильное место в массиве. Процесс повторяется, каждый раз уменьшая размерность несортированной части массива, пока он не будет отсортирован.

Общая сложность алгоритма в худшем и среднем случаях сопоставима с \( n^2 \) (квадратичная), где \( n \) — количество элементов.

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

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

1. Анализ кода и задачи:

Программа предназначена для вычисления суммы элементов массива \( a[1..n] \). Фрагмент кода:

// ...
const n = 10;
var a: array [1..n] of integer; s, i: integer;
begin
  s := 0;
  for i := 1 to n do
  begin
    readln(a[i]); // Ввод элемента
    s := s + 1;  // Ошибка здесь!
  end;
  writeln('s=', s)
end.

2. Ошибка:

Вместо того, чтобы добавлять значение элемента \( a[i] \) к сумме \( s \) (то есть \( s := s + a[i] \)), программист ошибочно инкрементирует счетчик \( s \) на 1 (\( s := s + 1 \)). В итоге программа будет считать количество элементов (равное \( n \)), а не их сумму.

3. Результат выполнения с числами 1, -2, 3, ... -10:

Счетчик \( s \) будет увеличиваться на 1 на каждой итерации цикла 10 раз (\( n=10 \)). Введенные числа не влияют на значение \( s \). Результат будет \( s = 10 \).

1. Анализ кода и задачи:

Программа предназначена для вычисления произведения элементов массива \( a[1..n] \). Фрагмент кода:

// ...
var a: array [1..n] of integer; p, i: integer;
begin
  p := 0;  // Ошибка здесь!
  for i := 1 to n do
  begin
    readln(a[i]);
    p := p * a[i];
  end;
  writeln('p=', p)
end.

2. Ошибка:

Переменная \( p \), предназначенная для хранения произведения, инициализирована значением \( 0 \) (\( p := 0 \)). При умножении любого числа на ноль результат всегда будет ноль. Для корректного расчета произведения начальное значение должно быть равно 1 (\( p := 1 \)).

3. Результат выполнения:

Независимо от значений, введенных в массив \( a \), результат произведения \( p \) всегда будет равен 0.

Для формирования массива цифр числа \( n \) необходимо последовательно выделять последнюю цифру с помощью операции остатка от деления \( ( n \text{ mod } 10 ) \) и затем уменьшать число \( ( n := n \text{ div } 10 ) \) до нуля. Массив придется заполнять в обратном порядке.

program digit\_analysis;
const MAX\_DIGITS = 5; // Для числа до 32000 (5 разрядов)
var n, temp\_n, i, count, sum, prod, max\_d, min\_d: integer;
    digits: array [1..MAX\_DIGITS] of integer;
begin
  write('Введите натуральное число n (<= 32000): ');
  readln(n);
  
  temp\_n := n;
  count := 0;
  sum := 0;
  prod := 1;
  max\_d := 0; // Цифры от 0 до 9
  min\_d := 9;
  
  // 1. Формирование массива, подсчет суммы и произведения
  while temp\_n > 0 do
  begin
    count := count + 1;
    digits[count] := temp\_n mod 10; // Получаем последнюю цифру
    temp\_n := temp\_n div 10; // Уменьшаем число
    
    // 2. Нахождение max и min цифр
    if digits[count] > max\_d then
      max\_d := digits[count];
    if digits[count] < min\_d then
      min\_d := digits[count];
      
    // 3. Сумма и произведение
    sum := sum + digits[count];
    prod := prod * digits[count];
  end;
  
  // Вывод результата
  writeln('Цифры числа (в обратном порядке): ');
  for i := count downto 1 do
    write(digits[i], ' ');
  writeln;
  
  writeln('Наибольшая цифра: ', max\_d);
  writeln('Наименьшая цифра: ', min\_d);
  writeln('Сумма цифр: ', sum);
  writeln('Произведение цифр: ', prod);
end.

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

Алгоритм сортировки выбором для банок:

1. Считаем первую банку \( B_1 \) самой легкой в неупорядоченной части.
2. Просматриваем все остальные банки \( B_i \) в неупорядоченной части, сравнивая их с текущей самой легкой банкой \( B_{\min} \) с помощью чашечных весов.
3. Если \( B_i \) легче, чем \( B_{\min} \), то \( B_i \) становится новой самой легкой банкой \( B_{\min} \).
4. После того как вся неупорядоченная часть просмотрена, меняем местами текущую банку \( B_{\min} \) и первую банку \( B_{first} \) в неупорядоченной части.
5. Повторяем процесс, начиная с пункта 1, для оставшейся (уменьшенной) неупорядоченной части, пока все банки не будут отсортированы.

Алгоритм инициализирует max и min первым элементом массива \( a[1] \). Затем в цикле, начиная со второго элемента \( ( i = 2 ) \), каждый элемент \( a[i] \) сравнивается как с текущим min, так и с текущим max.

program min\_max\_search;
const n = 7;
var a: array [1..n] of integer;
    i, max\_val, min\_val: integer;
begin
  // Пример массива из задания 6: [10, 12, 5, 8, 4, 15, 20]
  a[1]:=10; a[2]:=12; a[3]:=5; a[4]:=8; a[5]:=4; a[6]:=15; a[7]:=20; 
  
  // Инициализация
  max\_val := a[1];
  min\_val := a[1];
  
  // Цикл для одновременного поиска
  for i := 2 to n do
  begin
    if a[i] > max\_val then
      max\_val := a[i];
    if a[i] < min\_val then
      min\_val := a[i];
  end;
  
  writeln('Максимальное значение: ', max\_val);
  writeln('Минимальное значение: ', min\_val);
end.

Данный фрагмент кода реализует операцию удаления элемента с индексом \( k=4 \). Цикл выполняется для \( i \) от \( 4 \) до \( 6 \) (\( n-1 \)). Элементы с индекса \( i+1 \) сдвигаются на позицию \( i \).

• \( i=4 \): \( a[4] := a[5] \), т.е. \( a[4] := 4 \).
• \( i=5 \): \( a[5] := a[6] \), т.е. \( a[5] := 15 \).
• \( i=6 \): \( a[6] := a[7] \), т.е. \( a[6] := 20 \).

Элемент \( a[7] \) (со значением 20) остается в массиве, но теперь он находится на позиции \( a[6] \). Последний элемент \( a[7] \) теперь содержит неактуальное (старое) значение. Новый массив с шестью значимыми элементами: \( [10, 12, 5, 4, 15, 20] \).

Данный фрагмент кода реализует операцию перестановки всех элементов массива в обратном порядке. Цикл выполняется для \( i \) от \( 1 \) до \( 3 \) (\( n \text{ div } 2 \)), меняя местами симметричные пары элементов \( a[i] \) и \( a[n-i+1] \) с использованием вспомогательной переменной \( r \).

• \( i=1 \): Обмен \( a[1] \) (10) и \( a[7] \) (20). Массив: \( [20, 12, 5, 8, 4, 15, 10] \).
• \( i=2 \): Обмен \( a[2] \) (12) и \( a[6] \) (15). Массив: \( [20, 15, 5, 8, 4, 12, 10] \).
• \( i=3 \): Обмен \( a[3] \) (5) и \( a[5] \) (4). Массив: \( [20, 15, 4, 8, 5, 12, 10] \).

Элемент \( a[4] \) (8) остается на своем месте, так как массив имеет нечетное число элементов.

Конечный массив: \( [20, 15, 4, 8, 5, 12, 10] \).

Программа инициализирует max1 := a[1] = 1 и max2 := a[2] = 2. Цикл начинается с \( i=2 \):

• \( i=2 \): \( a[2]=2 \). \( 2 > max1 \) (1). \( \text{max}2 := \text{max}1 = 1 \); \( \text{max}1 := a[2] = 2 \). Текущие: \( \text{max}1=2, \text{max}2=1 \).
• \( i=3 \): \( a[3]=6 \). \( 6 > max1 \) (2). \( \text{max}2 := \text{max}1 = 2 \); \( \text{max}1 := a[3] = 6 \). Текущие: \( \text{max}1=6, \text{max}2=2 \).
• \( i=4 \): \( a[4]=4 \). \( 4 \) не \(> max1 \) (6). \( 4 > max2 \) (2). \( \text{max}2 := a[4] = 4 \). Текущие: \( \text{max}1=6, \text{max}2=4 \).
• \( i=5 \): \( a[5]=6 \). \( 6 \) не \(> max1 \) (6). \( 6 \) не \(> max2 \) (4). Действий нет. Текущие: \( \text{max}1=6, \text{max}2=4 \).

Программа выведет: max1= 6 max2= 4. (Обратите внимание: правильные максимальные значения — 6 и 6, но алгоритм нашел только 6 и 4.)