ЕГЭ по информатике 2010-2011 А5, А6, А18, В2, В5, В8 Кухилава Ельза Шакровна Учитель информатики МОУ Лицей 59 г. Сочи. - презентация

1 ЕГЭ по информатике А5, А6, А18, В2, В5, В8 Кухилава Ельза Шакровна Учитель информатики МОУ Лицей 59 г. Сочи

2 А5 базовый уровень. Тема: Оператор присваивания в языке программирования. Что нужно знать: переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы оператор присваивания служит для записи значения в переменную если в переменную записывают новое значение, старое стирается знаки +, -, *, / используются для обозначения операций сложения, вычитания, умножения и деления запись вида a div b означает результат целочисленного деления a на b (остаток отбрасывается) запись вида a mod b означает остаток от деления a на b запись вида a := b + 2*c + 3; означает «вычислить значения выражения справа от знака присваивания := и записать результат в переменную a»; при этом значения других переменных (кроме a) не изменяются.

3 для многократного выполнения одинаковых операций используют циклы; цикл с переменной выполняется N раз, в этом примере переменная i принимает последовательно все значения от 1 до N с шагом 1 паскаль: for i:=1 to N do begin { тело цикла} end; Basic For i=1 to n step k next i цикл с условием выполняется до тех пор, пока условие в заголовке цикла не нарушится; Паскаль: Basic: while { условие } do begin While условие { тело цикла } end; Wend

4 1. Пример задания: Определите значение переменной c после выполнения следующего фрагмента программы. a := 5; a := a + 6; b := –a; c := a – 2*b; 1) c = –112) c = 153) c = 274) c = 33 Решение: 1.для решения нужно использовать «ручную прокрутку» программы, то есть, выполнить вручную все действия 2. наиболее удобно и наглядно это получается при использовании таблицы, где в первом столбце записаны операторы программы, а в остальных показаны изменения переменных при выполнении этих операторов 3. здесь используются три переменные: a, b, c; до выполнения программы их значения неизвестны, поэтому ставим в таблице знаки вопроса:

5 abc ??? 4. после выполнения оператора a := 5; изменяется значение переменной a: abc ??? a := 5; 5 5. оператор a := a + 6; означает «вычислить значение выражения a + 6 используя текущее значение a (равное 5), и записать результат обратно в переменную a»; таким образом, новое значение равно = 11: abc ??? a := 5; 5 a := a + 6; 11

6 6. следующий оператор, a := a + 6, изменяет значение переменной b, записывая в нее –a; учитывая, что в a записано число 11, находим, что b будет равно –11: abc ??? a := 5; 5 a := a + 6; 11 b := –a; –11 7. последняя команда, c := a – 2*b, изменяет значение переменной c; при текущих значениях a = 11 и b = –11 результат выражения равен 11 – 2*(–11) = 33, это число и будет записано в переменную c: abc ??? a := 5; 5 a := a + 6; 11 b := –a; –11 c := a – 2*b; таким образом, правильный ответ – 4.

7 пример 2. В результате выполнения фрагмента программы while n 0 do begin write ( 2*(n mod 10)+1); n := n div 10; end; на экран выведено число Какое число хранилось до этого в переменной n? 1) 7162) 6383) 3864) 836 Решение: 1. прежде всего, заметим, что для вывода используется оператор write, который не переходит на следующую строку; поэтому числа в цикле будут выводиться в одной строке «вплотную» друг к другу, без промежутков 2. для решения можно использовать «ручную прокрутку» программы, то есть, выполнить программу вручную для всех приведенных ответов 3. вспомним, что n mod 10 – остаток от деления числа на 10 – это последняя цифра числа в десятичной системе счисления; 4. операция n div 10 (деление нацело на 10) равносильна отбрасыванию последней цифры в десятичной системе счисления 5. эти две операции выполняются пока значение переменной n не станет равно нулю 6. теперь можно построить таблицу ручной прокрутки; рассмотрим первый из ответов, 716:

8 nn mod 10 вывод на экран n 0? write(2*(n mod 10)+1); 613 n := n div 10; 71 n 0? write(2*(n mod 10)+1); 13 7 n := n div 10; 7 n 0? write(2*(n mod 10)+1); n := n div 10; 0 n 0? видим, что в этом случае на экран будет выведена цепочка 13315, не равная заданной (13717) 1.аналогично проверяем все остальные предложенные ответы и выясняем, что для последнего числа, 836, на экран выводится цепочка 13717, совпадающая с заданной 2. таким образом, правильный ответ – 4.

9 Задачи для тренировки: 1.Определите значение целочисленных переменных a и b после выполнения фрагмента программы: a := 3 + 8*4; b := (a div 10) + 14; a := (b mod 10) + 2; 1) a = 0, b = 18 2) a = 11, b = 193) a = 10, b = 18 4) a = 9, b = Определите значение целочисленных переменных a и b после выполнения фрагмента программы: a := 1819; b := (a div 100)*10+9; a := (10*b–a) mod 100; 1) a = 81, b = 1992) a = 81, b = 1893) a = 71, b = 199 4) a = 71, b = Определите значение целочисленных переменных a и b после выполнения фрагмента программы: a := 42; b := 14; a := a div b; b := a*b; a := b div a; 1) a = 42, b = 142) a = 1, b = 423) a = 0, b = 5884) a = 14, b = Определите значение целочисленных переменных x, y и t после выполнения фрагмента программы: x := 5; y := 7; t := x; x := y mod x; y := t; 1) x=2, y=5, t=52) x=7, y=5, t=5 3) x=2, y=2, t=24) x=5, y=5, t=5 5. Определите значение целочисленных переменных a и b после выполнения фрагмента программы: а :=6*12 + 3; b :=(a div 10)+ 5; a :=(b mod 10)+ 1; 1) a = 1, b = 102) a = 3, b = 123) a = 4, b = 164) a = 10, b = 20

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

11 A[1,1] A[2,2] A[3,3] A[4,4] 1.выше главной диагонали расположены элементы, у которых номер строки меньше номера столбца; 2.ниже главной диагонали расположены элементы, у которых номер строки больше номера столбца; A[1,2]A[1,3]A[1,4] A[2,3]A[2,4] A[3,4] A[2,1] A[3,1]A[3,2] A[4,1]A[4,2]A[4,3]

12 Пример задания: Дан фрагмент программы, обрабатывающей двухмерный массив A размера n×n. k := 1; for i:=1 to n do begin c := A[i,i]; A[i,i] := A[k,i]; A[k,i] := c; end Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. Тогда данный алгоритм меняет местами 1) два столбца в таблице 2) две строки в таблице 3) элементы диагонали и k-ой строки таблицы 4) элементы диагонали и k-го столбца таблицы Решение: сначала разберемся, что происходит внутри цикла; легко проверить (хотя бы ручной прокруткой, если вы сразу не узнали стандартный алгоритм), что операторы c := A[i,i]; A[i,i] := A[k,i]; A[k,i] := c; меняют местами значения A[i,i] и A[k,i], используя переменную c в качестве вспомогательной ячейки; элемент матрицы A[i,i], у которого номера строки и столбца одинаковые, стоит на главной диагонали; элемент A[k,i] стоит в том же столбце i, но в строке с номером k; это значит, что в столбце i меняются местами элемент на главной диагонали и элемент в строке k

13 i kA[k,i] iA[i,i] так как эти операторы находятся в цикле, где переменная i принимает последовательно все значения от 1 до n, обмен выполняется для всех столбцов матрицы; то есть, все элементы главной диагонали меняются с соответствующими элементами строки k перед циклом стоит оператор присваивания k := 1;, а после него переменная k не меняется; поэтому в программе элементы главной диагонали обмениваются с первой строкой таким образом, правильный ответ – 3.

14 Еще пример задания: Значения двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы: for n:=1 to 100 do A[n] := (n-80)*(n-80); for n:=1 to 100 do B[101-n] := A[n]; Какой элемент массива B будет наибольшим? 1) B[1]2) B[21]3) B[80]4) B[100] Решение: здесь два цикла, в первом из них заполняется массив А, во втором – массив В в элемент массива A[n] записывается квадрат числа n-80; все элементы массива А неотрицательны (как квадраты чисел) посмотрим чему равны некоторые элементы массива А: A[1] = (1–80) 2 = (–79) 2 = 792A[2] = (2–80) 2 = (–78) 2 = A[80] = (80–80) 2 = (0) 2 = 0A[81] = (81–80) 2 = (1) 2 = 1... A[99] = (99–80) 2 = 192A[100] = (100–80) 2 = 202 таким образом, при увеличении n от 1 до 80 значение A[n] уменьшается от 792 до нуля, а потом (для n > 80) возрастает до 202 отсюда следует, что максимальное значение в массиве A – это A[1] = 792 во втором цикле для всех номеров n от 1 до 100 выполняется оператор B[101-n] := A[n]; который просто переписывает элементы массива A в массив В, «развертывая» массив в обратном порядке (элемент A[1] будет записан в B[100], а A[100] – в B[1]) A[1], наибольший элемент массива А, будет записан в B[100], поэтому B[100] – наибольший элемент в массиве В таким образом, правильный ответ – 4.

15 Задачи для тренировки: 1. Значения двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы: for n:=1 to 100 do A[n] := n - 10; for n:=1 to 100 do B[n] := A[n]*n; Сколько элементов массива B будут иметь положительные значения? 1) 102) 503) 904) Все элементы двумерного массива A размером 10х10 элементов первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы: for n:=1 to 4 do for k:=n to 4 do begin A[n,k] := A[n,k] + 1; A[k,n] := A[k,n] + 1; end; Сколько элементов массива в результате будут равны 1? 1) 0 2) 163) 124) 4 3. Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы: for n:=1 to 5 do for k:=1 to 5 do B[n,k] := n + k; Чему будет равно значение B(2,4)? 1) 92) 83) 74) 6 4. Дан фрагмент: for n:=l to 6 do for m:=l to 5 do begin C[n,m]:=C[n,m]+(2*n-m); end; Чему будет равно значение С[4,3], если перед этими командами значение С[4,3]=10? 1) 52) 103) 154) 25

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

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

18 Решение: легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо: на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно; кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:

19 4. итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты: 5. этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют: 6. проверяем оставшиеся три клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал: 7. итак, условию удовлетворяет только одна клетка – F4 8. таким образом, правильный ответ – ABCDEF ABCDEF ABCDEF ABCDEF ABCDEF

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

21 Решение: 1. особенность этой задач в том, что РОБОТ проверяет стенку в одном направлении, а движется в другом 2. рассмотрим первый цикл: ПОКА вверх понятно, что при движении вверх РОБОТ остановится в первой же клетке, где слева будет стена 3.рассуждая аналогично, находим, что во втором цикле при движении вправо РОБОТ останавливается в клетке, где есть стена сверху; в третьем цикле (движение вниз) РОБОТ останавливается в клетке, где есть стена справа; 4. наконец, в четвертом цикле РОБОТ останавливается в клетке, где есть стена снизу; при этом он должен попасть обратно в исходную клетку, обозначенную на рисунке красной точкой; 5. кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке зеленым фоном, был свободен для прохода, иначе РОБОТ врежется в стенку 6.теперь отметим на карте все клетки-кандидаты, где снизу есть стена: 7. при движении из клеток B5, D1, E1, E6, F1 и F3 РОБОТ врежется в стенку, потому что слева стены нет и условие «слева свободно» всегда истинно: 8. начав движение с клетки A1, C1 или C2, РОБОТ также врезается в стенку и разрушается: 9. и только путь, начатый в клетке B1, приводит РОБОТА обратно в точку старта: 10.таким образом, только клетка B1 удовлетворяет условию задачи, поэтому … правильный ответ – 1.

22 пример задания: В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции: Длина(a) – возвращает количество символов в строке a. (Тип «целое») Извлечь(a,i) – возвращает i-тый (слева) символ в строке a. (Тип «строка») Склеить(a,b) – возвращает строку, в которой записаны сначала все символы строки a, а затем все символы строки b. (Тип «строка») Значения строк записываются в одинарных кавычках (Например, a:='дом'). Фрагмент алгоритма: i := Длина(a) k := 2 b := 'А' пока i > 0 нц c := Извлечь(a,i) b := Склеить(b,c) i := i – k кц b := Склеить(b,'Т') Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ПОЕЗД? 1) АДЕПТ2) АДЗЕОП3) АДТЕТПТ4) АДЗОТ Решение: 1.эта задача более близка к классическому программированию, здесь выполняется обработка символьных строк; вся информация для успешного решения, вообще говоря, содержится в условии, но желательно иметь хотя бы небольшой опыт работы с символьными строками на Паскале (или другом языке) 2. заметим, что последняя команда алгоритма, b:=Склеить(b,'Т'), добавляет букву 'Т' в конец строки b, поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву 'Т', а не на 'П') 3. для решения будем использовать ручную прокрутку; здесь пять переменных: a, b, c, i, k, для каждой из них выделим столбец, где будем записывать изменение ее значения 4. перед выполнением заданного фрагмента мы знаем только значение a, остальные неизвестны (обозначим их знаком вопроса):

23

24 поскольку i=5, вызов функции Извлечь(a,i) выделяет из строки a символ с номером 5, это 'Д'; следующей командой этот символ приписывается в «хвост» строки b, теперь в ней хранится цепочка 'АД'; в команде i:=i-k значение переменной i уменьшается на k (то есть, на 2) далее нужно перейти в начало цикла и снова проверить условие i>0, оно опять истинно, поэтому выполняется следующий шаг цикла, в котором к строке b добавляется 3-й символ строки a, то есть 'Е': abcik... 'ПОЕЗД''АД'…32 i > 0?да c:=Извлечь(a,i) 'Е' b:=Cклеить(b,c) 'АДЕ' i:=i–k 1 условие i>0 истинно, поэтому тело цикла выполняется еще один раз, к строке b добавляется 1-й символ строки a, то есть 'П': abcik... 'ПОЕЗД''АДЕ'…12 i > 0?да c:=Извлечь(a,i) 'П''П' b:=Cклеить(b,c) 'АДЕП' i:=i–k –1–1

25 теперь i=-1, поэтому при очередной проверке условие i>0 в начале цикла оказывается ложным, выполнение цикла заканчивается, и исполнителю остается выполнить единственную строчку после цикла, которая дописывает в конец строки b букву 'Т': abcik... 'ПОЕЗД''АДЕП'…–12 i > 0?нет b:=Склеить(b,'Т') 'АДЕПТ' у нас получилось, что в конце выполнения фрагмента алгоритма в переменной b будет записана последовательность символов 'АДЕПТ' таким образом, правильный ответ – 1.

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

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

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

29 4. Имеется фрагмент алгоритма, записанный на алгоритмическом языке: i := Длина(а) k := 1 b := 'T' пока i > 1 нц с := Извлечь(а, i) b := Склеить(b, с) i := i - k; кц Здесь переменные a, b и с - строкового типа; переменные n, m, k – целые. В алгоритме используются следующие функции: Длина(х) – возвращает количество символов в строке х. Имеет тип «целое». Извлечь(х,i) – возвращает i-й символ слева в строке х. Имеет строковый тип. Склеить(х,у) – возвращает строку, в которой записаны подряд сначала все символы строки х, а затем все символы строки у. Имеет строковый тип. Значения строк записываются в кавычках (одинарных), например x:='школа'. Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение 'КАРА'? 1) КАРАТ2) ТАРА3) КРАТ4) ТКАРА

30 B2. Тема: Блок-схемы алгоритмов. Переменные, присваивание значений. Ветвления. Организация циклов с помощью блока «ветвление». Что нужно знать: переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы оператор присваивания (в Паскале обозначается сочетанием символов «:=») служит для записи нового значения в переменную (для изменения ее значения) если в переменную записывают новое значение, старое стирается знаки +, -, *, / используются для обозначения операций сложения, вычитания, умножения и деления запись вида a := a + 2; – это не уравнение, а команда «прочитать текущее значение переменной a, добавить к нему 2 и записать результат обратно в переменную a»; для наглядной записи небольших алгоритмов используют блок-схемы; они состоят из блоков разного назначения и соединительных линий со стрелками, которые показывают порядок выполнения блоков Пример задания: Запишите значение переменной b после выполнения фрагмента алгоритма: a:=a*2; b:=b+a; a:=1; b:=1; a = 256? да нет

31 Решение: 1.по схеме видим, что алгоритм содержит цикл (есть петля, контур) 2. ручную прокрутку удобнее всего выполнять в виде таблицы, в первом столбце будем записывать выполняемые команды, во втором и третьем – изменение значений переменных a и b 3. после выполнения первого блока получаем ab a:=1; 1? b:=1; 1 знак вопроса означает, что после выполнения первого оператора значение b не определено затем выполняется проверка условия; поскольку а не равно 256, ответ на вопрос «a = 256?» будет «нет»: ab a:=1; 1? b:=1; 1 a = 256? нет далее алгоритм уходит на выполнение тела цикла; здесь сначала меняется переменная a, а потом – b, причем нужно помнить, что для вычисления b используется новое значение a, равное 2, поэтому новое значение b равно = 3: ab a:=1; 1? b:=1; 1 a = 256? нет a:=a*2; 2 b:=b+a; 3

32 после этого по стрелке переходим на проверку условия; поскольку a = 2, ответ на вопрос «a = 256?» снова будет «нет», и выполняется очередной шаг цикла: ab a:=1; 1? b:=1; 1 a = 256? нет a:=a*2; 2 b:=b+a; 3 a = 256? нет a:=a*2; 4 b:=b+a; 7 аналогично можно выполнить вручную все шаги цикла, результаты последнего из них выглядят так: ab a:=a*2; 256 b:=b+a; 511 a = 256? да как только значение a стало равно 256, цикл завершает работу таким образом, верный ответ – 511.

33 Задачи для тренировки: Определите значение переменной m после выполнения фрагмента алгоритма. m:=54; n:=16; m = n? да нет m > n? да m:=m-n; нет n:=n-m; 2. Определите значение переменной a после выполнения фрагмента алгоритма. b:=b+1; a:=a*2; a:=1; b:=0; b = 4? да нет

34 3. Определите значение переменной x после выполнения фрагмента алгоритма. x:=55; y:=75; x y? нет да x > y? нет y:=y-x; да x:=x-y; 4. Определите значения переменных x и y после выполнения фрагмента алгоритма. В ответ запишите номер правильного варианта: 1)x=15, y=16 2) x=20, y=13 2)3) x=16, y=15 4) x=13, y=20 x:=10; y:=15; y < 16? нет да x

35 B5 (повышенный уровень, время – 10 мин) Тема: Поиск алгоритма минимальной длины для исполнителя. Что нужно знать: каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6- 7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды Пример задания: У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 3 2. умножь на 4 Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа это программа умножь на 4 прибавь 3 умножь на 4 прибавь 3 которая преобразует число 2 в 50.)

36 Решение «обратный ход»: 1.нам нужно увеличить число (с 3 до 57), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях 2.попробуем решить задачу «обратным ходом», начав с числа 57; 3.очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение (прибавь 3), над стрелкой записан номер команды: 4. число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение: 5. аналогично для числа 51: 6. число 48 делится на 4, поэтому используем умножение: 7. наконец, добавив в начало программы еще одно умножение, получаем полную цепочку: 8. таким образом, правильный ответ – 22111, эта программа состоит из 5 команд.

37 Задачи для тренировки: 1.У исполнителя строитель две команды, которым присвоены номера: 1. вычти 2 2. умножь на три Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, – это программа: умножь на три вычти 2 умножь на три вычти 2 вычти 2, которая преобразует число 2 в 8). (Если таких программ более одной, то запишите любую из них.) 2. У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2 2. умножь на 3 Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа – это программа: умножь на 3 прибавь 2 умножь на 3 прибавь 2 прибавь 2, которая преобразует число 1 в 19). 3. У исполнителя СТРОИТЕЛЬ две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза. Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд. (Например, программа это программа умножь на 3 вычти 1 умножь на 3 вычти 1 которая преобразует число 1 в 4.)

38 B8 (повышенный уровень, время – 10 мин) Тема: Анализ алгоритма построения последовательности. Что нужно знать: в некоторых задачах (на RLE-кодирование, см. далее) нужно знать, что такое бит и байт, что байт равен 8 бит. Пример задания: Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).

39 Решение: 1.используя приведенное правило, можно построить следующие строки: (5) EDCBAABAACBAABAADCBAABAACBAABAA (6) FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAA BAACBAABAA мы быстро убедимся, что следующие строки получаются достаточно длинные, и легко запутаться, отсчитывая символы с номерами в восьмой строке 3.попробуем найти закономерности, позволяющие решить задачу без выписывания 8-ой строки; 4. прежде всего, заметим, что длины первых строк 1, 3, 7, 15, … – это числа вида 2 n -1, где n– номер строки; таким образом, длина 7-ой строки – 127, а длина восьмой – 255 символов 5. восьмая строка строится так: восьмая буква латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны номера символов) HGFEDC…...AABAAGFEDC…...AABAA 6.символы находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA) 7. далее сразу находим, что интересующая нас часть 8-ой строки имеет вид ABAAGFEDC 8. таким образом, правильный ответ – BAAGFED.

40 Еще пример задания: Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Сколько в восьмой строке букв, отличных от буквы «А»? Решение : 1.попробуем найти закономерность в изменении количества букв, отличных от буквы «A» 2.в первой строке 0 таких букв, во второй – 1 (удвоили число букв «не A» в предыдущей строке и добавили 1, поскольку в начало строки дописана буква «B») 3.аналогично находим, что в третьей строке – 3 нужных буквы, в 4-ой – 7 и т.д. 4.продолжим последовательность, каждый раз умножай предыдущее число на 2 и добавляя единицу: 5 строка – 15 6 строка – 31 7 строка – 63 8 строка – эти числа задаются общей формулой, где N – номер строки, подстановка дает, что совпадает с полученным выше результатом 6.таким образом, правильный ответ – 127.

41 Еще пример задания: Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала дважды подряд записывается предыдущая строка, а потом справа приписывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита). Вот первые 4 строки, созданные по этому правилу: (1) A (2) AAB (3) AABAABC (4) AABAABCAABAABCD Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите шесть символов подряд, стоящие в восьмой строке со 101-го по 106-е место (считая слева направо). Решение: 1.сначала подсчитаем общую длину 8-ой строки; длины строк изменяются согласно последовательности 1, 3, 7, 15, … (каждое следующее число равно удвоенному предыдущему плюс 1); таким образом, для 8-ой строки получаем длину 255 (можно было также использовать формулу, где N – номер строки) 2.вспомним, как строится 8-ая строка: сначала дважды записана 7-ая строка, а затем – буква «H» (8-ой символ латинского алфавита) AABAA…...CDEFGAABAA…...CDEFGH 3.видим, что символы находятся внутри первой части, она состоит из двух 6-х строк и буквы G: AABAA…...BCDEFAABAA…...BCDEFG 4.символы находятся во второй копии 6-ой строки, которая состоит из двух 5-х строк и буквы F AABAA…...ABCDEFAABAA…...ABCDEF

42 5.символы находятся во второй копии 5-ой строки, которая, в свою очередь, состоит из двух 4-х строк и буквы E 6.рассмотрим копию 4-ой строки, которая в 8-ой строке начинается с символа 95: AABAABCAABAABC 7.интересующие нас символы выделены зеленым цветом 8.таким образом, правильный ответ – CAABAA.

43 Задачи для тренировки: 1.Цепочки символов (строки) создаются по следующему правилу: Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается такими действиями: в начало записывается число – номер строки по порядку (для i-й строки ставится число «i»), далее дважды подряд записывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 211 (3) (4) Сколько раз встречается цифра «1» в первых семи строках (суммарно)? 2.Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 112 (3) (4) Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)? Записано 7 строк, каждая имеет свой номер – от «0»- до «6»-й. В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу: (0) 0 (1) 001 (2) (3) Какая цифра стоит в последней строке на 123-м месте (считая слева направо)? Цепочки символов (строки) создаются по следующему правилу: первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так: сначала записывается порядковый номер данной строки, далее дважды записывается вся цепочка цифр из предыдущей строки. Первые 4 строки, созданные по этому правилу, выглядят следующим образом: Сколько раз в общей сложности встречаются в 10-й строке нечетные цифры (1,3, 5, 7,9)?