2012 - Оптимизация кода
В ходе разработки сложного программного проекта произошел сбой в системе обработки исходного кода проекта. В результате появился «мусорный» код, что затрудняло понимание работы программы, но при этом программа осталась работоспособной.
Проанализируйте приведенный ниже код. Какую задачу он выполняет? Оптимизируйте его, убрав «мусор»
ДАНО массив A[N], k, i, j, a2132, a3456, a6677, i1289
ЦИКЛ1
НАЧИНАЯ с k=0; ПОКА k<N+1; k ПРИБАВЛЯТЬ 1
i1289 = k
ЦИКЛ2
НАЧИНАЯ С j=1; ПОКА j<N; j ПРИБАВЛЯТЬ 1
a2132 = A[j]
ЦИКЛ3
НАЧИНАЯ С i=j; ПОКА i>0; i УМЕНЬШАТЬ НА 1
НАЧАЛО
a2132 = А[i-1]
ЕСЛИ A[i] < a2132
НАЧАЛО
i1289 = A[i]
A[i] = a2132
A[i-1] = i1289
КОНЕЦ
КОНЕЦЦИКЛ3
k = a6677
КОНЕЦ ЦИКЛ2
КОНЕЦ ЦИКЛ1
Показать решение
Перепишем текст программы так, чтобы он оказался четко структурированным, а переменные приняли удобочитаемые имена.
(01) ДАНО массив A[N], k, i, j, B, C, D, E
(02) ЦИКЛ1
(03) НАЧИНАЯ с k=0; ПОКА k<N+1; k ПРИБАВЛЯТЬ 1
(04) E = k
(05) ЦИКЛ2
(06) НАЧИНАЯ С j=1; ПОКА j<N; j ПРИБАВЛЯТЬ 1
(07) B = A[j]
(08) ЦИКЛ3
(09) НАЧИНАЯ С i=j; ПОКА i>0; i УМЕНЬШАТЬ НА 1
(10) НАЧАЛО
(11) B = А[i-1]
(12) ЕСЛИ A[i] < B
(13) НАЧАЛО
(14) E = A[i]
(15) A[i] = B
(16) A[i-1] = E
(17) КОНЕЦ
(18) КОНЕЦ ЦИКЛ3
(19) k = D
(20) КОНЕЦ ЦИКЛ2
(21) КОНЕЦ ЦИКЛ1
Заметим, что (07) избыточно, поскольку в (11) переназначается B и, судя по коду (11)-(16) переменная B вообще не нужна. Получаем:
(01) ДАНО массив A[N], k, i, j, C, D, E
(02) ЦИКЛ1
(03) НАЧИНАЯ с k=0; ПОКА k<N+1; k ПРИБАВЛЯТЬ 1
(04) E = k
(05) ЦИКЛ2
(06) НАЧИНАЯ С j=1; ПОКА j<N; j ПРИБАВЛЯТЬ 1
(08) ЦИКЛ3
(09) НАЧИНАЯ С i=j; ПОКА i>0; i УМЕНЬШАТЬ НА 1
(10) НАЧАЛО
(12) ЕСЛИ A[i] < А[i-1]
(13) НАЧАЛО
(14) E = A[i]
(1 5) A[i] = А[i-1]
(16) A[i-1] = E
(17) КОНЕЦ
(18) КОНЕЦ ЦИКЛ3
(19) k = D
(20) КОНЕЦ ЦИКЛ2
(21) КОНЕЦ ЦИКЛ1
Рассуждая аналогично, приходим к выводу, что (19) и (4), а переменные D и С не нужны. Получаем:
(01) ДАНО массив A[N], k, i, j, E
(02) ЦИКЛ1
(03) НАЧИНАЯ с k=0; ПОКА k<N+1; k ПРИБАВЛЯТЬ 1
(05) ЦИКЛ2
(06) НАЧИНАЯ С j=1; ПОКА j<N; j ПРИБАВЛЯТЬ 1
(08) ЦИКЛ3
(09) НАЧИНАЯ С i=j; ПОКА i>0; i УМЕНЬШАТЬ НА 1
(10) НАЧАЛО
(12) ЕСЛИ A[i] < А[i-1]
(13) НАЧАЛО
(14) E = A[i]
(1 5) A[i] = А[i-1]
(16) A[i-1] = E
(17) КОНЕЦ
(18) КОНЕЦ ЦИКЛ3
(20) КОНЕЦ ЦИКЛ2
(21) КОНЕЦ ЦИКЛ1
В (12)-(17) производится перестановка элементов массива по условию их сравнения. Цикл 2 и цикл 3 позволяют тотально перебрать все элементы массива и после того, как они будут правильно расставлены, новый перебор в цикле 1 не даст нового результата, следовательно, цикл 1 также избыточен и переменная k не нужна. Получаем:
(01) ДАНО массив A[N], i, j, E
(05) ЦИКЛ2
(06) НАЧИНАЯ С j=1; ПОКА j<N; j ПРИБАВЛЯТЬ 1
(08) ЦИКЛ3
(09) НАЧИНАЯ С i=j; ПОКА i>0; i УМЕНЬШАТЬ НА 1
(10) НАЧАЛО
(12) ЕСЛИ A[i] < А[i-1]
(13) НАЧАЛО
(14) E = A[i]
(1 5) A[i] = А[i-1]
(16) A[i-1] = E
(17) КОНЕЦ
(18) КОНЕЦ ЦИКЛ3
(20) КОНЕЦ ЦИКЛ2
Это и будет результирующей программой, в которой, если вернуться к прежнему обозначению переменных, следует заменить имя E на i1289.
Показать ответ
(01) ДАНО массив A[N], i, j, E
(05) ЦИКЛ2
(06) НАЧИНАЯ С j=1; ПОКА j<N; j ПРИБАВЛЯТЬ 1
(08) ЦИКЛ3
(09) НАЧИНАЯ С i=j; ПОКА i>0; i УМЕНЬШАТЬ НА 1
(10) НАЧАЛО
(12) ЕСЛИ A[i] < А[i-1]
(13) НАЧАЛО
(14) E = A[i]
(1 5) A[i] = А[i-1]
(16) A[i-1] = E
(17) КОНЕЦ
(18) КОНЕЦ ЦИКЛ3
(20) КОНЕЦ ЦИКЛ2
<< Назад в раздел (Все задания)
