uzluga.ru
добавить свой файл



Алгоритмизация

  • Подготовка к ЕГЭ

  • 2008-2009 год





Анализ 2007 год

  • Анализ и исполнение алгоритма, записанного в виде блок-схемы - 80%

  • Запись фрагмента алгоритма для исполнителя с фиксированным набором команд – 80 %

  • Использование переменных - 78%

  • Работа с массивами – 64%

  • Поиск алгоритма минимальной длины для исполнителя – 64%

  • Анализ дерева игры – 36%

  • Часть С -28%



А5 Оператор присваивания в языке программирования (базовый уровень, время – 2 мин)

  • Что нужно знать:

  • переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы;

  • оператор присваивания служит для записи значения в переменную;

  • если в переменную записывают новое значение, старое стирается;

  • знаки +, -, *, / используются для обозначения операций сложения, вычитания, умножения и деления;

  • запись вида a div b означает результат целочисленного деления a на b (остаток отбрасывается);

  • запись вида a mod b означает остаток от деления a на b;

  • запись вида a := b + 2*c + 3; означает «вычислить значения выражения справа от знака присваивания := и записать результат в переменную a»; при этом значения других переменных (кроме a) не изменяются.



mod и div

  • 23:5=4(ост 3)

  • 23 5

  • 20 4 div

  • 3

  • mod

  • mod 5 = 3

  • 23 div 5 = 4



А5 Определите значение переменной c после выполнения следующего фрагмента программы.

  • Решение: а = 5

  • a = 5 + 6 = 11

  • b = - 11

  • с = 11 – 2*(-11) = 33.

  • Ответ 4



Возможные ловушки и проблемы:

  • Можно перепутать нужную переменную, и, увидев в ответах число –11, выбрать его (поскольку b = –11);

  • нельзя забывать про знак переменных и про то, что «минус на минус дает плюс»



А6 Работа с массивами и матрицами в языке программирования (повышенный уровень, время – 4 мин)

  • работу цикла for (цикла с переменной);

  • массив – это пронумерованный набор однотипных элементов, имеющих общее имя;

  • для обращения к элементу массива используют квадратные скобки, запись A[i] обозначает элемент массива A с номером (индексом) i;

  • матрица (двухмерный массив) – это прямоугольная таблица однотипных элементов;

  • если матрица имеет имя A, то обращение A[i,k] обозначает элемент, расположенный на пересечении строки i и столбца k;

  • элементы, у которых номера строки и столбца совпадают, расположены на главной диагонали;

  • выше главной диагонали расположены элементы, у которых номер строки меньше номера столбца;

  • ниже главной диагонали расположены элементы, у которых номер строки больше номера столбца;



А6 Дан фрагмент программы, обрабатывающей двумерный массив A размера n×n

  • Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j –номером столбца, в котором расположен элемент. Тогда данный алгоритм меняет местами

  • 1) два столбца в таблице

  • 2) две строки в таблице

  • 3) элементы диагонали и k-ой строки таблицы

  • 4) элементы диагонали и k-го столбца таблицы



Решение

  • c = A(i,i) с присваиваются элементы диагонали.

  • A(i,i) = A(k,i) вместо элементов диагонали ставят элементы k-ой строки таблицы

  • A(k,i) = c вместо элементов k-ой строки таблицы ставят элементы диагонали.

  • Ответ 3



Возможные ловушки и проблемы:

  • сложность этой задачи в том, что все действия нужно «прокручивать в уме» (или на бумаге), не используя компьютер для отладки

  • главная проблема – не перепутать столбцы и строки; номер строки – это (по соглашению) первый индекс элемента матрицы, а номер столбца – второй



Совет:

  • чтобы понять, что делает программа, часто бывает полезно сделать ручную прокрутку на матрице небольшого размера, например, 3 на 3 или 4 на 4.

  • если матрица небольшая (скажем, 5 на 5) можно (а иногда и нужно) вообще сделать все вычисления вручную и посмотреть, что получится



Анализ алгоритма построения последовательности (А12, В8)

  • Что нужно знать:

  • в некоторых задачах (на RLE-кодирование) нужно знать, что такое бит и байт, что байт равен 8 бит, что такое старший бит, как переводить числа из двоичной системы в десятичную

  • в классических задачах (на символьные цепочки) каких-либо особых знаний из курса информатики, кроме умения логически мыслить, не требуется



A12 Анализ алгоритма построения последовательности (базовый уровень, время – 2 мин)

  • Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте.

  • Какая из перечисленных цепочек создана по этому правилу?

  • 1) CBB 2) EAC 3) BCD 4) BCB



Решение:

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

  • Ответ 1.



B8 Анализ алгоритма построения последовательности. (повышенный уровень, время – 10 мин)

  • Строки (цепочки символов латинских букв) создаются по следующему правилу.

  • Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка.

  • Вот первые 4 строки, созданные по этому правилу:

  • (1) A

  • (2) BAA

  • (3) CBAABAA

  • (4) DCBAABAACBAABAA

  • Латинский алфавит (для справки):

  • ABCDEFGHIJKLMNOPQRSTUVWXYZ

  • Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).



Решение1:

  • Будем записывать по правилам условия.

  • (5) E DCBAABAACBAABAADCBAABAACBAABAA

  • (6) FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAABAACBAABAA

  • (7)

  • GFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAABAACBAABAAFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAABAACBAABAA

  • (8)

  • HGFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAABAACBAABAAFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAABAACBAABAAGFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAABAACBAABAAFEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAABAACBAABAA

  • Записать ответ BAAGFED.



Решение 2

  • 1. используя приведенное правило, можно построить следующие строки:

  • (5) EDCBAABAACBAABAADCBAABAACBAABAA

  • (6) EDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAA

  • DCBAABAACBAABAA

  • ...

  • 2. мы быстро убедимся, что следующие строки получаются достаточно

  • длинные, и легко запутаться, отсчитывая символы с номерами 126-132

  • восьмой строке

  • 3. попробуем найти закономерности, позволяющие решить задачу без

  • выписывания 8-ой строки;

  • 4. прежде всего, заметим, что длины первых строк 1, 3, 7, 15, … – это числа

  • вида 2i-1, где i – номер строки; таким образом, длина 7-ой строки – 127, а

  • длина восьмой – 255 символов

  • 5. восьмая строка строится так: восьмая буква латинского алфавита (H) и затем

  • – два раза седьмая строка (сверху написаны номера символов)



Решение 2 (продолжение)



Возможные ловушки и проблемы

  • можно, конечно, попробовать выписать заданную строку и выделить нужные символы, но этот подход очень трудоемкий и чреват случайными ошибками

  • чаще всего заданная цепочка находится на границе, где соединяются две части строки (например, в этом задании – на границе двух последовательностей, совпадающих с 7-ой строкой)

  • в задачах этого типа часто встречается игра на последовательностях вида

  • 2k: 1, 2, 4, 8, 16, …

  • 2k-1: 1, 3, 7, 15, 31, …

  • полезно помнить формулу, которая «сворачивает» сумму степеней двойки:

  • 1 + 2 + 4 + 8 + … + 2k = 2k+1 - 1

  • (для доказательства используйте тот факт, что двоичное число, состоящее только из единиц, имеет вид 2n-1)



Важное замечание

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



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

  • Что нужно знать:

  • правила выполнения линейных, разветвляющихся и циклических алгоритмов

  • основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)

  • исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

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

  • запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1



Главное

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



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



Решение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.

  • Ответ 1



Решение 2

  • легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:

  • на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;

  • кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода

  • итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:



Решение 2

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



Решение 2

  • 5. проверяем оставшиеся три клетки-кандидаты, но для них всех

  • после выполнения алгоритма РОБОТ не приходит в ту клетку,

  • откуда он стартовал:



Возможные ловушки и проблемы:

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


А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) ‘АДЗОТ’



Решение

  • А:=Поезд

  • 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,'Т')



В2 Блок-схемы алгоритмов. Переменные, присваивание значений. Ветвления. Организация циклов с помощью блока «ветвление» (базовый уровень, время – 1 мин) .

  • Что нужно знать:

  • переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы

  • оператор присваивания (в Паскале обозначается сочетанием символов «:=») служит для записи нового значения в переменную (для изменения ее значения)

  • если в переменную записывают новое значение, старое стирается

  • знаки +, -, *, / используются для обозначения операций сложения, вычитания, умножения и деления

  • запись вида a := a + 2; – это не уравнение, а команда «прочитать текущее значение переменной a, добавить к нему 2 и записать результат обратно в переменную a»;

  • для наглядной записи небольших алгоритмов используют блок-схемы; они состоят из блоков разного назначения и соединительных линий со стрелками, которые показывают порядок выполнения блоков

  • в задачах ЕГЭ встречаются два блока: процесс (выполнение некоторых действий) и ветвление (условие, в зависимости от которого выполнение алгоритма продолжается по одной или другой «ветке» )

  • с помощью ветвления можно организовать цикл (многократное выполнение одинаковых действий), в этом случае в блок-схеме будет соединительная линия, идущая «в обратном направлении» (петля, замкнутый контур)



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



Возможные проблемы:

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


Решение (вариант 2, анализ алгоритма):

  • «прокрутив» начало алгоритма, можно заметить, что последовательные значения a – это степени двойки a = 1, 2, 4, 8, … 256

  • поскольку оператор b:=b+a означает «взять текущее значение b, прибавить к нему текущее значение a и результат записать обратно в b», изменение b сводится к тому, что эти степени двойки складываются: b = 1 + 2 + 4 + 8 + … + 256

  • теперь можно, конечно, сложить эти числа вручную (их всего 9), но можно заметить (или вспомнить), что сумма всех последовательных степеней двойки, начиная с 1, на единицу меньше, чем следующая степень двойки (первая, не вошедшая в сумму, здесь – 512); это легко проверяется по начальной части таблицы

  • таким образом, верный ответ 512 – 1 = 511



Возможные проблемы:

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


В5 Поиск алгоритма минимальной длины для исполнителя (повышенный уровень, время – 10 мин)

  • Что нужно знать:

  • каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом

  • исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды



В5 Поиск алгоритма минимальной длины для исполнителя (повышенный уровень, время – 10 мин)

  • У исполнителя Калькулятор две команды, которым присвоены номера:

  • 1. прибавь 3

  • 2. умножь на 4

  • Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

  • (Например, программа 21211 это программа

  • умножь на 4

  • прибавь 3

  • умножь на 4

  • прибавь 3

  • прибавь 3

  • которая преобразует число 2 в 50.)



Решение («обратный ход»):

  • нам нужно увеличить число (с 3 до 57), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях

  • попробуем решить задачу «обратным ходом», начав с числа 57;

  • очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение (прибавь 3), над стрелкой записан номер команды:

  • число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение:

  • аналогично для числа 51:

  • число 48 делится на 4, поэтому используем умножение:

  • наконец, добавив в начало программы еще одно умножение, получаем полную цепочку:

  • таким образом, правильный ответ – 22111, эта программа состоит из 5 команд.



Возможные ловушки и проблемы:

  • Иногда может потребоваться «откат» назад, например, если исходное число – 6, то применив деление на 4 для 12 мы «проскакиваем» его (получаем 12/4=3<6), поэтому нужно возвращаться обратно к 12 и дважды применять сложение; в этом случае ответ будет такой:



Почему здесь «обратный ход» лучше?:

  • обратим внимание, что когда мы «шли» в обратном направлении, от конечного числа к начальному, часто очередную операцию удавалось определить однозначно (когда число не делилось на 4)

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



В5 Поиск алгоритма минимальной длины для исполнителя (повышенный уровень, время – 10 мин)

  • Два игрока играют в следующую игру.

  • Имеются три кучки камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой нибудь кучке, или добавить по два камня в каждую из трех куч. Предполагается, что у каждого игрока имеется неограниченный запас камней.

  • Выигрывает тот игрок, после чьего хода в какой-нибудь кучке становиться >=15 камней или во всех трех кучках суммарно становиться >=25 камней.

  • Игроки ходят по очереди. Выясните, кто выигрывает при правильной игре, -первый или второй игрок.



Решение