Необходимо анализировать и выполнять алгоритмы, используя различные формы записи: естественный язык; графический язык; формальный язык (язык программирования) Элементы теории алгоритмов Задания 6, 14, 20, 22, 25

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

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

Прямой ход Обратный ход Ответ: 22111

У исполнителя Аккорд две команды, которым присвоены номера: 1. отними 1 2. умножь на x где x – неизвестное положительное число. Выполняя первую из них, Аккорд отнимает от числа на экране 1, а выполняя вторую, умножает это число на x. Программа для исполнителя Аккорд – это последовательность номеров команд. Известно, что программа переводит число 4 в число 23. Определите значение x.

Система команд: 1. отними 1 2. умножь на x Программа переводит число 4 в число 23. Решение : Пусть x - неизвестное положительное число Вход: 4 1 : 4 – 1 = 3 2 : 3· x = 3 x 1 : 3· x – 1 2 : (3· x – 1) · x = 3 x 2 – x 1 : 3 x 2 – x – 1 = 23 Корни уравнения: x 1 = 3 и x 2 = – 2,666 Ответ : 3.

У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера: 1. сдвинь влево 2. вычти 1 Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд Запишите результат в десятичной системе.

Система команд исполнителя: 1. сдвинь влево 2. вычти 1 Программа перевода числа 104. Решение: 1. Числа однобайтовые (8 бит). 2.«Сдвиг влево» - операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса. 3. Переводим число 104 в двоичную систему счисления и выполняем программу. 4. Переводим в десятичную систему счисления. Ответ : 60.

Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?

Ответ: 414

Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика: Вперед 4 – Кузнечик прыгает вперед на 4 единицы, Назад 3 – Кузнечик прыгает назад на 3 единицы. Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 27? Решение: Составим уравнение Решим уравнение в целых числах: Ответ: 3

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1 ) Строится двоичная запись числа N. 2 ) К этой записи дописываются справа ещё два разряда по следующему правилу: а ) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись преобразуется в запись ; б ) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе. Выполнение и анализ простых алгоритмов Ответ: 46

Проверяемые элементы содержания: умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд. Что нужно знать: правила выполнения линейных, разветвляющихся и циклических алгоритмов основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну) в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1 14 (повышенный уровень, время – 6 мин)

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно снизу свободно слева свободно справа свободно Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? 1) 1 2) 2 3) 3 4) 0 НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ Ответ: 1

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно снизу свободно слева свободно справа свободно Цикл ПОКА команда выполняется, пока условие истинно. В конструкции ЕСЛИ ТО КОМАНДА1 ИНАЧЕ КОМАНДА2 КОНЕЦ ЕСЛИвыполняется команда 1 (если условие истинно) или команда 2 (если условие ложно).

Если РОБОТ начнет движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервется. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет и остановится в закрашенной клетке (F6)? 1) 8 2) 15 3) 24 4) 27 НАЧАЛО ПОКА вправо КОНЕЦ ПОКА ПОКА вниз КОНЕЦ ПОКА КОНЕЦ Ответ: 3

ПОКА вправо КОНЕЦ ПОКА ПОКА вниз КОНЕЦ ПОКА

20 (повышенный уровень, время – 5 мин) Проверяемые элементы содержания: анализ алгоритма, содержащего цикл и ветвление. Что нужно знать: основные конструкции языка программирования; уметь выполнять ручную прокрутку программы уметь выделять переменную цикла, от изменения которой зависит количество шагов цикла уметь определять количество шагов цикла уметь определять переменную, которая выводится на экран.

Ответ: 34

В результате выполнения фрагмента программы while n 0 do begin write ( 2*(n mod 10)+1); n := n div 10; end; на экран выведено число Укажите все числа, которые могли находиться в переменной n до выполнения этого цикла.

Ниже записана программа. Получив на вход число x, этот алгоритм печатает два числа L и M. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 7. var x, L, M: integer; begin readln(x); L:=0; M:=0; while x > 0 do begin L:=L+1; if M < (x mod 10) then begin M:=x mod 10; end; x:= x div 10; end; writeln(L); write(M); end. 25

1. Рассмотрим цикл, число шагов которого зависит от изменения переменной x : while x > 0 do begin... x:= x div 10; { отсечение последней цифры } end; На каждом шаге от десятичной записи x отсекается последняя цифра до тех пор, пока все цифры не будут отсечены и x не станет равно 0. Следовательно, цикл выполняется столько раз, сколько цифр в десятичной записи введенного числа x. Переменная L при каждом выполнении цикла увеличивается на 1 и в ней по окончании выполнения цикла будет находится количество цифр числа x.

2. Переменная М изменяется в условном операторе: if M < (x mod 10) then begin M:=x mod 10; end; Так как x mod 10 – это последняя цифра десятичной записи числа. Если цифра окажется больше, чем значение M, то она станет новым значением M. Условный оператор выполняется в цикле для всех значений цифр введенного числа. Следовательно, в переменной M окажется наибольшая из всех цифр введенного числа. 3. Наибольшее трехзначное число, со старшей цифрой 7 – это 777. Ответ: 777.

22 (повышенный уровень, время – 7 мин) Проверяемые элементы содержания: умение анализировать результат исполнения алгоритма Что нужно знать: уметь строить дерево решений уметь искать одинаковые числа в списке уметь считать разные числа в списке

У исполнителя Калькулятор две команды: 1. прибавь 3, 2. вычти 2. Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются). Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?

1. Построение полного графа решений: Ответ: 6

У исполнителя Калькулятор две команды: 1. прибавь 1 2. умножь на 2. Первая из них увеличивает число на экране на 1, вторая – удваивает его. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команд?

1. Построение полного графа решений: Ответ: 15

У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 3 Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20?

1 способ решения: 1. прибавь 1 2. умножь на 3

2 способ решения: 1. прибавь 1 2. умножь на 3 При выполнении любой из команд число увеличивается (не может уменьшаться). Все числа, меньшие начального числа 1, с помощью этого исполнителя получить нельзя, для них количество программ будет равно 0. Для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды. Построим рекуррентную формулу, связывающую K N с предыдущими элементами последовательности K 1, K 2,…,K N-1 : если N не делится на 3: K N =K N-1 если N делится на 3: K N =K N-1 +K N/3 N KNKN N KNKN

У исполнителя Удвоитель две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель – это последовательность команд. Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»?

1. Прибавить 1 2. Умножить на 2 Предпоследняя команда – 1, последняя команда может быть любая – 1 или 2, т.е. программа может заканчиваться либо на 11, либо на 12. Если программа заканчивается на 11, то до выполнения этих команд было число =22. Если программа заканчивается на 12, то до выполнения этих команд было число 24/2-1=11. Поэтому результатом будет число программ для преобразования 4 в 22 + число программ для преобразования 4 в 11. Для начального числа 4 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды. Построим рекуррентную формулу, связывающую K N с предыдущими элементами последовательности K 1, K 2,…,K N-1 : если N не делится на 2: K N =K N-1 если N делится на 2: K N =K N-1 +K N/2 при условии N/2 4 N KNKN K=3+15=18

Исполнитель Июнь 15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь 15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

1. Прибавить 1 2. Умножить на 2 Построим рекуррентную формулу, связывающую K N с предыдущими элементами последовательности K 1, K 2,…,K N-1 : если N не делится на 2: K N =K N-1 если N делится на 2: K N =K N-1 +K N/2 Так как траектория вычислений программ должна проходить через число 10, сначала определим, сколькими способами можно получить 10 из 1. После этого определим, сколькими способами можно получить 21 из 10. N KNKN N KNKN 14 28

25 (высокий уровень, время – 30 мин) Проверяемые элементы содержания: умения написать короткую (10-15 строк) простую программу на языке программирования или записать алгоритм на естественном языке Что нужно знать: массив – это набор однотипных элементов, имеющих общее имя и расположенных в памяти рядом; для обращения к элементу массива используют квадратные скобки, запись A[i] обозначает элемент массива A с номером (индексом) i; для обработки всех элементов массива используется цикл вида for i:=1 to N do begin { что-то делаем с элементом A[i] } end; переменная i обозначает номер текущего элемента массива, она меняется от 1 до N с шагом 1, то есть мы «проходим» последовательно все элементы;

Что нужно знать: матрица (двухмерный массив) – это прямоугольная таблица однотипных элементов; если матрица имеет имя A, то обращение A[i,k] обозначает элемент, расположенный на пересечении строки i и столбца k; каждая строка матрицы – это обычный (одномерный, линейный) массив; для того, чтобы обработать строку i в матрице из M столбцов, нужно использовать цикл, в котором меняется номер столбца k: for k:=1 to M do begin { что-то делаем с элементом A[i,k] } end; каждый столбец матрицы – это обычный (одномерный, линейный) массив; для того, чтобы обработать столбец k в матрице из N строк, нужно использовать цикл, в котором изменяется номер строки i: for i:=1 to N do begin { что-то делаем с элементом A[i,k] } end;

Операции с элементами массива Линейный поиск элемента: проверка факта наличия в массиве элемента с заданными свойствами; поиск индекса элемента массива, равного некоторому числу; поиск индекса первого элемента массива, равного некоторому числу. Вставка и удаление элементов в массиве: удаление из массива k-го элемента со сдвигом всех расположенных справа от него элементов на одну позицию влево; вставка в массив заданного числа на k-е место со сдвигом элементов на одну позицию вправо.

Операции с элементами массива Перестановка всех элементов массива в обратном порядке. Суммирование элементов массива. Проверка соответствия элементов массива некоторому условию. Нахождение минимального (максимального) значения в данном массиве и количества элементов, равных ему, за однократный просмотр массива. Нахождение второго по величине (максимального или минимального) значения в данном массиве за однократный просмотр массива.

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

Поиск второго максимума Дан целочисленный массив из 30 элементов. Элементы массива могут принимать произвольные целые значения. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит второй максимум массива (элемент, который в отсортированном по невозрастанию массиве стоял бы вторым).

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

Решение: В цикле, начиная с третьего элемента массива, просматриваем очередной элемент: если очередной элемент a[i] > max, то записываем значение max в max2 (предыдущий максимум становится вторым), а значение a[i] записываем в max, иначе, если a[i] max2, если да, то записываем в max2 значение a[i]:

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди элементов массива, которые имеют чётное значение и не делятся на три. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого чётно и не кратно трем. const N=20; var a: array [1..N] of integer; i, j, min: integer; begin for i:=1 to N do readln(a[i]); … end. Определение минимального значения среди элементов массива с заданными условиями

1. Требуется найти минимальный элемент из всех, которые имеют чётное значение и не делятся на Условие, определяющее отбор нужных элементов, запишется в виде (a[i] mod 2 = 0) and (a[i] mod 3 <> 0) 3. Стандартный цикл поиска минимального элемента, удовлетворяющего условию, выглядит так: for i:=1 to N do if and (a[i] < min) then min := a[i]; 4. Для выбора начального значения минимального элемента берем значение 1001 (по условию исходные значения элементов массива лежат в диапазоне от 0 до 1000). Решение:

min:=1001; for i:=1 to N do if (a[i] mod 2=0) and (a[i] mod 3<>0) and (a[i]<min) then min:=a[i]; writeln(min); Фрагмент на языке Паскаль

1 балл Найти произведение двузначных чисел, которые не делятся на 6.

0 баллов Найти произведение двузначных чисел, которые не делятся на 7. В презентации использованы материала с сайта