Оценка скорости работы алгоритмов

Данное задание проверяет знание зависимости количества операций при обработке массива от размера массива. В зависимости от алгоритма эта зависимость может быть линейной, квадратичной или логарифмической. В некоторых случаях алгоритм в задании описывается явным образом, в некоторых экзаменуемый должен вспомнить стандартный алгоритм, применяемый в таком случае. Если в задании встречается определение «эффективный алгоритм», то это означает, что из известных стандартных алгоритмов надо выбрать самый быстрый.

Задание 9.

Следующий фрагмент программы записывает в переменную Max максимальный элемент в двумерном массиве Dist размера N*N, наполненном неотрицательными числами:

For i:=1 to N Do

For j:=1 to N Do

If Dist[I,j]>Max Then Max:= Dist[I,j];

На очень медленном компьютере эта программа при N=1000 работала 5 секунд. Определите время работу этой программе на том же компьютере при N=2000:

1) 10 сек.;

2) 20 сек.;

3) 30 сек.;

4) 40 сек.

Решение.

В данном алгоритме два вложенных оператора цикла. При увеличении N в два раза количество проверок (выполнений оператора If) возрастет в 2², т.е. в 4 раза, что соответствует варианту ответа №2.

Ответ: 2.

Задание 10. (Задание А19 демоверсии 2005 г.)

Стандартный алгоритм вычисления среднего арифметического элементов числового массива из миллиона элементов работает 0, 5 сек. Оцените время работы того же алгоритма на том же компьютере, если длина массива 3 миллиона.

1) 1 сек.;

2) 1,5 сек.;

3) 3 сек.;

4) 4,5 сек.

Решение.

Для вычисления среднего арифметического N чисел необходимо выполнить N операций сложения. При увеличении количества элементов в 3 раза время выполнения алгоритма возрастает линейно - так же в 3 раза. Следовательно, время будет равно 0,5*3=1,5(сек), что соответствует варианту ответа №2.

Ответ: 2.

Работа с исполнителями

Задание 11. (Задания А 23 демоверсии 2005, А20 демоверсии 2006 г.)

Исполнитель Черепашка перемещается на экране компьютера, оставляя след виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:

Вперед n, где n - целое число, вызывающая передвижение черепашки на n шагов в направлении движения.

Направо m, где m - целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.

Запись Повтори 5 [Команда1 Команда2] означает, что последовательность команд в скобках выполняется 5 раз.

Черепашки был дан для исполнения следующий алгоритм:

Повтори 5 [вперед 10 направо 72]

Какая фигура появится на экране?

1) Незамкнутая ломаная линия

2) Правильный треугольник

3) Квадрат

4) Правильный пятиугольник.

Решение.

Исполнитель Черепашка прочертит на экране 5 линий, угол между соседними из которых будет равен 72°(=360°/5). Поэтому в результате получится правильный пятиугольник, что соответствует варианту ответа №4.

Ответ: 4.

Список литературы

№	Название литературы
1.	Учебно-тренировочные материалы для подготовки к единому государственному экзамену. Информатика/ Крылов С.С., Лещинер В.Р., Супрун П.Г., Якушкин П.А.; под ред. Лещинера В.Р. – М. Интеллект-Центр, 2005 – 136 с.
2.	Андреева Е.В. Информатика. Основы алгоритмизации. Тетрадь с печатной основой. – Саратов: «Лицей», 2000. – 80 с.
3.	Экзаменационные вопросы и ответы. 11 класс/ Л.Л. Босова, Н.Д. Угринович. – М.: БИНОМ. Лаборатория знаний, 2003. – 191 с.: ил.
4.	Шпаргалки по информатике./ Е.Ю. Пестерева. – М.: Издательство
5.	Информатика и информационные технологии. Учебник для 10-11 классов/Н.Д. Угринович. – М.: Лаборатория Знаний, 2003. 512 с.: ил.
6.	Угринович Н.Д., Босова Л.Л., Михайлова Н.И. Практикум по информатике и информационным технологиям. Учебное пособие для образовательных учреждений. – М.: Лаборатория Базовых Знаний, 2001. 256 с.: ил.
7.	Единый государственный экзамен по информатике. Демонстрационный вариант 2004 г.
8.	Единый государственный экзамен по информатике. Демонстрационный вариант 2005 г.
9.	Единый государственный экзамен по информатике. Демонстрационный вариант 2006 г.

Задания для самостоятельного решения

1.Определите значение переменной b после выполнения следующего фрагмента алгоритма (см. рис.11):

1) 6;

2) 5;

3) 3;

4) 4.

2.Определите значение переменной a после выполнения алгоритма (см. рис.12):

1) 5;

2) 11;

3) 23;

4) 47.

3. Определите значение переменной s после выполнения фрагмента алгоритма (см. Рис. 13).

4. Определите значение целочисленных переменных x, y и t после выполнения фрагмента программы:

Бейсик	Паскаль	Алгоритмический
x=4 y=16 t=x x=y MOD x y=t+1	x:=4; y:=16; t:=x; x:=y Mod x; y:=t+1;	x:=4 y:=16 t:=x x:=MOD (y,x) y:=t+1

1) x=4; y=1; t=0;

2) x=0; y=5; t=4;

3) x=0; y=4; t=5;

4) x=4; y=1; t=5.

5. Определите значение целочисленных переменных b и c после выполнения фрагмента программы:

Бейсик	Паскаль	Алгоритмический
a=37 b=a MOD 10 c=a\10	a:=37; b:=a Mod 10; c:=a Div 10;	a:=37 b:=Mod (a,10) c:= Div (a,10)

1) b=3; c=7;

2) b=7; c=3;

3) b=3; c=4;

4) b=4; c=3.

6. Определите значение целочисленных переменных a и b после выполнения фрагмента программы:

Бейсик	Паскаль	Алгоритмический
a=20 b=7 a=a\b b=a*b a=b\a	a:=20; b:=7; a:=a Div b b:=a*b; a:=b Div a;	a:=20 b:=7 a:=Div (a,b) b:=a*b a:=Div (b,a)

1) a=7; b=21;

2) a=7; b=7;

3) a=7; b=14;

4) a=3; b=21.

7. Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы:

Бейсик	Паскаль	Алгоритмический
FOR n=1 TO 500 FOR k=1 TO 500 B(n,k)=n(n+1)k/2 NEXT k NEXT n	For n:=1 To 500 Do For k:=1 To 500 Do B[n,k]:= n(n+1)k/2	н.ц. для n от 1 до 500 н.ц.для k от 1 до 500 B[n,k]:= n(n+1)k/2 к.ц. к.ц.

Чему будет равно значение B(19,21)?

8. Все элементы массива А размером 10*10 элементов первоначально были равны 1. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы:

Бейсик	Паскаль	Алгоритмический
FOR n=1 TO 5 FOR k=1 TO 5 А(n,k)=A(n,k)-1 NEXT k NEXT n	For n:=1 To 5 Do For k:=1 To 5 Do A[n,k]:= A[n,k]-1	н.ц. для n от 1 до 5 н.ц.для k от 1 до 5 A[n,k]:= A[n,k]-1 к.ц. к.ц.

Сколько элементов массива в результате будут равны 0?

9. Все элементы массива А размером 10*10 элементов первоначально были равны 1. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы:

Бейсик	Паскаль	Алгоритмический
FOR n=1 TO 4 FOR k=1 TO n+1 А(n,k)=A(n,k)-1 А(n,k+1)=A(n,k)-1 NEXT k NEXT n	For n:=1 To 4 Do For k:=1 To n+1 Do Begin A[n,k]:= A[n,k]-1; A[n,k+1]:= A[n,k]-1; End;	н.ц. для n от 1 до 5 н.ц.для k от 1 до n+1 A[n,k]:= A[n,k]-1 A[n,k+1]:= A[n,k]-1 к.ц. к.ц.

Сколько элементов массива в результате будут равны 0?

10. Стандартный алгоритм вычисления среднего арифметического элементов числового массива из тысячи элементов работает 0,01 сек. Оцените время работы того же алгоритма на том же компьютере, если длина массива миллион элементов.

1) 1 сек.;

2) 5 сек.;

3) 10 сек.;

4) 0,1 сек.

11. Исполнитель Черепашка перемещается на экране компьютера, оставляя след виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:

Вперед n, где n - целое число, вызывающая передвижение черепашки на n шагов в направлении движения.

Направо m, где m - целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.

Запись Повтори 5 [Команда1 Команда2]означает, что последовательность команд в скобках выполняется 5 раз.

Черепашки был дан для исполнения следующий алгоритм:

Повтори 4 [вперед 10 направо 120]

Какая фигура появится на экране?

1) Незамкнутая ломаная линия

2) Правильный треугольник

3) Квадрат

4) Правильный пятиугольник.

12. Исполнитель - тот же, что и в предыдущем задании. Какое натуральное число следует поставить вместо переменной N в следующем алгоритме:

Повтори 6 [вперед 60 направоN]