Лабораторная работа № 2. Определение сложности, эквивалентные преобразования и оптимизация алгоритмов

Лабораторная работа № 2

Определение сложности, эквивалентные преобразования и оптимизация алгоритмов

Вычисление и преобразование алгоритмов.

1. Вычислите результат работы заданного алгоритма.

Начало

X = 1

Y = X + 1

Y = X – 1

Вывод Y

Конец

2. Вычислите результат работы заданного алгоритма.

Циклдо X > 5

X = 1; Y = 0

Цикл

Начало

Y =Y + X

Конец

3. Определите какой результат выдаст заданный алгоритм.

Цикл

X = 1; Y= 0

Цикл пока X £ 5

Начало

X = X + 1 Y =Y + X

Конец

Вывод X, Y

4. Определите какой результат выдаст заданный алгоритм.

(ц)

s = 1

(ц) i = -1, 5

Начало

s = s * i

Конец

Вывод s

5. Вычислите результат работы заданного алгоритма.

Начало выполнения:

Ввод последовательности А из N элементов

B = 0

С = 0

i = 0

Цикл при i < 1

Если A[i] < 0 то

B = B + A[i]

иначе

С = С + 1

конец_если

конец_цикла

Вывод (В, С)

конец_выполнения.

6. Определите какую задачу решает заданный алгоритм.

Начало выполнения:

Ввод последовательности А из N элементов

B = A[1]

Для i = 1 до N

Если В > A[i] то

B = A[i]

конец_если

конец_для

Вывод (В)

конец_выполнения.

7. Определите какую задачу решает заданный алгоритм.

Начало выполнения:

Ввод последовательности А из N элементов

B = 0

С = 0

Для i = 1 до N

Если A[i] < 0 то

B = B + A[i]

иначе

С = С + 1

конец_если

конец_для

Вывод (В, С)

конец_выполнения.

8. Определите какой результат выдаст заданный алгоритм.

Начало выполнения:

N = 5

A[N] = 1

Для i = N до 2 с шагом -1

A[i-1] = A[i] - 2

конец_для

Вывод последовательности А

конец_выполнения.

9. Определите какой результат выдаст заданный алгоритм.

Начало выполнения:

x = 1

y = 0

Цикл

x = x + 1

y = y + x

до x < 5

Вывод х, у

конец_выполнения.

10. Определите являются ли заданные алгоритмы эквивалентными.

Циклдо X > 5

X = 1; Y = 0

Цикл

Начало

Y =Y + X X = X + 1

Конец

Вывод X, Y

Цикл

X = 1; Y=1

Цикл при X< 5

Начало

X = X + 1 Y =Y + X

Конец

Вывод X, Y

11. Определите оценки алгоритмической, временной и емкостной сложности заданного алгоритма

Цикл

X = 1; Y = 0

Цикл пока X £ 5

Начало

X = X + 1 Y =Y + X

Конец

Вывод X, Y

12. Выполните эквивалентное преобразование алгоритма путем замены цикла с предусловием на цикл с постусловием

Цикл

Y = 0; N = 20

Цикл пока X £ N

Начало

X = X + 1 Y =Y + X

Конец

Вывод X, Y

Ввод X

13. Оптимизируйте алгоритм из задания 12 путем использования более эффективного метода решения задачи. Сравните эти алгоритмы по алгоритмической, временной и емкостной сложности.