Алгоритмизация Подготовка к ЕГЭ 2008-2009 год Анализ 2007 год Анализ и исполнение алгоритма, записанного в виде блок-схемы - 80% Запись фрагмента алгоритма. - презентация

1

2 Алгоритмизация Подготовка к ЕГЭ год

3

4 Анализ 2007 год Анализ и исполнение алгоритма, записанного в виде блок-схемы - 80% Запись фрагмента алгоритма для исполнителя с фиксированным набором команд – 80 % Использование переменных - 78% Работа с массивами – 64% Поиск алгоритма минимальной длины для исполнителя – 64% Анализ дерева игры – 36% Часть С -28%

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

6 mod и div 23:5=4(ост 3) div 3 mod 23mod 5 = 3 23 div 5 = 4 -

7 А5 Определите значение переменной c после выполнения следующего фрагмента программы. Решение: а = 5 a = = 11 b = - 11 с = 11 – 2*(-11) = 33. Ответ 4 БейсикПаскальАлгоритмический a = 5 a = a + 6 b = – a c = a – 2 * b a:=5; a:=a+6; b:= –a; c:=a–2*b; a:=5 a:=a+6 b:= –a c:=a–2*b 1) с = -11 2)с = 15 3) с = 27 4) с = 33

8 Возможные ловушки и проблемы: Можно перепутать нужную переменную, и, увидев в ответах число –11, выбрать его (поскольку b = –11); нельзя забывать про знак переменных и про то, что «минус на минус дает плюс»

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

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

11 Решение c = A(i,i) с присваиваются элементы диагонали. A(i,i) = A(k,i) вместо элементов диагонали ставят элементы k-ой строки таблицы A(k,i) = c вместо элементов k-ой строки таблицы ставят элементы диагонали. Ответ 3

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

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

14 Анализ алгоритма построения последовательности (А12, В8) Что нужно знать: в некоторых задачах (на RLE-кодирование) нужно знать, что такое бит и байт, что байт равен 8 бит, что такое старший бит, как переводить числа из двоичной системы в десятичную в классических задачах (на символьные цепочки) каких-либо особых знаний из курса информатики, кроме умения логически мыслить, не требуется

15 A12 Анализ алгоритма построения последовательности (базовый уровень, время – 2 мин) Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу? 1) CBB 2) EAC 3) BCD 4) BCB

16 Решение: В конце цепочки стоит одна из бусин A, B, C, значит подходить могут варианты: 1) CBB, 2) EAC, 4) BCB. Так как на первом месте – одна из бусин B, D, C которой нет на третьем месте, то остаётся только вариант: 1) CBB. Этот вариант подходит для варианта, в середине – одна из бусин А, C, E, B, не стоящая на первом месте. Ответ 1.

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

18 Решение1: Будем записывать по правилам условия. (5) E DCBAABAACBAABAADCBAABAACBAABAA (6) FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBA ABAADCBAABAACBAABAA (7) GFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAA BAADCBAABAACBAABAAFEDCBAABAACBAABAADCBAABAAC BAABAAEDCBAABAACBAABAADCBAABAACBAABAA (8) HGFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBA ABAADCBAABAACBAABAAFEDCBAABAACBAABAADCBAABAA CBAABAAEDCBAABAACBAABAADCBAABAACBAABAAGFEDCB AABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAAD CBAABAACBAABAAFEDCBAABAACBAABAADCBAABAACBAAB AAEDCBAABAACBAABAADCBAABAACBAABAA Записать ответ BAAGFED.

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

20 Решение 2 (продолжение) находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA) 7. далее сразу находим, что интересующая нас часть 8-ой строки имеет вид ABAAGFEDC 8. таким образом, правильный ответ – BAAGFED

21 Возможные ловушки и проблемы 1.можно, конечно, попробовать выписать заданную строку и выделить нужные символы, но этот подход очень трудоемкий и чреват случайными ошибками 2.чаще всего заданная цепочка находится на границе, где соединяются две части строки (например, в этом задании – на границе двух последовательностей, совпадающих с 7-ой строкой) 3.в задачах этого типа часто встречается игра на последовательностях вида 2 k : 1, 2, 4, 8, 16, … 2 k -1: 1, 3, 7, 15, 31, … полезно помнить формулу, которая «сворачивает» сумму степеней двойки: … + 2 k = 2 k (для доказательства используйте тот факт, что двоичное число, состоящее только из единиц, имеет вид 2 n -1)

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

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

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

25 А18 Выполнение алгоритмов для исполнителя (базовый уровень, время – 2 мин) 1) 1 2) 2 3) 3 4) 0

26 Решение1: Проверять будем по схеме. 1)A6 – останется на месте. 2)B6 ->B5 ->B4 – СТОП. 3) C6 -> C4 -> A4 -> A5 -> E5. 4) D6 -> D3-> A3 -> A5 -> E5. 5) E6 -> E2. 6) F6 -> F1 -> B1. 7) A5 -> A1. 8) B5 -> A5 -> E5. 9) C5 - > C4 -> A4 ->A5 -> E5. 10) D5 -> D3 -> A3 -> A5 -> E5. 11) E5 -> E2. Аналогично проверяются остальные циклы. Подойдёт только F4 -> F1 -> B1-> B4 -> F4. Ответ ABCDEF

27 Решение 2 1.легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо: 2.на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно; 3.кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода 4.итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:

28 Решение 2 4. этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:

29 Решение 2 5. проверяем оставшиеся три клетки-кандидаты, но для них всех после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал: 6. итак, условию удовлетворяет только одна клетка – F4 7. таким образом, правильный ответ – 1.

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

31 А18 Выполнение алгоритмов для исполнителя (базовый уровень, время – 2 мин) В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные 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) АДЗОТ

32 Решение А:=Поезд i := 5 k := 2 b := 'А' пока i > 0 5>0 3>0 нц c := Извлечь(a,i) Д E b := Склеить(b,c) АД АДЕ i := i – k 5-2=3 кц b := Склеить(b,'Т') 1) АДЕПТ

33 В2 Блок-схемы алгоритмов. Переменные, присваивание значений. Ветвления. Организация циклов с помощью блока «ветвление» (базовый уровень, время – 1 мин). Что нужно знать: 1.переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы 2.оператор присваивания (в Паскале обозначается сочетанием символов «:=») служит для записи нового значения в переменную (для изменения ее значения) 3.если в переменную записывают новое значение, старое стирается 4.знаки +, -, *, / используются для обозначения операций сложения, вычитания, умножения и деления 5.запись вида a := a + 2; – это не уравнение, а команда «прочитать текущее значение переменной a, добавить к нему 2 и записать результат обратно в переменную a»; 6.для наглядной записи небольших алгоритмов используют блок-схемы; они состоят из блоков разного назначения и соединительных линий со стрелками, которые показывают порядок выполнения блоков 7.в задачах ЕГЭ встречаются два блока: процесс (выполнение некоторых действий) и ветвление (условие, в зависимости от которого выполнение алгоритма продолжается по одной или другой «ветке» ) 8.с помощью ветвления можно организовать цикл (многократное выполнение одинаковых действий), в этом случае в блок-схеме будет соединительная линия, идущая «в обратном направлении» (петля, замкнутый контур)

34 В2 Запишите значение переменной b после выполнения фрагмента алгоритма: a b

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

36 Решение (вариант 2, анализ алгоритма): «прокрутив» начало алгоритма, можно заметить, что последовательные значения a – это степени двойки a = 1, 2, 4, 8, … 256 поскольку оператор b:=b+a означает «взять текущее значение b, прибавить к нему текущее значение a и результат записать обратно в b», изменение b сводится к тому, что эти степени двойки складываются: b = … теперь можно, конечно, сложить эти числа вручную (их всего 9), но можно заметить (или вспомнить), что сумма всех последовательных степеней двойки, начиная с 1, на единицу меньше, чем следующая степень двойки (первая, не вошедшая в сумму, здесь – 512); это легко проверяется по начальной части таблицы таким образом, верный ответ 512 – 1 = 511

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

38 В5 Поиск алгоритма минимальной длины для исполнителя (повышенный уровень, время – 10 мин) Что нужно знать: каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

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

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

41 Возможные ловушки и проблемы: Иногда может потребоваться «откат» назад, например, если исходное число – 6, то применив деление на 4 для 12 мы «проскакиваем» его (получаем 12/4=3

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

43 В5 Поиск алгоритма минимальной длины для исполнителя (повышенный уровень, время – 10 мин) Два игрока играют в следующую игру. Имеются три кучки камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой нибудь кучке, или добавить по два камня в каждую из трех куч. Предполагается, что у каждого игрока имеется неограниченный запас камней. Выигрывает тот игрок, после чьего хода в какой- нибудь кучке становиться >=15 камней или во всех трех кучках суммарно становиться >=25 камней. Игроки ходят по очереди. Выясните, кто выигрывает при правильной игре, -первый или второй игрок.

44 Решение 0123 (анализ) 2,3,4 4,3,4 8,3,4 4,6,4Проигрыш 1-го игрока 4,3,8 6,5,6 2,6,4 4,6,4Проигрыш 1-го игрока 2,12,4 2,6,8 4,8,6 2,3,82,3,16Проигрыш 1-го игрока 4,5,6 8,5,6Выигрыш 1-го игрока 4,10,6Выигрыш 1-го игрока 4,5,12Выигрыш 1-го игрока 6,7,8Выигрыш 1-го игрока