Презентация, доклад на тему Алгоритм в задачах ОГЭ

школа №63
с углубленным изучением отдельных предметов»

несколько шагов.
Шаг алгоритма – это каждое отдельное действие алгоритма.

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

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

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

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

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

Вперёд 15]
Какая фигура появится на экране? 1. правильный пятиугольник 2. правильный треугольник 3. правильный шестиугольник 4. правильный двенадцатиугольник

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

Выполнив весь алгоритм, Черепашка совершит поворот на 600 ∙ 6 = 3600.
Сумма внешних углов многоугольника = 360°.
Следовательно, получается замкнутая ломаная, образующая правильный многоугольник, состоящий из шести равных сторон, т.е. правильный шестиугольник.

Вперёд 18 Направо 45]
Какая фигура появится на экране?
восьмиконечная звезда
правильный восьмиугольник
незамкнутая ломаная линия
квадрат

Решение.
Если это правильный многоугольник, то сумма его внешних углов = 3600.
Величина одного внешнего угла = 450 + 450 = 900
3600/ 900 = 4 (делится без остатка)
получаем КВАДРАТ, так как Повтори 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 раз.

–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 шаг цикла

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.

многократное выполнение некоторой совокупности действий, которая называется телом цикла.

Циклы бывают трех видов:
с предусловием «пока-делай»,
постусловием «делай-пока»,
со счётчиком «для».

Цикл со счётчиком «для». Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.

For i:= нз to кз do
begin тело цикла end;

приведён на трёх языках программирования.

Решение: В теле цикла происходит увеличение значения переменной 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.

количество элементов одного типа, объединенных одним именем

Назначение: хранение данных

Имя массива

Индекс (номер)

Значение элемента

градусах (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.

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

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

Решение

Простой линейный алгоритм для формального исполнителя

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

Ответ: 22112

Исходная задача: 3 → 21 1. умножь на два;
2. прибавь единицу.

Результат решения обратной задачи — полученную последовательность команд — переписываем в обратном порядке для получения ответа исходной задачи.

Подобные задачи принято решать «от ответа»

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

Ответ: 1211

на три
2. вычти 2
Первая из них утраивает число на экране, вторая уменьшает его на 2.

Запишите порядок команд в алгоритме получения из числа 9 числа 19, содержащем не более 3 команд, указывая лишь номера команд.

Например, 21211 — это алгоритм:
1. умножь на три
2. вычти 2
1. умножь на три
2. вычти 2
2. вычти 2, — который преобразует число 2 в 8.

Ответ: 212

3
2. умножь на 2
Первая из них уменьшает число на экране на 3, вторая — удваивает его.

Запишите порядок команд в алгоритме получения из числа 11 числа 13, содержащем не более 3 команд, указывая лишь номера команд.

Например, 212111 — это алгоритм:
умножь на 2
вычти 3
умножь на 2
вычти 3
вычти 3
вычти 2, — который преобразует число 5 в 8


Если таких алгоритмов более одного, то запишите любой из них.

Ответ: 121

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

Ответ: 11212

на 3
прибавь 3
Первая из них уменьшает число на экране на 1, вторая — утраивает его, а третья увеличивает на 3.
Запишите порядок команд в алгоритме получения из числа 5 числа 23 за наименьшее число команд.

Например, 211 — это алгоритм:
2. умножь на 3
1. вычти 1
1. вычти 1,— который преобразует число 7 в 19.

Решение

из числа 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

Для решения данной задачи полезно построить дерево. Строим!

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

Решение

(максимум за 5 команд).

Ответ: 12212

Исполнитель Конструктор

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

Строим таблицу решений







Т.о. получили АЛЛАММАЛЛАН

лабиринту, начерченному на плоскости, разбитой на клетки.

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

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

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






Напишите для Робота алгоритм, закрашивающий все клетки, расположенные между стенами. Робот должен закрасить только клетки, удовлетворяющие данному условию. Например, для рисунка выше Робот должен закрасить следующие клетки:







Конечное расположение Робота может быть произвольным. Алгоритм должен решать задачу для произвольного размера стены и любого допустимого начального положения Робота.
Алгоритм напишите в текстовом редакторе и сохраните в текстовом файле.

Решение

пока сверху не свободно не сверху свободно
влево
кц
вправо
нц пока сверху не свободно не сверху свободно
закрасить
вправо
кц
вниз
влево
нц пока снизу не свободно не снизу свободно
закрасить
влево
кц
кон

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

Решение

Задание :

вверх
кц
закрасить
нц пока справа свободно
вправо
кц
закрасить
нц пока снизу свободно
вниз
кц
закрасить
нц пока слева свободно
влево
кц
закрасить

Возможный вариант алгоритма:

натуральных чисел определяет количество чисел, оканчивающихся на 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.