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

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

Задание 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) возрастет в 22, т.е. в 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 To500 Do Fork:=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 To5 Do Fork:=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 To4 Do Fork:=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]

Чтобы на экране появился правильный пятиугольник?

Ответык заданиям для самостоятельного решения

Задание

Ответ

Статьи к прочтению:

Сложность алгоритма Большое О

Похожие статьи: