Гладков_Кулютникова Информатика

73 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

Вариант 2. Используется сортировка без вспомогательного массива, но сортируются только отрицательные элементы.

mas[i] := mas[j]; mas[j] := r

end; for i := 1 to n do write (mas[i], ‘ ‘);

end.

Вопросы. 1. Какой алгоритм сортировки используется в этой программе? 2. Указать диапазон чисел, которыми заполняется массив.

Задача. Известны расстояния от дома любителя плова до любой из n существующей в городе П. закусочной. Известна цена плова в каждой закусочной. Проверьте утверждение любителя плова: “ Чем дальше закусочная, тем меньше цена на плов”.

Решение. Исходные данные представим в виде двумерного массива из n столбцов (количество закусочных) и двух строк: первая строка - расстояние до закусочной, вторая - стоимость плова в этой закусочной. Далее необходимо упорядочить двумерный массив в порядке возрастания элементов первой строки, т.е. в порядке возрастания расстояний. Если после этого преобразования, вторая строка будет упорядочена по убыванию, значит, любитель плова прав.

program task;

const n = 20; {количество закусочных}

var a: array [1..2, 1..n] of integer; {исходный массив}

74 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

end;

{упорядочивание массива} for i := 1 to n - 1 do

begin k := i;

for j := i + 1 to n do

if a[1, j] < a[1, k] then k := j;

x := a[1, i]; a[1, i] := a[1, k]; a[1, k] := x; x := a[2, i]; a[2, i] := a[2, k]; a[2, k] := x; end;

{проверяем, упорядочена ли вторая строка по убыванию} i := 1; f := true; {считаем, что любитель плова прав}

while (i <= n - 1) and f do {пока не проверили все закусочные и любитель

if f then writeln (‘любитель плова прав’) else writeln (‘любитель плова не прав’);

end.

Тест 1. Расстояние Стоимость плова

После упорядочивания:

Тест 2. Расстояние Стоимость плова

После упорядочивания:

Упражнения.

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

2.Известны цены на землянику на n рынках Перми. Известно расстояние от дома покупателя до каждого рынка. Найдите номер рынка, на котором можно дешевле всего купить ягоды, если покупатель согласен пройти расстояние не более r км.

3.Имеется n озер. Для каждого озера известно среднее количество рыбы в кг, которую можно выловить за день рыбалки. Известны расстояния от каждого озера до города П. Укажите озеро, где рыбак может поймать больше всего рыбы, если он согласен пройти до места рыбалки не менее p км, но не более r км.

4.В городе П. имеется n гостиниц известной вместимости. Известны расстояния от каждой гостиницы до вокзала. Укажите номера гостиниц, в которых можно разместить не менее R гостей так, чтобы они находились как можно ближе к вокзалу.

ДВУМЕРНЫЕ МАССИВЫ

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

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

75 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

var a: array [1..n] of array [1..m] of real; {массив а, состоящий из n элементов каждый элемент которого - одномерный массив из m действительных чисел}

В этом случае обратиться к элементу массива можно следующим образом: a[i][j]. Чаще используется следующее описание двумерного массива:

var a: array [1..n, 1..m] of real;

А к элементу массива обращаются следующим образом: a[i, j], где i - номер строки, j - номер столбца.

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

var a: array [1..8,‘a’..’h’] of boolean;

Количество элементов двумерного массива определяется путем перемножения количества столбцов на количество строк.

ВПаскале разрешены многомерные массивы. Глубина вложенности массивов произвольная, поэтому количество элементов в списке индексов (размерность массива) не ограничена, однако суммарная длина внутреннего представления любого массива не может быть больше 65 520 байт.

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

Обрабатывать элементы двумерного массива можно как по строкам, так и по столбцам.

В первом варианте перебираться будут следующие элементы (для случая n = 3, m = 4): a[1, 1], a[1, 2], a[1, 3], a[1, 4], a[2, 1], a[2, 2], a[2, 3], a[2, 4], a[3,1], a[3, 2], a[3, 3], a[3, 4], a[4, 1], a[4, 2], a[4, 3], a[4, 4].

Во втором варианте: a[1, 1], a[2, 1], a[3, 1], a[4, 1], a[1, 2], a[2, 2], a[3, 2], a[4, 2], a[1,3],

a[2, 3], a[3, 3], a[4, 3], a[1, 4], a[2, 4], a[3, 4], a[4, 4].

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

a11 a12 a13 a14 a15 Элементы: а11, а22, а33, а44, а55 составляют главную диагональ. a21 a22 a23 a24 a25 Для них справедливо равенство номеров строки и столбца (i=j).

a31 a32 a33 a34 a35 Элементы: а51, а42, а33, а24, а15 составляют побочную диагональ. a41 a42 a43 a44 a45 Для них справедливо равенство i+j=n+1.

a51 a52 a53 a54 a55

Для элементов, расположенных выше главной диагонали, справедливо i < j, для элементов ниже главной диагонали - i > j. Для элементов, расположеных на линиях, параллельных главной диагонали, справедливо следующее соотношение: |i-j| = k, где k - номер линии по отношению к главной диагонали.

Для элементов, расположенных выше побочной диагонали, справедливо: i+j<n+1, а для элементов ниже побочной диагонали: i+j>n+1. Индексы элементов, расположенных на линиях, параллельных побочной диагонали, удовлетворяют соотношению: 2 ≤ i+j ≤ 2*n.

76 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

Решение.

Вариант 1. Сначала необходимо весь массив заполнить нулями, затем первую и последнюю строку, первый и последний столбец заполнить единицами.

В варианте 2 заполняются единицами элементы главной и побочной диагонали. for i := 1 to n do

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

for i := 1 to n do

(i= j ) or (i + j = n + 1) then a[i, j] := 1;

В варианте 3 можно выделить два треугольника: верхний и нижний. В верхнем треугольнике с увеличением номера строки уменьшается количество элементов, равных 1, причем для 2-ой строки единицами заполняются элементы со второго до n - 1, т.е. каждый раз индекс столбца слева и справа уменьшается на 1. В нижнем треугольнике при уменьшении номера строки уменьшается индекс столбца справа и слева на 1.

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

for i := 1 to n div 2 do for j := i to n - i + 1 do a[i, j] := 1;

for i := n downto n div 2 + 1 do for j := n - i + 1 to i do

a[i, j] := 1;

В варианте 4 также рассмотрим два треугольника. В верхнем треугольнике при увеличении номера строки количество столбцов должно увеличиваться влево и вправо на 1. В нижнем треугольнике - уменьшаться.

77 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

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

for i := 1 to n do begin

writeln;

for j := 1 to m do write(a[i, j], ‘ ‘);

end;

Задача 2. Дан двумерный массив n×m. Сформируйте одномерный массив, содержащий количество нулей: а) в соответствующей строке двумерного массива; б) в соответствующем столбце массива.

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

Вариант а).

const nn = 20; mm = 30;

var a: array [1..nn, 1..mm] of real;

b: array [1..nn] of integer; {количество нулей в соответствующей строке}

i, j, n, m: integer; begin

write (‘задайте количество строк и столбцов’); readln (n, m);

writeln (‘заполните массив’); for i := 1 to n do

for j := 1 to m do read (a[i, j]);

for i := 1 to n do

begin b[i] := 0; {количество нулей в i-ой строке равно нулю} for j := 1 to m do

if a[i, j] = 0 then b[i] := b[i] + 1; end;

for i := 1 to n do write (b[i], ‘ ‘);

end.

Вариант б).

const nn = 20; mm = 30;

var a: array [1..nn, 1..mm] of real;

b: array [1..nn] of integer; {количество нулей в соответствующей строке}

i, j, n, m: integer; begin

write (‘задайте количество строк и столбцов’);

78 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

readln (n, m);

writeln (‘заполните массив’); for i := 1 to n do

for j := 1 to m do read (a[i, j]);

for j := 1 to m do

begin b[j] := 0; {количество нулей в j-ом столбце равно нулю} for i := 1 to n do

if a[i, j] = 0 then b[i] := b[i] + 1; end;

for i := 1 to m do write (b[i], ‘ ‘);

end.

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

Решение. Сначала необходимо найти максимальный элемент, а точнее его координаты по i и по j, назовем их соответственно imax и jmax. Затем необходимо сначала поменять местами первую и imax-ую строки, затем первый и jmax-ый столбцы.

const nn = 20; mm = 30;

var a: array [1..nn, 1..mm] of real; i, j, imax, jmax, n, m: integer;

r: real; begin

write (‘задайте количество строк и столбцов’); readln (n, m);

writeln (‘заполните массив’); for i := 1 to n do

for j := 1 to m do read (a[i, j]);

imax := 1; jmax := 1;

for i := 1 to n do for j := 1 to m do

if a[i, j] > a[imax, jmax]

then begin imax := i; jmax := j end;

for j := 1 to m do {меняются местами 1-ая и imax-ая строки} begin r := a[1, j];

a[1, j] := a[imax, j]; a[imax, j] := r

end;

for i := 1 to n do {меняются местами 1-ый и jmax-ый столбцы} begin r := a[i, 1];

a[i, 1] := a[i, jmax]; a[i, jmax] := r

end;

for i := 1 to n do begin

writeln;

for j := 1 to m do write (a[i, j], ‘ ‘);

80 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

tipe arr = array [fi...if] of integer; var a: {массив} fi;

i, n, j: int{индексы и количество элементов}eger; begin write (‘Введите’, n);

read (n);

for i := 1 to n - 1 do begin read (a[i])

for j := i + 1 downto n do if a(i) > a(j) and i > j then a(i) = a(j);

i := if;

while i <= n do write (a[i], ‘ ‘);

end

Все ли найденные Вами ошибки обнаружит транслятор?

9. Восстановите пропущенные операторы и элементы выражений Паскальпрограммы (они обозначены ?) так, чтобы она решала задачу: “ Нечетные строки матрицы заменить вектором”. Опишите назначение всех переменных. Сколько строк будет выведено на экран по окончании работы программы?

end;

end.

ОБРАБОТКА СТРОК

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

Символьным константам можно присваивать имена. const st = ‘строка’;

81 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

Символьные переменные описываются в разделе описания переменных с описателем string.

var st1, st2: string [10];

st3: string;

Переменные st1, st2 могут содержать до 10 символов, причем в самом начале областей st1, st2, в отличие от одномерного символьного массива, помещается дополнительная ячейка st1[0], st2[0], в которой хранится текущее значение строки, доступное программисту. Переменная st3 занимает max+1 байт, где max - максимальное число символов в строке, которое равно 255 символам.

Пример.

var st: string [10];

a: array [0..10] of char;

Рассмотрим, как будет размещена строка ‘program’ в строке st

Клюбому символу в строке можно обратиться точно так же, как к элементу одномерного массива, т.е. указав имя строки и индекс символа в этой строке. Например, st[5] = ‘r’.При этом для элемента строки разрешены те же операции и функции, что и для типа char.

Строки вводят и выводят с помощью операторов readln, writeln без организации циклов.

Строки можно сравнивать. Сравнение осуществляется лексикографически по коду, т.е. последовательно слева направо сравниваются первые символы, вторые и т.д. до несовпадающего символа, какой из несовпавших символов больше, та строка и больше. Например, ‘рак’ > ‘ мак’; ‘ раки’ > ‘ рак’. Две строки равны, если они равны по длине и совпадают посимвольно.

Кстрокам можно применять операцию сцепления “+”. Например,

st1 := ‘шок’; st2 := ‘лад’;

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

функции - целое число, которое определяет номер первого символа, с которого начинается