Анализ поставленной задачи и определение возможных путей решения

Разделить исходный массив произвольной длины по критерию знака числа (положительное или отрицательное). В новых массивах числа расположить в порядке их следования в исходном массиве. Начальный и конечный адреса массива расположить в ячейках памяти. Формат чисел следующий:

З	Модуль числа

где: З – знак числа.

Поставленная задача подразумевает под собой два задания. Первое: отделить отрицательные числа от положительных и сгруппировать их в виде массивов положительных и отрицательных чисел. Второе: записать в некоторые ячейки памяти адреса конца и начала каждого из массивов.

Рассмотрим возможные пути решения первого задания. Предположим, что исходный массив выглядит следующим образом (рис.1). Где по вертикальной оси указанны номера ячеек памяти, а по горизонтальной номера битов ячеек памяти. Разделение производится по критерию знака, а знак закодирован седьмым битом ячейки памяти, поэтому те ячейки памяти, в которых значение седьмого бита равно единице отделяются от тех, в которых это значение равно нулю. Запишем индексы ячеек с отрицательными операндами: 1, 3, 6. И с положительными: 2, 4, 5. Причем, ячейки записаны в порядке возрастания значения их индекса, именно так они будут расположены в новых массивах(рис.2).

Рисунок2- Конечный массив

Рисунок1–Исходный массив

Рисунок 3- метод№1

Для выполнения этого задания я могу предложить три метода. Назовем их условно: метод 1, метод 2, метод 3. Принцип метода 1 проиллюстрирован на рис.3. Если последовательно перемещаться от первой ячейки памяти до шестой

Рисунок 4 – Метод№2

и менять местами смежные ячейки памяти, в которых в младшей ячейке седьмой бит равен нулю, а в старшей единице, то в результате нескольких проходов (до тех пор, пока не исчезнут комбинации, подходящие для замены) получится требуемый результат. Принцип метода 2 изображен на рис. 4.

Рисунок 5 – Исходный массив

Последовательно перемещаясь от первой ячейки памяти к шестой, программа ищет отрицательные числа, если перед отрицательным числом имеются положительные числа, то оно помещается в буферную ячейку памяти, а ячейка памяти, в которой оно располагалось, становится вакантной. Затем все положительные числа сдвигаются вперед на одну ячейку, освобождая, таким образом, начальную или смежную с отрицательной ячейку памяти. В эту ячейку из буферной ячейки перемещается отрицательное число. После прохождения всех шести ячеек мы получим отсортированный массив. Метод 3 проиллюстрирован на рис.5. Последовательно перемещаясь от первой ячейки к шестой, программа ищет отрицательные числа, найдя отрицательное число, она записывает его в новую ячейку памяти вне исходного массива. Следующее отрицательное число записывается в ячейку с адресом увеличенным на единицу. После первого прохождения массива, начинается второе прохождение, но теперь уже программа ищет положительные числа и последовательно размещает их в ячейках памяти.

Сравнивая эти три метода особо нужно выделить третий, от первого и второго его отличает то, что исходный массив не подвергается изменениям. Это может пригодиться при решении некоторых задач. Однако недостатком этого метода является требовательность к памяти, для своей работы он нуждается в два раза большем количестве ячеек памяти, чем первый и второй методы. Поскольку значительную часть времени выполнения программ по трем методам занимают перемещения чисел в памяти, следует отметить, что для данного метода количество перемещений из одной ячейки памяти в другую легко вычисляемо и равно количеству ячеек памяти исходного массива. При неизменном размере исходного массива количество перемещений будет постоянно. В первом и втором методах количество таких перемещений зависит от комбинаций чисел массива и может быть большим или меньшим чем в третьем методе. Для примера возьмем массив рис.1. На перемещение ячеек памяти влияют значения седьмого бита, запишем значения седьмых битов ячеек памяти данного массива в формате 6,5,4,3,2,1: 100101. Первым методом потребуется выполнить 4 замены: 100101→₁ 100011→₂ 010011→₃ 001011→₄ 000011. Вторым методом потребуется выполнить четыре сдвига ячеек памяти: 100101→ 100□01(перемещаем ноль влево)= 1000□1(вставляем из буфера единицу)= 100011→ □00011(перемещаем три ноля влево)= 000□11 (вставляем из буфера единицу)= 000111. При использовании третьего метода количество перемещений будет равно количеству ячеек памяти массива, в данном случае шести. Теперь возьмем комбинацию 110000: для первого метода количество замен будет равно восьми, для второго метода количество сдвигов будет так же равно восьми, а для третьего метода, оно уже будет равняться шести. Однако количество замен, количество сдвигов и количество перемещений не эквиваленты. Перемещение операнда из одной ячейки памяти в другую для КР580ВМ80 в общем виде состоит из двух этапов. Первый этап это перемещение операнда из исходной ячейки памяти в регистр микропроцессора, второй этап перемещение из регистра микропроцессора в целевую ячейку памяти. Рассмотрим первый метод: замена значений ячеек памяти может выглядеть следующим образом: первая ячейка памяти помещается в один из регистров микропроцессора, вторая ячейка памяти помещается во второй регистр, затем из первого регистра операнд помещается во вторую ячейку, а из второго в первую. Таким образом, замена в первом методе эквивалентна двум перемещениям операнда из одной ячейки памяти в другую. Во втором методе происходит сдвиг положительных операндов на одну ячейку, который эквивалентен перемещению «из ячейки в ячейку», но помимо сдвига отрицательный операнд перемещается в буфер, а за тем из буфера обратно в освободившуюся ячейку памяти. Если в роли буфера использовать регистр микропроцессора, то перемещение отрицательного числа будет эквивалентно одному перемещению «из ячейки в ячейку». Значит количеству сдвигов вторым методом эквивалентно на единицу большее количество перемещений «из ячейки в ячейку». Основываясь на этом, запишем эквивалентное количество перемещений «из ячейки в ячейку» для двух приведенных примеров. Для комбинации 100101: первый метод 4*2=8, второй метод 4+1=5, третий метод=6. Для комбинации 110000: первый метод 8*2=16, второй метод 8+1=9, третий метод=6.

Помимо операций перемещения чисел в памяти все три метода предусматривают использование операций определения знака. Несмотря на различия методов можно выделить некоторые общие особенности этих операций. Во-первых: определение знака производится последовательно от младшей ячейки памяти к старшей. Во-вторых: всякое число при движении от младшей ячейки к старшей проверяется как минимум один раз. Из первой особенности следует, что в программах придется использовать указатель проверяемого числа, который будет хранится в регистре микропроцессора или в ячейке памяти и в начале программы примет значение адреса самой младшей ячейки исходного массива, а затем инкрементируясь достигнет значения адреса старшей ячейки. Использование указателя проверяемого числа подразумевает его сравнение со значением старшего адреса исходного массива после каждой операции инкрементации. Чем больше проходов от младшей ячейки исходного массива к младшей, тем больше количество таких сравнений. Другое свойство: поскольку при использовании первого и третьего методов приходится совершать несколько проходов, то из второй особенности следует, что знак числа будет проверен несколько раз. Для третьего метода, например, количество проходов - всегда одинаково и равно двум, по этому всякое число массива при использовании этого метода будет проверенно два раза. Таким образом, чем выше число проходов, тем больше повторяющихся операций, что соответственно увеличивает время выполнения программы. Самое высокое число проходов достижимо при использовании первого метода, по этому критерию он менее рационален, чем второй и третий методы.

На этом рассмотрение первой части поставленной задачи считаю законченной, и для ее решения мне представляется наиболее рациональным использование второго метода из-за меньшего количества повторяющихся операций, относительно меньшего количества операций перемещения чисел в памяти и как следствие - более высокого быстродействия. Главным недостатком первого метода является низкое быстродействие, второго метода – дополнительное использование памяти, равняющееся размеру исходного массива (так как размеры исходного массива не определены заданием и могут изменяться, этот критерий является критичным).

Вторая часть поставленной задачи состоит в том, что бы записать в некоторые ячейки памяти адреса конца и начала массивов отрицательных и положительных чисел. Это можно было бы сделать двумя способами. Первый входит в программу разделения массивов, второй – запускается после того как массивы разделены. Поскольку выбран второй метод разделения массива, при определении адресов начала и конца новых массивов параллельно с программой их разделения, пришлось бы выделять регистры или ячейки памяти, что бы запоминать изменяющиеся состояния исходного массива, удобнее проанализировать конечный результат. В дополнение к этому программа становится более наглядной, когда за каждую задачу отвечает отдельный ее блок. При использовании второго метода разделения массивов конечные массивы будут смежными (конец одного, находится в соседней ячейке с началом другого), значит достаточно определить начало положительного массива, а конец отрицательного можно просто вычислить вычитанием единицы из адреса начала положительного массива. Программа определения начала положительного массива будет работать следующим образом. Поскольку новые массивы находятся в области памяти исходного массива будем перемещать указатель адреса от младшего значения к старшему и проверять знак при каждом перемещении. При нахождении положительного числа запишем значение указателя адреса в отведенную для этого ячейку памяти, это и будет начальным адресом положительного массива. Конечный адрес отрицательного массива записывать не будем, потому что он легко вычисляется.

Дата добавления: 2015-08-31