Искусство
Языки
Языкознание
Вычислительная техника
Информатика
Финансы
Экономика
Биология
Сельское хозяйство
Психология
Ветеринария
Медицина
Юриспруденция
Право
Физика
История
Экология
Промышленность
Энергетика
Этика
Связь
Автоматика
Математика
Электротехника
Философия
Религия
Логика
Химия
Социология
Политология
Геология
программирование_занятие_4. Решение задач на составление алгоритмов задания, в которых исходные данные формируются по некоторым правилам
 Скачать 2.77 Mb.
|
|
Разбираются задачи не связанные с языком программирования (всевозможные исполнители, язык блок-схем). изучается: Решение задач на составление алгоритмов. задания, в которых исходные данные формируются по некоторым правилам; задания о работе различных исполнителей; задания про различные игры, дерево игры. Вычисление значений функций: вычисление значений функций - линейность, учет ОДЗ - ветвление, получение таблицы значений - цикл. «Решение задач на составление алгоритмов» При изучении курса программирования, формируется убеждение, что все алгоритмы являются программами и пишутся на языке программирования. Может быть это и так, но мы рассмотрим примеры «исполнителей», которые могут быть реализованы и вне памяти компьютера.
Записано 6 строк, каждая имеет свой номер – от “0”- до “5”. В “0”-й строке записана цифра 0 (ноль). Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в “i”-й строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки): (0) 0 (1) 001 (2) 0010012 (3) 001001200100123 Какая цифра стоит в последней строке на 62-м месте (считая слева направо)?
Решение: Изучая алгоритм построения очередной строки, прежде всего отметим, что все цифры некоторой строки стоят на тех же местах следующей строки. Для решения задачи достаточно найти первую же строку, в которой не меньше 62 цифр. Отметим так же, что в 0-й строке одна цифра, в 1-й строке 1+1+1=3 цифры, во 2 строке 3+3+1=7 цифр, в 3 строке 7+7+1=15 цифр, в 4 строке 15+15+1=31 цифра, в 5 строке 31+31+1=63 цифры. Последняя (63-я) цифра есть номер строки, то есть 5. Перед ней, 62-я цифра – последняя в предыдущей строке, то есть 4. Ответ – на 62 месте пятой и всех последующих строк стоит цифра 4. Номер правильного ответа так же 4.
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды: Вперед n, где n целое число. Направо m, где m целое число. Запись Повтори 5 [Команда1 Команда2 ]означает, что последовательность команд в скобках повторится 5 раз. Черепашке был дан для исполнения следующий алгоритм: Повтори 5 [Вперед 10 Направо 72] Какая фигура появится на экране? 1) Незамкнутая ломаная линия 2) Правильный треугольник 3) Квадрат 4) Правильный пятиугольник Решение Исполнитель Черепашка имеет параметр «направление движения», может перемещается на экране компьютера, оставляя след в виде линии. Среди команд исполнителя есть: Вперед n, где аргумент число, шагов, выполняемых черепашкой в направлении движения. Направо m, где аргумент – число в градусах, на которое изменяется направление по часовой стрелке. Повтори k [***] означает, что последовательность команд в скобках повторится k раз. Задача сводится к задаче по геометрии. Повторение одинаковых команд несколько раз подряд называется циклом. Пусть черепашка выполнила цикл 2 раза, то есть прошла вперед от точки М0 к точке М1 на а=10 шагов, повернулась на 72 градуса и прошла еще те же а шагов до точки М2. Путь черепашки можно изобразить двумя отрезками а. К каждому отрезку а построим серединный перпендикуляр b, точку пересечения серединных перпендикуляров обозначим О. В прямоугольном треугольнике со сторонами a/2, b, c известен угол при вершине М1, его величина (180-72)/2=54 градуса. Значит угол этого треугольника при вершине О будет 36 градусов, а угол М0ОМ1 будет 72 градуса. Тело цикла выполняется 5 раз, серединные перпендикуляры каждого отрезка а пройденного пути сходятся в точке О. Угол между ОМ0 и ОМ5 составит 5*72=360 градусов, что составит полную окружность. Значит, полный путь будет замкнут. Имеем замкнутую ломаную из 5 одинаковых по длине отрезков, соединенных под одинаковыми углами – правильный пятиугольник. 
Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: “Вперед N” (Кузнечик прыгает вперед на N единиц); “Назад M” (Кузнечик прыгает назад на M единиц). Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы? Решение Имеем задачу по арифметике: Всего команд выполнено 50, из низ команд «назад …» на 12 больше, чем команд «вперед…». Составляем уравнение и выясняем, что команд «ВПЕРЕД» было 19, а команд «НАЗАД» 31. Х – количество команд «НАЗАД» X + (X-12) = 50 2X = 62 X=31 команда «НАЗАД» выполнена 31 раз. команда «ВПЕРЕД» выполнена 19 раз, (проверка: всего 31+19=50, разница 31-19=12) Определим место кузнечика после выполнения 31 команды «НАЗАД 2» и 19 команд «ВПЕРЕД 3» Вычисления показывают, что кузнечик оказался левее того места, где был изначально, на 5 шагов. 19 х 3 – 31 х 2 = 57 – 62 = -5 Ответ: перемещение кузнечика можно проделать одной командой «НАЗАД 5»
У исполнителя Калькулятор две команды: 1. прибавь 3 2. умножь на 4 Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа 21211 это программа умножь на 4 прибавь 3 умножь на 4 прибавь 3 прибавь 3 которая преобразует число 2 в 50.) Решение Для начала проверим, действительно приведенный пример из числа 2 даст 50. 2 умножь на 4 =8 8 прибавь 3 =11 11 умножь на 4 =44 44 прибавь 3 =47 47 прибавь 3 =50 Получилось! Проверка прошла успешно. При этом, надеюсь, вы обратили внимание, что команда умножения меняет число сильнее, более резко, чем команда сложения. Общее решение получается, когда после нескольких сильных изменений, подгоняем имеющееся число к требуемому маленькими шажками. Итак, из числа 3 нужно получить число 57. 57 на 4 не делится, последней командой было не умножение. Предыдущим числом было 57 – 3 = 54 57 mod 4 = 1 (57 = 4*16+1) 54 прибавь 3 = 57 - последняя команда. 54 на 4 снова не делится, очередной командой было не умножение. Предыдущим числом было 54 – 3 = 51 51 прибавь 3 = 54 54 прибавь 3 = 57 - последняя команда. И 51 на 4 не делится, очередной командой было не умножение. Предыдущим числом было 51 – 3 = 48 48 прибавь 3 = 51 51 прибавь 3 = 54 54 прибавь 3 = 57 - последняя команда. 48 на 4 делится, то есть может быть получено из числа 12 путем умножения на 4. Умножение выполняет большое изменение числа, количество шагов сокращается. В задаче указано, что число шагов должно быть маленьким, поэтому при первой же возможности применить умножение, применим его. 12 умножь на 4 = 48 48 прибавь 3 = 51 51 прибавь 3 = 54 54 прибавь 3 = 57 - последняя команда. Число 12 тоже делится на 4. Оно получается, путем умножения, из исходного числа 3. 3 умножь на 4 = 12 12 умножь на 4 = 48 48 прибавь 3 = 51 51 прибавь 3 = 54 54 прибавь 3 = 57 - последняя команда. Имеем все команды, с помощью которых из числа 3 получается число 57. Всего команд 5, в норму уложились. Используя номера команд (1 – сложение, 2 – умножение), получаем краткую запись команд: 22111 (умножить-умножить-сложить-сложить-сложить) Следует отметить, что задача разрешима не для любых исходных данных. Например, из числа 1, число 2 получить нельзя. После кодирования: 22111
У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза. Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд. (Например, программа 21211 это программа) умножь на 3 вычти 1 умножь на 3 вычти 1 вычти 1 которая преобразует число 1 в 4.) Решение. Снова, начнем с проверки примера. 1 умножь на 3 = 3 3 вычти 1 = 2 2 умножь на 3 = 6 6 вычти 1 = 5 5 вычти 1 = 4 Проверка прошла успешно. В задаче требование: результат получить за небольшое число шагов. Снова обратим внимание, что вычитание изменяет число меньше, чем умножение. Чтобы число шагов было маленьким, нужно при первой же возможности применять умножение. Из числа 3 нужно получить 16. 16 на 3 не делится, последняя команда не умножение, а вычитание, предыдущее число 16+1=17. 17 вычти 1 = 16 последняя команда 17 на 3 тоже не делится, очередная команда не умножение, а вычитание, предыдущее число 17+1=18. 18 вычти 1 = 17 17 вычти 1 = 16 последняя команда 18 на 3 делится, может быть получено умножением. Предыдущее число 18:3=6. 6 умножь на 3 = 18 18 вычти 1 = 17 17 вычти 1 = 16 последняя команда 6 на 3 снова делится, может быть получено умножением. Предыдущее число 6:3=2. 2 умножь на 3 = 6 6 умножь на 3 = 18 18 вычти 1 = 17 17 вычти 1 = 16 последняя команда Число 2 меньше исходного числа 3, может быть из него получено вычитанием. 3 вычти 1 = 2 2 умножь на 3 = 6 6 умножь на 3 = 18 18 вычти 1 = 17 17 вычти 1 = 16 последняя команда Получившиеся 5 команд можем закодировать (1 – вычитание, 2 – умножение) в виде 12211 (вычесть-умножить-умножить-вычесть-вычесть). После кодирования: 12211 В отличие от предыдущей задачи, алгоритм существует для любых исходных натуральных чисел.
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх, вниз, влево, вправо При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно Цикл ПОКА < условие > команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? НАЧАЛО ПОКА < снизу свободно > вниз ПОКА < слева свободно > влево ПОКА < сверху свободно > вверх ПОКА < справа свободно > вправо КОНЕЦ 
Последний цикл алгоритма заканчивается в клетке, у которой справа стоит стенка. Только в таких клетках может начинаться требуемый в задаче маршрут.  Всего получилось 10 возможных клеток – начал маршрутов. Можно продолжить логические рассуждения и сократить количество возможных начал, но, по-моему, проще выполнить проверку каждой клетки. Пробуем от каждой клетки спускаться до упора вниз, затем до упора влево, затем до упора вверх, и до упора вправо. Если оказались не в клетке начала маршрута, то эту точку отбрасываем. После 10 проверок остается единственная клетка (F4).           Ответ:  Ответ: - В лабиринте есть только одна клетка, начав движение из которой и выполнив имеющуюся программу, робот окажется в этой же клетке.
Большое количество простых игр так же можно представить алгоритмами. Выполнение ходов соответствует шагам алгоритма. Принятие решения о том или ином ходе – ветвление. Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте. Решение Начальную ситуацию игры можно представить следующим образом: точка имеет координаты (5,2). По очереди каждым игроком откладывается один из векторов (3,0), (0,3), (0,4). Чей вектор пересечет окружность центром (0,0) и радиусом 13, тот и выиграл. Построим дерево игры, ходы первого игрока (нечетные) выполняем одним цветом, ходы второго (четные, на каждый ход первого) – другим.   Анализируя дерево игры видим, что вектор, нарисованный первым игроком, пересечет окружность в двух случаях: либо перемещаясь только горизонтально, либо только вертикально. Но этому может помешать второй игрок, выполнив второй ход в перпендикулярном направлении и выигрывая четвертым ходом. При правильной игре выигрывает второй игрок, его ход должен быть перпендикулярен ходу первого игрока. Можно построить полное дерево игры и сделать те же выводы: Первый игрок делает четные ходы, второй – ходы с нечетными номерами. Игра заканчивается либо на 3, либо на 4 ходу. Для выигрыша 1 игрока (окончание игры на 3 ходу), требуется, чтобы вторым ходом 2 игрок повторил ход 1 игрока. Если он этого не сделает, то выиграет. Стратегия второго игрока: для выигрыша не повторять первый ход первого игрока. 1ход 2ход 3ход 4ход (5,2)-(8,2)-(11,2)-(13,2) | | +(11,5)--+------+-----+ | | | (14,5) (11,8) (11,9) | | +(11,6)--+------+-----+ | | (14,6) (11,9) (11,10) | +(8,5)-+(12,5)--+------+-----+ | | | (15,5) (12,8) (12,9) | | +(8,8)---+------+-----+ | | | (11,8) (8,11) (8,12) | | +(8,9)---+------+-----+ | | (11,9) (8,12) (8,13) | +(8,6)-+(11,6)--+------+-----+ | | (14,6) (11,9) (11,10) | +(8,9)---+------+-----+ | | (11,9) (8,12) (8,13) | +(8,10)---+------+-----+ | (11,10) (8,13) (8,14) +(5,5)-(8,5)-+(11,5)---+------+-----+ | | | (14,5) (11,8) (11,9) | | +(8,8)---+------+-----+ | | | (11,8) (8,11) (8,12) | | +(8,9)---+------+-----+ | | (11,9) (8,12) (8,13) | +(5,8)-+(8,8)---+------+-----+ | | | (11,8) (8,11) (8,12) | | +(5,11)---+------+-----+ | | | (8,11) (5,14) (5,15) | | +(5,12)---+------+-----+ | | (8,12) (5,15) (5,16) | +(5,9)-+(8,9)----+------+-----+ | | (11,9) (8,12) (8,13) | +(5,12)---+------+-----+ | | (8,12) (5,15) (5,16) | +(5,13)---+------+-----+ | (8,13) (5,16) (5,17) +(5,6)-(8,6)-+(11,6)---+------+-----+ | | (14,6) (11,9) (11,10) | +(8,9)----+------+-----+ | | (11,9) (8,12) (8,13) | +(8,10) | (11,10) (8,13) (8,14) +(5,9)-+(8,9) ---+------+-----+ | | (11,9) (8,12) (8,13) | +(5,12) | | (8,12) (5,15) (5,16) | +(5,13) +(5,10)+(8,10) ---+------+-----+ | (11,10) (8,13) (8,14) +(5,13) +(5,14)
Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в первой из которых 2, во второй – 3, в третьей – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет по два камня в каждую из куч. Выигрывает игрок, после хода которого либо в одной из куч становится не менее 15 камней, либо общее число камней во всех трех кучах становится не менее 25. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте. Решение Снова составляем дерево игры. Начальное состояние (2,3,4) Возможные ходы: удваиваем число камней в куче с меньшим числом камней удваиваем число камней в куче со средним числом камней удваиваем число камней в куче с большим числом камней добавляем в каждую кучу по 2 камня. Для экономии места, каждый раз кучи сортируем по количеству камней. Кроме того, если в некоторой ситуации возможен выигрывающий ход, будем считать, что именно он и делается, остальные ходы не пишем. 1ход 2ход 3ход 4ход (2,3,4)+(3,4,4)+(4,4,6)-+(4,6,8)--(4,6,16) | | +(4,4,12)-(4,4,24) | | +(6,6,8)—-(6,6,16) | +(3,4,8)-+(3,4,16) | +(5,6,6)-+(6,6,10)-(6,6,20) | +(5,6,12)-(5,6,22) | +(7,8,8)—-(7,8,16) +(2,4,6)+(4,4,6)-+(4,6,8)—-(4,6,16) | | +(4,4,12)-(4,4,24) | | +(6,6,8)—-(6,6,16) | +(2,6,8)--(2,6,16) | +(2,4,12)-(2,4,24) | +(4,6,8)—-(4,6,16) +(2,3,8)-(2,3,16) +(4,5,6)+(5,6,8)—-(5,6,16) +(4,6,10)-(4,6,20) +(4,5,12)-(4,5,24) +(6,7,8)—-(6,7,16) Анализируя дерево игры видим, что если первый игрок выполнит добавление по 2 камня в каждую кучку, получив из начальной ситуации (2,3,4) ситуацию (4,5,6), то при любом ответном ходе второго игрока, он выиграет, удвоив камни в кучке с максимальным числом камней.
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте. Решение В каждой ситуации возможно 4 хода: увеличить на два число камней в 1 кучке, увеличить на два число камней во 2 кучке, утроить число камней в 1 кучке, утроить число камней во 2 кучке. Составим дерево игры. Получившиеся после хода количества камней в кучках выписываем в порядке возрастания. Если есть выигрывающий ход, другие ходы не пишем. Нечетные ходы выполнят первый игрок, четные – второй. 1ход 2ход 3ход 4ход (3,4)-+(4,5)-+(5,6)-+(6,7)—-(6,21) | | +(5,8)--(5,24) | | +(6,15)-(6,45) | | +(5,18)-(5,54) | +(4,7)--(4,21) | +(5,12)-(5,36) | +(4,15)-(4,45) +(3,6)-+(5,6)-+(6,7)--(6,21) | | +(5,8)--(5,24) | | +(6,15)-(6,45) | | +(5,18)-(5,54) | +(3,8)--(3,24) | +(6,9)--(6,27) | +(3,18)-(3,54) +(4,9)—-(4,27) +(3,12)-(3,36) Анализируя дерево игры, делаем вывод, что при правильной игре выигрывает второй игрок. При увеличении на 2 количество камней в одной кучке чему надо увеличить на 2 количество камней в другой кучке [(3,4)-(4,5)-(5,6) или (3,4)-(3,6)-(5,6)], и на любой ответ первого игрока утраивать камни в кучке с максимальным числом камней. Если первый игрок выполнит утроение камней, то проиграет уже на следующем ходу. Следует отметить, что составление дерева игры – очень трудоемкая операция.
Под конец занятия, рассмотрим важную в прикладном значении тему – «Вычисление значений функций» В языках программирования имеется достаточно встроенных функций, чтобы составлять различные арифметические выражения. Для удобства использования, вычисление функций можно обособить. Посмотрим, как оформляются и используются функции пользователя на языках «бейсик» и «паскаль». В языке бейсик, при объявлении функции, начальные буквы «fn» обязательны, за этими буквами стоит буква, отличающая одну функцию от другой. В языке паскаль, имена функций полностью определяет программист. basic 10 def fna(x)=x*x-5*x+6 ... 50 print x, fna(x) pascal function f(x:real):real begin f:=x*x-5*x+6; end; var x:real; Begin x:=3,14; writeln(x:8:2,f(x):12:6); End. Получение таблицы значений функции, при аргументе, изменяющем значение от a до b с шагом h, может быть представлено линейным алгоритмом.
Повторение одинаковых шагов, которые составят тело, есть алгоритмическая конструкция – цикл. В языке бейсик, задача может быть решена обычной командой цикла со счетчиком. Более строгий паскаль не может иметь счетчиком действительное значение. Приходится использовать цикл «пока». Во избежание неточностей, связанных с ошибкой округления, цикл следует выполнять не при x<=b, а при x строго меньшем некоторого числа, которое немного больше b. Иначе, если при округлении шага h последняя цифра увеличивается, возникнет ситуация, когда x=x+h математического подсчета окажется не больше b, а вычисленное компьютером – больше b. Требуемое, согласно математике, f(b) вычисляться не будет.
Например, требуется найти таблицу значений некоторой функции на отрезке [0,2] с шагом 2/3. То есть в точках 0, 2/3, 4/3, 2. x=0 print x, fnf(x) x=x+2/3 ‘ x=0.6666666667 print x, fnf(x) x=x+2/3 ‘ x=1.3333333334 print x, fnf(x) x=x+2/3 ‘ x=2.0000000001 > 2 Фактически компьютер сосчитает значения только в точках 0, 2/3 и 4/3. После третьего присваивания x=x+h аргумент превысит граничное значение b=2. Получение таблицы значений функции – простейший циклический алгоритм. В него часто следует включать еще и ветвление – некоторые функции определены не всюду.
Принадлежность аргумента области определения определяется как система неравенств. При этом, для действительных чисел нежелательно использовать нестрогие неравенства. Сравнивайте не с числом, а с небольшим интервалом, содержащим это число. Подобный прием позволяет избежать ошибок округления. Как появляются эти ошибки было показано. Вообще, «если 5 разделить на 6, а то что получится умножить на 6, то 5 не получится»!
По окончании нашего урока, вы должны знать ответы на вопросы: Как выполнять задания ЕГ, в которых исходные данные формируются по некоторым правилам? Как выполнять задания ЕГ о работе различных исполнителей? Как выполнять задания ЕГ про различные игры? Что такое дерево игры? Как получить таблицу значений любой функции в любом интервале с любым шагом? |