Алгоритм в задачах ОГЭ

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Алгоритм в заданиях ОГЭ
  Обзор составила
  учитель информатики
  Милосердова Ю.С.
  МБОУ «средняя общеобразовательная школа №63
  с углубленным изучением отдельных предметов»
  
  

• 

  2 слайд

  Алгоритм – это строго определенная последовательность действий при решении задачи.
  Алгоритм содержит несколько шагов.
  Шаг алгоритма – это каждое отдельное действие алгоритма.
  Исполнитель – это объект выполняющий определенный набор действий.
  Исполнителем может быть человек, робот, животное, компьютер.
  Система команд исполнителя (СКИ) – это совокупность команд, которые может выполнять исполнитель.
  Среда исполнителя – обстановка, в которой функционирует исполнитель.
  

• 

  3 слайд

  Разрабатывает алгоритмы: человек
  Исполняют алгоритмы: люди и устройства – компьютеры, роботы, станки, спутники, сложная бытовая техника, детские игрушки.
  Исполнитель решает задачу по заданному алгоритму, строго следуя по предписаниям (программе) не вникая и не рассуждая, почему он так делает.
  !!! Исполнителем алгоритма может быть не только человек, но и автоматическое устройство (реальное или воображаемое).
  В этом случае шаги алгоритма часто называют командами и вводят их в устройство в той форме, в которой оно сможет их обрабатывать.
  
  

• 

  4 слайд

  Обзор заданий ГИА по теме: «Алгоритм»
  Задания A6. Алгоритм для конкретного исполнителя с фиксированным набором команд
  Задания B2. Линейный алгоритм, записанный на алгоритмическом языке
  Задания B3. Простейший циклический алгоритм, записанный на алгоритмическом языке
  Задания B4. Циклический алгоритм обработки массива чисел, записанный на алгоритмическом языке
  Задания B8. Простой линейный алгоритм для формального исполнителя
  Задания B10. Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки
  Задания C2. Короткий алгоритм в среде формального исполнителя или на языке программирования
  

• 

  5 слайд

  Алгоритм для конкретного исполнителя с фиксированным набором команд
  
  Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии.
  В каждый конкретный момент известно положение исполнителя и направление его движения.
  СКИ (две команды):
  Вперёд n (где n — целое число), вызывающая передвижение Черепашки на n шагов в направлении движения.
  Направо m (где т — целое число), вызывающая изменение направления движения на m градусов
  по часовой стрелке.
  Запись
  Повтори k [Команда 1 Команда 2 Команда 3] означает, что последовательность команд в скобках повторится k раз.
  
  

• 

  6 слайд

  Черепашке дан для исполнения алгоритм:
  Повтори 6 [Направо 60 Вперёд 15]
  Какая фигура появится на экране?
  1. правильный пятиугольник
  2. правильный треугольник
  3. правильный шестиугольник
  4. правильный двенадцатиугольник
  Решение.
  Выпуклый многоугольник называется правильным, если у него все стороны равны и все углы равны.
  Черепашка шесть раз повторяет группу команд, указанную в скобках. При этом она каждый раз поворачивает в одном направлении — направо, на один и тот же угол и прочерчивает отрезки одинаковой длины.
  Выполнив весь алгоритм, Черепашка совершит поворот на 600 ∙ 6 = 3600.
  Сумма внешних углов многоугольника = 360°.
  Следовательно, получается замкнутая ломаная, образующая правильный многоугольник, состоящий из шести равных сторон, т.е.
  правильный шестиугольник.
  600
  600
  600
  600
  600
  600
  

• 

  7 слайд

  Черепашке был дан для исполнения следующий алгоритм:
  Повтори 8 [Направо 45 Вперёд 18 Направо 45]
  Какая фигура появится на экране?
  восьмиконечная звезда
  правильный восьмиугольник
  незамкнутая ломаная линия
  квадрат
  Решение.
  Если это правильный многоугольник, то сумма его внешних углов = 3600.
  Величина одного внешнего угла = 450 + 450 = 900
  3600/ 900 = 4 (делится без остатка)
  получаем КВАДРАТ, так как Повтори 8…,
  квадрат нарисуется дважды по одному контуру
  450
  450
  450
  450
  450
  450
  450
  450
  

• 

  8 слайд

  Алгоритм для конкретного исполнителя с фиксированным набором команд
  
  Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след  в  виде  линии. 
  Чертёжник  может  выполнять  команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Если числа a,  b  положительные,  значение  соответствующей
  координаты увеличивается, если отрицательные – уменьшается.
  Например,  если  Чертёжник  находится  в  точке  с  координатами (4, 2),  то команда Сместиться на (2, –3) переместит Чертёжника в точку (6, –1).
  Запись
  Повтори k раз
  Команда1 Команда2 Команда3
  Конец
  означает,  что  последовательность  команд  Команда1  Команда2  Команда3 повторится k раз.
  

• 

  9 слайд

  Чертёжнику был дан для исполнения следующий алгоритм:
  Повтори 3 раз
  Сместиться на (–2, –1) Сместиться на (3, 2) Сместиться на (2, 1)
  Конец
  На  какую  одну  команду  можно  заменить  этот  алгоритм,  чтобы  Чертёжник оказался в той же точке, что и после выполнения алгоритма?
  1) Сместиться на (–9, –6)
  2) Сместиться на (6, 9)
  3) Сместиться на (–6, –9)
  4) Сместиться на (9, 6)
  
  Решение:
  Так как начальное положение не задано, выберем его сами
  — например, (1, 1).
  Чертежника обозначим зеленым кружком. Рассмотрим тело цикла:
  Сместиться на (–2, –1) Сместиться на (3, 2) Сместиться на (2, 1)
  Отразим эти команды на нашем рисунке: после выполнения трех команд Чертёжник сместился относительно начального положения на 3 клетки вправо и 2 клетки вверх. По условию задачи, эти три команды выполняются 3 раза (Повтори 3 раз). И если мы повторим рассмотренные команды из тела цикла еще один раз, то Чертёжник сместиться еще на 3 клетки вправо и 2 клетки вверх. А на последнем повторении — еще раз на 3 вправо и 2 вверх. В сумме получим, что после выполнения алгоритма Чертёжник сместиться на 3 раза по 3 клетки вправо и на 3 раза по 2 клетки вверх. Т. е. в общем он сместиться на 9 клеток вправо и 6 клеток вверх относительно начального положения. Значит весь этот алгоритм можно заменить одной командой — Сместиться на (9, 6). Правильный ответ 4.
  
  4
  5
  6
  9
  2
  3
  1 шаг цикла
  

• 

  10 слайд

  Линейный алгоритм, записанный на алгоритмическом языке
  В алгоритме, записанном ниже, используются переменные a и b. Символ «:=» обозначает оператор присваивания, знаки «+», «-», «*» и «/» — соответственно операции сложения, вычитания, умножения и деления. Правила выполнения операций и порядок действий соответствуют правилам арифметики.
  Линейный алгоритм – это алгоритм, шаги которого выполняются последовательно друг за другом. 
  Решение:
  Выполним программу:
  а := 10
  b := 110
  b := 110 + b/a = 110 + 11 = 121
  a := b/11*a = 11 · 10 = 110.
  
  Ответ: 110
  
  Определите значение переменной a после выполнения алгоритма: 
  а := 10
  b := 110
  b := 110 + b/a
  a := b/11*a
  В ответе укажите одно целое число — значение переменной a.
  

• 

  11 слайд

  Простейший циклический алгоритм, записанный на алгоритмическом языке
  Циклический алгоритм – алгоритм, обеспечивающий многократное выполнение некоторой совокупности действий, которая называется телом цикла.
  
  Циклы бывают трех видов:
  с предусловием «пока-делай»,
  постусловием «делай-пока»,
  со счётчиком «для».
  
  Цикл со счётчиком «для». Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
  
  For i:= нз to кз do
  begin тело цикла end;
  
  

• 

  12 слайд

  Определите, что будет напечатано в результате работы следующей программы. Текст программы приведён на трёх языках программирования.
  Решение: В теле цикла происходит увеличение значения переменной s на 5. Так как параметр цикла увеличивается от 0 до 9 с шагом 1, то при выполнении программы тело цикла будет выполняться 10 раз ( k будет равно 0,1,2,3,4,5,6,7,8,9). Т. е. переменная s увеличивается на 10*5 = 50.
  А так как начальное значение переменной s = 1 и после выполнения программы оно увеличится на 50, то в конечном итоге значение переменной s станет равным 51.
  

• 

  13 слайд

  Циклический алгоритм обработки массива чисел, записанный на алгоритмическом языке
  
  Массив – фиксированное количество элементов одного типа, объединенных одним именем
  
  Назначение: хранение данных
  
  
  Имя массива
  Индекс (номер)
  Значение элемента
  

• 

  14 слайд

  В таблице Dat хранятся данные измерений среднесуточной температуры за неделю в градусах (Dat[1] – данные за понедельник, Dat[2] – за вторник и т.д.). Определить, что будет напечатано в результате выполнения алгоритма, записанного на языке Паскаль:
  
  Задание:
  var k, m, day: integer;
  Dat: array [1..7] of integer;
  Begin
  Dat[1] := 7;
  Dat[2] := 9;
  Dat[3] := 10;
  Dat[4] := 8;
  Dat[5] := 6;
  Dat[6] := 7;
  Dat[7] := 6;
  day := 1; m := Dat[1];
  for k := 2 to 7 do
  begin
  if Dat[k] < m then
  begin m := Dat[k]; day := k; end;
  end;
  write (day);
  end.
  

• 

  15 слайд

  Анализ программы:
  var k, m, day: integer;
  Dat: array [1..7] of integer;
  Begin
  Dat[1] := 7;
  Dat[2] := 9;
  Dat[3] := 10;
  Dat[4] := 8;
  Dat[5] := 6;
  Dat[6] := 7;
  Dat[7] := 6;
  day := 1; m := Dat[1];
  for k := 2 to 7 do
  begin
  if Dat[k] < m then
  begin m := Dat[k]; day := k; end;
  end;
  write (day);
  end.
  Ответ: 5
  

• 

  16 слайд

  Исполнитель Вычислитель имеет следующую систему пронумерованных команд:
  умножь на два;
  прибавь единицу.
  Первая умножает число на два, а вторая прибавляет к числу единицу.
  Алгоритм, преобразующий число 3 в число 26, записывается в виде последовательности команд 1121, что соответствует:
  1. умножь на два3 ∙ 2 = 6
  1. умножь на два6 ∙ 2 = 12
  2. прибавь единицу12 + 1 = 13
  1. умножь на два 13 ∙ 2 = 26
  Запишите порядок команд алгоритма, преобразующего число 3 в число 21, содержащего не более пяти команд, указывая лишь номера команд.
  Решение
  Простой линейный алгоритм для формального исполнителя
  

• 

  17 слайд

  Решим обратную задачу:
  получить из числа 21 число 3. Применяемые команды также должны быть обратными к заданным командам исполнителя:
  дели на два;
  вычти единицу.
  Операция дели на два выполняется только для чисел, кратных двойке, иначе она не будет обратной исходной команде умножь на два.
  Для скорейшего получения из числа 21 числа 3 по возможности применяем операцию деления, а если это невозможно — операцию вычитания.
  Ответ: 22112
  Исходная задача: 3 → 21
  1. умножь на два;
  2. прибавь единицу.
  Результат решения обратной задачи — полученную последовательность команд — переписываем в обратном порядке для получения ответа исходной задачи.
  Подобные задачи принято решать «от ответа»
  

• 

  18 слайд

  Исполнитель Делитель
  У исполнителя Делитель две команды, которым присвоены номера:
  1. прибавь пять
  2. раздели на два
  Первая команда увеличивает число на экране на 5, вторая — уменьшает его в 2 раза.
  Запишите порядок команд в алгоритме получения из числа 1 числа 13, содержащем не более 5 команд, указывая лишь номера команд.
  Например, последовательность 11221 соответствует алгоритму, который преобразует число 7 в 8:
  1. прибавь пять (12)
  2. раздели на два (6)
  1. прибавь пять (11)
  1. прибавь пять (16)
  2. раздели на два (8)
  Если таких алгоритмов более одного, то запишите любой из них.
  Ответ: 1211
  

• 

  19 слайд

  Исполнитель Утроитель
  У исполнителя Утроитель две команды, которым присвоены номера:
  1. умножь на три
  2. вычти 2
  Первая из них утраивает число на экране,
  вторая уменьшает его на 2.
  Запишите порядок команд в алгоритме получения
  из числа 9 числа 19, содержащем
  не более 3 команд, указывая лишь номера команд.
  
  Например, 21211 — это алгоритм:
  1. умножь на три
  2. вычти 2
  1. умножь на три
  2. вычти 2
  2. вычти 2, — который преобразует число 2 в 8.
  Ответ: 212
  

• 

  20 слайд

  Исполнитель Удвоитель
  У исполнителя Удвоитель две команды, которым присвоены номера:
  1. вычти 3
  2. умножь на 2
  Первая из них уменьшает число на экране на 3, вторая — удваивает его.
  Запишите порядок команд в алгоритме получения из числа 11 числа 13, содержащем не более 3 команд, указывая лишь номера команд.
  
  Например, 212111 — это алгоритм:
  умножь на 2
  вычти 3
  умножь на 2
  вычти 3
  вычти 3
  вычти 2, — который преобразует число 5 в 8
  
  
  Если таких алгоритмов более одного, то запишите любой из них.
  
  Ответ: 121
  

• 

  21 слайд

  Исполнитель Удвоитель
  У исполнителя Делитель две команды, которым присвоены номера:
  вычти три
  умножь на два
  Первая команда уменьшает число на экране на 3, вторая — увеличивает его в 2 раза.
  Запишите порядок команд в алгоритме получения из числа 16 числа 34, содержащем не более 5 команд, указывая лишь номера команд.
  Например, последовательность 22121 соответствует алгоритму, который преобразует число 2 в 7:
  2. умножь на два (4)
  2. умножь на два (8)
  1. вычти три (5)
  2. умножь на два (10)
  1. вычти три(7).
  Если таких алгоритмов более одного, то запишите любой из них.
  
  Ответ: 11212
  

• 

  22 слайд

  Исполнитель Вычислитель
  У исполнителя Вычислитель три команды, которым присвоены номера:
  вычти 1
  умножь на 3
  прибавь 3
  Первая из них уменьшает число на экране на 1, вторая — утраивает его, а третья увеличивает на 3.
  Запишите порядок команд в алгоритме получения из числа 5 числа 23 за наименьшее число команд.
  
  Например, 211 — это алгоритм:
  2. умножь на 3
  1. вычти 1
  1. вычти 1,— который преобразует число 7 в 19.
  Решение
  

• 

  23 слайд

  Исполнитель Вычислитель
  вычти 1
  умножь на 3
  прибавь 3
  Запишите порядок команд в алгоритме получения из числа 5 числа 23 за наименьшее число команд.
  5
  -1
  *3
  +3
  4
  15
  8
  -1
  *3
  +3
  -1
  *3
  +3
  -1
  3
  12
  7
  14
  45
  18
  7
  24
  11
  +3
  *3
  *3
  +3
  -1
  23
  I
  II
  III
  Ответ: 321
  Для решения данной задачи полезно построить дерево. Строим!
  

• 

  24 слайд

  Исполнитель Конструктор
  У исполнителя Конструктор две команды, которым присвоены номера:
  1. приписать 2
  2. разделить на 2.
  Первая из них приписывает к числу на экране справа цифру 2, вторая – делит его на 2.
  Запишите порядок команд в алгоритме получения
  из числа 1 числа 16, содержащем не более 5 команд, указывая только номера команд
  (например, 22212 – это алгоритм:
  разделить на 2
  разделить на 2
  разделить на 2
  приписать 2
  разделить на 2,
  который преобразует число 8 в число 6.)
  Если таких алгоритмов более одного, запишите любой из них.
  Решение
  

• 

  25 слайд

  СКИ:
  1. приписать 2
  2. разделить на 2.
  Получить из числа 1 число 16 (максимум за 5 команд).
  1
  1
  2
  12
  1
  6
  122
  2
  I
  II
  III
  2
  1
  3
  62
  2
  1
  32
  2
  1
  16
  322
  IV
  V
  Ответ: 12212
  Исполнитель Конструктор
  

• 

  26 слайд

  Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки
  Получить из одной цепочки символов новую следующим образом:
  1. Записывается исходная цепочка;
  2. Далее она же в обратном порядке;
  3. Далее по алфавиту буква, следующая по порядку за последней буквой из исходной цепочки.
  Дана цепочка АЛ. Что будет, если алгоритм применить дважды.
  Строим таблицу решений
  
  
  
  
  
  
  
  Т.о. получили АЛЛАММАЛЛАН
  

• 

  27 слайд

  Короткий алгоритм в среде формального исполнителя
  Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости, разбитой на клетки.
  У Робота есть четыре команды перемещения:
  вверх
  вниз
  влево
  вправо.
  При выполнении любой из этих команд Робот перемещается на одну клетку соответственно:
  вверх ↑, вниз ↓, влево ←, вправо →.
  Между соседними (по сторонам) клетками может стоять стена, через которую Робот пройти не может. Если Робот получает команду передвижения через стену, то он разрушается.
  Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится Робот:
  сверху свободно
  снизу свободно
  слева свободно
  справа свободно.
  Эти команды можно использовать с условием «если», имеющим следующий вид:
  если <условие> то
  последовательность команд
  все
  Последовательность команд — это одна или несколько любых команд Робота. Например, для передвижения на одну клетку вправо, если справа нет стенки, можно использовать такой алгоритм:
  если справа свободно то
  вправо
  все
  В одном условии можно использовать несколько команд, используя логические связки: «и», «или», «не». Например,
  если (справа свободно) и (не снизу свободно) то
  вправо
  все
  Для повторения последовательности команд можно использовать цикл «пока», имеющий следующий вид:
  нц пока <условие>
  последовательность команд
  кц
  Например, для движения вправо, пока это возможно, можно использовать следующий алгоритм:
  нц пока справа свободно
  вправо
  кц
  У Робота есть команда закрасить, закрашивающая клетку, в которой находится Робот в настоящий момент.
  

• 

  28 слайд

  Задание :
  На бесконечном поле имеются две длинные горизонтальные стены одинаковой длины. Длина стен неизвестна. Расстояние между ними — две клетки. Робот находится в одной из клеток, расположенной между стен. Начальное положение Робота неизвестно. Одно из возможных положений Робота приведено на рисунке (Робот обозначен буквой «Р»):
  
  
  
  
  
  
  
  Напишите для Робота алгоритм, закрашивающий все клетки, расположенные между стенами. Робот должен закрасить только клетки, удовлетворяющие данному условию. Например, для рисунка выше Робот должен закрасить следующие клетки:
  
  
  
  
  
  
  
  Конечное расположение Робота может быть произвольным. Алгоритм должен решать задачу для произвольного размера стены и любого допустимого начального положения Робота.
  Алгоритм напишите в текстовом редакторе и сохраните в текстовом файле.
  Решение
  

• 

  29 слайд

  Возможный вариант алгоритма:
  
  алг Закраска
  нач
  если сверху свободно то
  вверх
  все
  нц пока сверху не свободно не сверху свободно
  влево
  кц
  вправо
  нц пока сверху не свободно не сверху свободно
  закрасить
  вправо
  кц
  вниз
  влево
  нц пока снизу не свободно не снизу свободно
  закрасить
  влево
  кц
  кон
  

• 

  30 слайд

  На бесконечном поле имеется прямоугольник из стен. Длина противоположных стен прямоугольника неизвестна. Расстояние между противоположными стенами — не менее двух клеток. Робот находится в одной из клеток, расположенной внутри прямоугольника из стен. Начальное положение Робота неизвестно. Одно из возможных положений Робота приведено на рисунке (Робот обозначен буквой «Р»).
  Напишите для Робота алгоритм, закрашивающий все внутренние угловые клетки прямоугольника из стен. Робот должен закрасить только клетки, удовлетворяющие данному условию. Например, для исходного рисунка Робот должен закрасить клетки, заштрихованные на рисунке ниже.
  Конечное расположение Робота может быть произвольным. Алгоритм должен решать задачу для произвольного размера стены и любого допустимого начального расположения Робота. Алгоритм напишите в текстовом редакторе и сохраните в текстовом файле.
  Решение
  Задание :
  

• 

  31 слайд

  нц пока слева свободно
  влево
  кц
  нц пока сверху свободно
  вверх
  кц
  закрасить
  нц пока справа свободно
  вправо
  кц
  закрасить
  нц пока снизу свободно
  вниз
  кц
  закрасить
  нц пока слева свободно
  влево
  кц
  закрасить
  Возможный вариант алгоритма:
  

• 

  32 слайд

  Короткий алгоритм на языке программирования
  Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, оканчивающихся на 3. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 3. Количество чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна вывести одно число — количество чисел, оканчивающихся на 3.
  Uses crt;
  Var n, s, k, g: integer;
  Begin
  s:=0; {счетчик искомых чисел}
  readln(n); {количество чисел в последовательности}
  for k:=1 to n do
  Begin
  readln(g); {очередной член послед-ти}
  if (g div 10 = 3) then
  s:=s+1;
  end;
  writeln(s);
  end.