Лекция 3. Массивы и матрицы. Итерационные циклы. (Воробьева И.А. - Информатика. Язык Паскаль), страница 2

«Если над побочной диагональю матрицы нет элементов,значение которых лежит между числами y и z» – это, по сути, или найтихотя бы один элемент между числами y и z (задача 1) или проверить,что все элементы НЕ лежат между числами y и z (задача 2).Какой вопрос по уточнению задачи должен возникнуть3?23Вопрос «строго или не строго упорядочены», т.е. если элементы равны – считаем ли мы их упорядоченными или нет.Вопрос «интервал (y, z) или отрезок [y, z]», т.е. строгое или не строгое будет сравнение.89Воробьева И.А. «Информатика.

Язык Паскаль»Иногда формулировки не удобны, содержат двойныеотрицания.Пример 4.3. «Если в матрице нет элементов, значение которыхнеотрицательны… (т.е. ≥ 0)» – это, по сути, найти хотя бы одиннеотрицательный (≥ 0) элемент (задача 1) или проверить, что всеэлементы отрицательны (< 0) (задача 2).Рекомендация.

Переформулируйте задачу так, как лично вам удобнееее решать. Избавляйтесь от отрицаний, особенно двойных. Но будьтеаккуратны, чтобы не совершить ошибку на этом этапе иначе будете сразурешать какую-то другую задачу. Не ту, что была задана.Протестируйте себя на реальном примере, что «новая формулировка»после поиска и установки флага-условия, приводит к тому же результату,что и исходная. Не забывайте, что формулировки «задачи_1» и «задачи_2» – являются взаимообратными.

Это означает, что если взадаче_1 положительный ответ приводит к действию_1, аотрицательный – к действию_2, то в задаче_2 положительный ответприводит к действию_2, а отрицательный – к действию_1.Продемонстрируем сказанное для задачи из примера 4.3.ИСХОДНАЯ ЗАДАЧА«нет ≥0»-+ДЕЙСТВИЕ 1ДЕЙСТВИЕ 2ЗАДАЧА_1«есть ≥0»+ДЕЙСТВИЕ 2ЗАДАЧА_2 ≡ ИСХ. ЗАДАЧА-«все < 0»≡ «нет ≥0»-+ДЕЙСТВИЕ 1ДЕЙСТВИЕ 1ДЕЙСТВИЕ 2910Воробьева И.А. «Информатика. Язык Паскаль»Приведем фрагмент кода для задачи_1 и задачи_2 из примера 4.3 сиспользованием флага для досрочного выхода из матрицы.VAR// ОБЩАЯ ЧАСТЬ ДЛЯ ОБЕИХ ФОРМУЛИРОВОКn, m, i, j: byte;// размерность матрицы и индексыFlg: boolen;// флаг выполнения условия поискаA: array[1..10, 1..10] of real; // матрицаBEGIN… // ввод n и m (от 1 до 10), матрицы A из вещественных чиселFlg:= FALSE;i:= 1; j:= 1;// считаем, что ПОКА НЕ НАШЛИ элемента « ≥ 0»// начальное значение индексовwhile ( i <= n) AND NOT flg do beginwhile ( j <= m) AND NOT flg do beginif A[i, j] >= 0 thenFlg:= TRUE; // нашли « ≥ 0» → больше искать смысла нетinc(j);end;inc(i);end;if Flg then… Действие 2…else… Действие 1… ;END.Flg:= TRUE;i:= 1; j:= 1;// считаем, что ВСЕ элементы отрицательны// начальное значение индексовwhile ( i <= n) AND flg do beginwhile ( j <= m) AND flg do beginif A[i, j] >= 0 thenFlg:= FALSE; // НЕ ВСЕ «< 0» → больше искать смысла нетinc(j);end;inc(i);end;if Flg then … Действие 1…else… Действие 2… ;END.1011Воробьева И.А.

«Информатика. Язык Паскаль»4.4. Задача с досрочным выходом из поиска в матрице.Пример решенияЗадачаДана целочисленная матрица А(n,m). Проверить, есть ли четныеэлементы в верхней половине матрицы. Если да, то поменять местамилевую и правую половины матрицы «зеркально». В противном случаесообщить, что «Четных элементов нет».Уточнения задачи1 Если n нечетное, то как будем считать верхнюю половину? В этом случае будем считать входные данные некорректными – невсякие задачи решаются для любых входных данных.

Онекорректности выведем сообщение «n – должно быть четным».2 Ноль четное число? Да, ноль четное число, по определению, но всегда полезно об этомдополнительно упомянуть в задаче.3 Число столбцов может быть нечетным? m может быть равно единице? Да. Если m – нечетное число, тогда 1-й столбец меняем местами с mстолбцом, 2-й с (m-1)-м и т.д., а средний+12– столбец4 останетсянеизменным. m может быть равно единице.4Средний столбец в матрице из m столбцов:−12+1=+121112Воробьева И.А. «Информатика.

Язык Паскаль»Данные, которые уже заданы и которые потребуютсяВх.: n – максимальное значение индексов строк , 2 ≤ ≤ 10, − четноm – максимальное значение индексов строк , 1 ≤ ≤ 10А – матрица из целочисленных элементов, причем значенияэлементов: | | ≤ 20;Промежуточные:i – индекс строк,1 ≤ ≤ ;j – индекс столбцов, 1 ≤ ≤ ;Midi, Midj – целая часть от деления числа строк/столбцов на два,диапазон: 1 ≤ , ≤ 5;Flg – флаг проверки условия (Flg =TRUE – есть четные элементы);Вых.: А – измененная матрица из целочисленных элементов, причемзначения элементов: | | ≤ 20;ИЛИ Сообщение-альтернатива, Not_Even: «Четных элементов нет».ИЛИ Сообщение-аномалия, ERR_n: «n – должно быть четным».1213Воробьева И.А.

«Информатика. Язык Паскаль»Блок-схема (алгоритм) решения задачиРасписываем алгоритм нисходящим способом, не углубляясь вподробности подзадач. Это «нулевой уровень» – каркас взаимодействияподзадач, основные логические связи. Умение выделять подзадачи снеобходимыми им входными/выходными данными – очень важноеумение в решении любых задач, не только в программировании.началоввод n−n – чет. И n >2+ввод m, A«ERR_n»вывод n, m, AMidi = n DIV 2;Midj = m DIV 2Вх.: Midi, m, AПРОВЕРКАЭЛЕМЕНТОВ НАЧЕТНОСТЬ−Вых.: FlgFlg=TRUEВх.: n, Midj, A+ОБМЕН ЭЛЕМЕНТОВМАТРИЦЫВых.: A«Not_Even»вывод Aконец1314Воробьева И.А. «Информатика.

Язык Паскаль»Следующее важное умение, не пытаться написать код решениязадачи в лоб и сразу весь, а написать только то, что указано в блок-схеме«нулевого уровня». Все, что скрыто в подзадачах, можно спокойнозаменить так называемыми заглушками – имитацией вычисленногорезультата.Program Lab2;CONSTnmax=10; mmax=10;VARn, m, i, j: byte;// размерность матрицы и индексыFlg: boolen;// флаг выполнения условия поискаA: array[1.. nmax, 1.. nmax] of integer; // матрицаMidi, Midj: byte;// условная середина размерности матрицыBEGINwriteln(‘Введите n’);readln(n);if (n MOD 2 <> 0) OR (n < 2) OR (n > nmax) thenwrite(‘n – должно быть четным , >1 и <11’)// Аномалияelse begin// ввод m (от 1 до 10), матрицы A (проверки m нет, что плохо)writeln(‘Введите m’);readln(m);FOR i:=1 TO n DO BeginFOR j:=1 TO m DOread ( A[i, j] );// считываем первую строкуreadl;// переходим на следующую строкуend;// вывод n, m и матрицы A проводим ОТДЕЛЬНО!writeln(‘Размерность матрицы (’, n:3, ‘,’ , m:3, ‘)’ );FOR i:=1 TO n DO BeginFOR i:=1 TO m DOwrite ( A[i, j]:4, ‘,’ );// выводим первую строкуwriteln;// переходим на следующую строкуend;1415Воробьева И.А.

«Информатика. Язык Паскаль»// Вычисление границ для циклов заранее еще один моментнаписания эффективного кода. Сделаем это.Midi:= n DIV 2; // целая часть от деления числа строк на дваMidj:= m DIV 2; // целая часть от деления числа столбцов на два// Первая заглушка: результат ее работы – это флаг FlgFlg:= TRUE;// для проверки одной ветки нулевого уровня// Flg:= FALSE; // для проверки другой ветки нулевого уровня надобудет снять символы комментирования «//»ПОДЗАДАЧА 1if Flg then Begin// Вторая заглушка: результат ее работы – это измененнаяматрицаA[1,1]:= - A[1,1];// изменим любой элемент матрицы, просто,// чтобы она измениласьПОДЗАДАЧА 2// вывод измененной матрицы AFOR i:=1 TO n DO BeginFOR i:=1 TO m DOwrite ( A[i, j]:4, ‘,’ ); // выводим первую строкуwriteln;// переходим на следующую строкуend;End elsewrite(‘n – должно быть четным , >1 и <11’);Альтернативаend;//END.Если на этом этапе все работает хорошо, только тогда имеет смыслрешать подзадачи.

Раскроем код заглушек.Если пренебречь этой1516Воробьева И.А. «Информатика. Язык Паскаль»рекомендацией и пытаться всю задачу написать сразу, то этап отладкикода займет гораздо больше времени.// ПРОВЕРКА ВЕРХНЕЙ ПОЛОВИНЫ МАТРИЦЫ НА ЧЕТНОСТЬ ЕЕЭЛЕМЕНТОВFlg:= FALSE;i:= 1; j:= 1;// считаем, что ПОКА НЕ НАШЛИ четного элемента// начальное значение индексовwhile ( i <= Midi) AND NOT Flg do beginwhile ( j <= m) AND NOT Flg do beginif (A[i, j] MOD 2) = 0 thenFlg:= TRUE; // нашли четный → больше искать смысла нетinc(j);end;inc(i);ПОДЗАДАЧА 1end;Обратите внимание: инициализация флага и счетчиков происходит не где-то в началевсей программы, а именно там, где решается подзадача; граница Midi просчитана заранее, а не вычисляется КАЖДЫЙ раз наочередном шаге цикла.

Ведь можно было записать и такwhile ( i <= n DIV 2) AND NOT Flg do это допустимо для матрицыиз 10-ти элементов, но всегда надо писать эффективное решение для«большой задачи», например, для n=10 000 и больше.// ОБМЕН ЭЛЕМЕНТОВ СТОЛБЦОВ МАТРИЦЫ ОТНОСИТЕЛЬНОСЕРЕДИНЫi:= 1; j:= 1;// начальное значение индексов задаем еще разwhile ( i <= n) AND NOT Flg do beginwhile ( j <= Midj) AND NOT Flg do begin// !!! операция определена только для целых типов// А=A xor B; B=A xor B; A=A xor BA[i,j]:=A[i,j] XOR A[i,m-j+1];A[i,m-j+1]:= A[i,j] XOR A[i,m-j+1];A[i,j]:=A[i,j] XOR A[i,m-j+1];1617Воробьева И.А. «Информатика. Язык Паскаль»inc(j);end;inc(i);end;ПОДЗАДАЧА 217.