Подготовка к ЕГЭ по информатике и ИКТ в 2011 г Работа с массивами: заполнение, считывание, поиск, сортировка, массовые операции. Исполнение алгоритм для. - презентация

1 Подготовка к ЕГЭ по информатике и ИКТ в 2011 г Работа с массивами: заполнение, считывание, поиск, сортировка, массовые операции. Исполнение алгоритм для конкретного исполнителя с фиксированным набором команд. Подготовила: учитель информатики и ИКТ МОУ «Большетроицкая СОШ» Зорина С.А.

2 Сравнительная характеристика результатов ЕГЭ 3-х последних лет по данным темам является следующей: Работа с массивами: заполнение, считывание, поиск, сортировка, массовые операции - А6 ( ), А17 (2011), П, время вып. - 6 мин; Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд - А18, В, время вып. - 6 мин.

3 Работа с массивами: заполнение, считывание, поиск, сортировка, массовые операции, А17 Что нужно знать: работу цикла for (цикла с переменной) массив – это набор однотипных элементов, имеющих общее имя; обращения к элементу массива осуществляется по его номеру (запись A[i] обозначает элемент массива A с номером (индексом) i); матрица (двухмерный массив) – это прямоугольная таблица однотипных элементов если матрица имеет имя A, то обращение A[i,k] обозначает элемент, расположенный на пересечении строки i и столбца k

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]

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

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

7 ДЕМО-2011, А17: В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, записанный на разных языках программирования, в котором значения элементов массива сначала задаются, а затем меняются. Бейсик FOR i=0 TO 10 A(i)=i-1 NEXT i FOR i=10 TO 1 STEP -1 A(i-1)=A(i) NEXT i Паскаль for i:=0 to 10 do A[i]:=i-1; for i:=10 downto 1 do A[i-1]:=A[i]; Чему окажутся равны элементы этого массива? 1) ) ) )

8 Решение: i A(i)=i-1 A(i-1)=A(i) FOR i=0 TO 10 A(i)=i-1 NEXT i FOR i=10 TO 1 STEP -1 A(i-1)=A(i) NEXT i ) ) ) ) Ответ:

9 ДЕМО-2010, А6 (17): В программе используется одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент программы, записанный на разных языках программирования, в котором значения элементов сначала задаются, а затем меняются. Бейсик FOR i=0 TO 10 A(i)=i NEXT i FOR i=0 TO 10 A(10-i)=A(i) A(i)=A(10-i) NEXT i Паскаль for i:=0 to 10 do A[i]:=i; for i:=0 to 10 do begin A[10-i]:=A[i]; A[i]:=A[10-i]; end; Чему будут равны элементы этого массива после выполнения фрагмента программы? 1) ) ) )

10 Решение: i A(i)=i A(10-i)=A(i) FOR i=0 TO 10 A(i)=i NEXT i FOR i=0 TO 10 A(10-i)=A(i) A(i)=A(10-i) NEXT i Ответ: 10 1) ) ) )

11 ДЕМО-2009, А6: Дан фрагмент программы, обрабатывающей двухмерный массив A размера n×n. Тогда данный алгоритм меняет местами 1) два столбца в таблице 2) две строки в таблице 3) элементы диагонали и k-ой строки таблицы 4) элементы диагонали и k-го столбца таблицы k := 1; for i:=1 to n do begin c := A[i,i]; A[i,i] := A[k,i]; A[k,i] := c; end.

12 Решение: Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. i k A[k,i] i A[i,i] Ответ: 1) два столбца в таблице; 2) две строки в таблице; 3) элементы диагонали и k-ой строки таблицы; 4) элементы диагонали и k-го столбца таблицы.

13 Исполнение алгоритма для конкретного исполнителя с фиксированным набором команд, А18 Что нужно знать: правила выполнения линейных, разветвляющихся и циклических алгоритмов основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «склеивание» двух строк в одну) исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1

14 ДЕМО-2009, А18: Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно снизу свободно слева свободно справа свободно Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ 1) 1 2) 2 3) 3 4) 0

15 Решение: для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо; на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно; кроме этих четырех стенок, необходимо, чтобы коридор, выделенный зеленым фоном, был свободен для прохода НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ

16 НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ возможны еще «вырожденные» варианты

17 нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты. НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ

18 этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, мы нашли только одну клетку. НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ

19 Проверяем оставшиеся четыре клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал: НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ

20 Ответ: 1) 1 2) 2 3) 3 4) 0

21 Возможные «ловушки» и проблемы вариантов может быть достаточно много, важно не пропустить ни один из них; можно попытаться выполнить алгоритм для каждой клетки лабиринта, но это займет много времени; поэтому лучше ограничиться только клетками-кандидатами; нужно правильно определить свойства, по которым клетку можно считать «кандидатом»; можно не заметить стенку и таким образом получить лишнее решение.