РАЗДЕЛ “Элементы теории алгоритмов. Программирование”
ПЕРЕЧЕНЬ элементов содержания, проверяемых на ЕГЭ по информатике и ИКТ
1.6.Элементы теории алгоритмов
1.6.1.Формализация понятия алгоритма.
1.6.2.Вычислимость. Эквивалентность алгоритмических моделей.
1.6.3.Построение алгоритмов и практические вычисления.
1.7.Языки программирования
1.7.1.Типы данных.
1.7.2.Основные конструкции языка программирования. Система программирования.
1.7.3.Основные этапы разработки программ. Разбиение задачи на подзадачи.
ПЕРЕЧЕНЬ требований к уровню подготовки, проверяемому на ЕГЭ по информатике и ИКТ
1.1.3.Записывать алгоритмы на естественном языке и в виде блок-схем.
1.1.4.Читать и отлаживать программы на языке программирования.
1.1.5.Создавать программы на языке программирования по их описанию.
Возможные алгоритмические задачи:
ЗАДАНИЯ:
А5. Формальное исполнение алгоритма, записанного на естественном языке (1.6.1, 1.1.3).
А12. Работа с массивами (заполнение, считывание, поиск, сортировка, массовые операции и др.) (1.5.2/1.5.6, 1.1.4).
А13. Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд (1.6.3, 1.1.4).
В2. Умение создавать линейный алгоритм для формального исполни, 1.1.4).
В3. Знание основных алгоритмических конструкций языка программирования (1.7.2, 1.1.4).
В6. Использование переменных. Операции над переменными различных типов в языке программирования (1.7.1, 1.1.4).
В7. Анализ алгоритма, содержащего вспомогательные алгоритмы, цикл и ветвление (1.6.1, 1.1.4).
В13. Умение анализировать результат исполнения алгоритма (1.6.1, 1.1.3).
В14. Умение анализировать программу, использующую процедуры и функции (1.7.2, 1.1.4).
С1. Умение прочесть фрагмент программы на языке программирования и исправить допущенные ошибки (1.7.2, 1.1.4).
С2. Умение написать короткую простую программу на языке программирования или записать алгоритм на естественном языке (1.7.3/1.6.3, 1.1.5/1.1.3).
С3.Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию (1.5.1, 1.1.3).
С4. Умение создавать собственную программу (30-50 строк) для решения задач средней сложности (1.7.3, 1.1.5).
Примерные задания:
1.Кассир забыл пароль к сейфу, но помнил алгоритм его получения из строки «AYY1YABC55»: если последовательно удалить из строки цепочки символов «YY» и «ABC», а затем поменять местами символы A и Y, то полученная последовательность и будет паролем. Определите пароль:
1) A1Y55 2) AA55Y1 4) Y1A55
2.Вася забыл пароль к Windows XP, но помнил алгоритм его получения из строки подсказки «B265C42GC4»: если все последовательности символов «C4» заменить на «F16», а затем из получившейся строки удалить все трехзначные числа, то полученная последовательность и будет паролем. Определите пароль:
1) BFGF16 2) BF42GF16 3) BFGF4 4) BF16GF
3.Дан фрагмент программы:
Бейсик | Паскаль | Алгоритмический |
for i:=1 to 5 for j:=1 to 5 if i=j then a(i, j)=1 else a(i, j)=0 end if next j next i | for i:=1 to 5 do for j:=1 to 5 do if i=j then a[i, j]:=1 else a[i, j]:=0; | нц для i от 1 до 5 нц для j от 1 до 5 если i=j то a[i, j]:=1 иначе a[i,j]:=0 все кц кц |
Чему равна сумма значений элементов массива после выполнения этого фрагмента программы?
1 25
Решение.
1 | 2 | 3 | 4 | 5 | |
1 | 1 | 0 | 0 | 0 | 0 |
2 | 0 | 1 | 0 | 0 | 0 |
3 | 0 | 0 | 1 | 0 | 0 |
4 | 0 | 0 | 0 | 1 | 0 |
5 | 0 | 0 | 0 | 0 | 1 |
1.Цикл с параметром i является внешним циклом (i - номер строки), а цикл с параметром j − внутренним (j – номер столбца).
2.Если i=j, то элементы массива расположены на главной диагонали; если i>j, то элементы массива расположены ниже главной диагонали; если i<j, то элементы массива расположены выше главной диагонали.
Следовательно, в этом массиве на главной диагонали будут расположены элементы, равные 1, а выше и ниже главной диагонали − равные 0. Так как количество строк (или столбцов) равно 5, то и сумма значений элементов массива, расположенных на главной диагонали, будет равна 5.
Правильный ответ: 3.
4.Значения двумерного массива размера 
задаются с помощью вложенного оператора цикла в представленном фрагменте программы:
Бейсик | Паскаль | Алгоритмический |
for i:=1 to n for k:=1 to n if i>k then a(i, k)=1 else a(i, k)=0 end if next k next i | for i:=1 to n do for k:=1 to n do if i>k then a[i, k]:=1 else a[i, k]:=0; | нц для i от 1 до n нц для k от 1 до n если i>k то a[i, k]:=1 иначе a[i,k]:=0 все кц кц |
Как будет зависеть от 
сумма элементов массива после выполнения алгоритма? Напишите формулу вычисления суммы элементов массива в зависимости от .
Решение.
1.Цикл с параметром i является внешним циклом, а цикл с параметром k − внутренним.
1 | 2 | 3 | 4 | … | |
1 | 0 | 0 | 0 | 0 | … |
2 | 1 | 0 | 0 | 0 | … |
3 | 1 | 1 | 0 | 0 | … |
4 | 1 | 1 | 1 | 0 | … |
… | … | … | … | … | … |
2.Если i>k, то элементы массива расположены ниже главной диагонали. Следовательно, в этом массиве ниже главной диагонали будут расположены элементы, равные 1, а выше главной диагонали и на главной диагонали − равные 0.
3.В первой строке нет единичных элементов. Во второй строке А[2,1]=1. В третьей строке А[3,1]=А[3,2]=1 и их сумма равна 2. В −й строке A[n,1]=A[n,2]=…=A[n,n-1]=1 и их сумма равна 
. Таким образом, получаем сумму значений 
.
Полученные значения образуют арифметическую прогрессию, первый член которой равен 1, последний член равен 
, разность арифметической прогрессии равна 1. Формула суммы 
первых членов арифметической прогрессии: 
. По этой формуле определяем сумму: 
.
Ответ: 
.
5[1]Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно снизу свободно
слева свободно справа свободно
6 | ||||||
5 | ||||||
4 | ||||||
3 | ||||||
2 | ||||||
1 | ||||||
A | B | C | D | E | F |
Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
1 0
НАЧАЛО
ПОКА <снизу свободно> вниз
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
