Geum.ru

Перечень требований к уровню подготовки, проверяемому на егэ по информатике и икт

Вид материалаДокументы

Содержание


1.Цикл с параметром i
3.В первой строке нет единичных элементов. Во второй строке А[2,1]=1
НАЧАЛО ПОКА вниз
Подобный материал:
РАЗДЕЛ “Элементы теории алгоритмов. Программирование”

ПЕРЕЧЕНЬ элементов содержания, проверяемых на ЕГЭ по информатике и ИКТ



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.6.1, 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) A155 3) A55Y1 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) 1 2) 0 3) 5 4) 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, то элементы массива расположены выше главной диагонали.

Следовательно, в этом массиве на главной диагонали будут расположены элементы, равные 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. Формула суммы первых членов арифметической прогрессии: . По этой формуле определяем сумму: .

Ответ: .



51Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

вверх вниз влево вправо.

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно снизу свободно

слева свободно справа свободно




















6



















5



















4



















3



















2



















1

A
B
C
D
E
F


Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?

1) 1 2) 2 3) 3 4) 0

НАЧАЛО

ПОКА <снизу свободно> вниз

ПОКА <слева свободно> влево

ПОКА <сверху свободно> вверх

ПОКА <справа свободно> вправо

КОНЕЦ




















































































































































Решение:
  1. легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:

на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;
  1. кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода
  2. обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:



























































  3. итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:













    6

















    5


















    4


















    3

















    2


















    1

    A
    B
    C
    D
    E
    F


  4. этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:














    6


















    5


















    4


















    3


















    2


















    1

    A
    B
    C
    D
    E
    F


  5. проверяем оставшиеся три клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:















6



















5



















4



















3


















2



















1

A
B
C
D
E
F




















6



















5



















4



















3



















2



















1

A
B
C
D
E
F





















6


















5



















4



















3



















2



















1

A
B
C
D
E
F





  1. итак, условию удовлетворяет только одна клетка – F4
  2. таким образом, правильный ответ – 1.



6.У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь влево

2. вычти 1

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












1 Задача взята с сайта К. Полякова