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