Формирование программ сортировки почтовых единиц

Результатом распознавания ПИ в современных АЛСМ является нанесение на лист ШК, управляющий направлением письма в соответствующий накопитель АЛСМ.

При k -этапный сортировке ПК указанный ШК должен состоять из к частей, каждая из которых управляет направлением письма в соответствующий накопитель АЛСМ на каждом из k этапов сортировки ПК.

Составление таблиц многоэтапного сортировки ПК является трудоемкой однообразной работой, проверить правильность которой достаточно проблематично.

В то же время, существует возможность автоматизированного составления таблиц многоэтапного сортировки ПК, основанной на ее алгебраической интерпретации.

Пусть т - количество ОПЗ, в которых производится сортировка ПК, а, следовательно, количество ПИ, подлежащих распознаванию. При этом существует однозначная связь между каждым из этих ПИ и номером ОПЗ отвечает ему.

При наличии п накопителей АЛСМ последовательность номеров накопителей, в которые должен направляться письмо, адресованное в ОПЗ N , на этапах сортировки, может быть получена по представлению записи числа N в позиционной системе счисления с основанием п.

Напомним, что запись целого числа в позиционной системе счисления с основанием п имеет вид

где к - минимальная степень я, при которой выполняется неравенство ;

- Цифры числа N, которые принимают значения Основа системы счисления равно количеству накопителей АЛСМ и связана со значением М соотношением

где - значение , округленное до ближайшего большего целого числа.

Так, при т = 15625, значение я равна:

- При двухэтапном сортировке ПК ;

- При трехэтапный сортировке ПК .

В соответствии с этим, при двухэтапном сортировке ПК при трехэтапный - , а значение номеров накопителей, в которые направляется письмо на каждом этапе сортировки, совпадают со значениями соответствующих цифр представления числа N в позиционной системе счисления с основанием п.

Например, номер ОПЗ N = 12345 в позиционной системе счисления с основанием имеет вид , а в позиционной системе счисления с основанием

В приведенных записях числа, находящихся в скобках - это значения соответствующих цифр десятичного числа 12345, которое представлено в позиционных системах счисления с основаниями 125 и 25.

Из записи числа 12345 в позиционных системах счисления с основаниями 125 и 25 следует, что при двухэтапном нисходящем сортировке письмо, адресованное к ОПЗ N = 12345, направляется соответственно в накапливаемые , ; при двухэтапном восходящем сортировке - соответственно в накапливаемые , ; при трехэтапный нисходящем сортировке - соответственно в накапливаемые ; при трехэтапный восходящем сортировке - соответственно в накапливаемые

Напомним, что принципиальными различиями нисходящего и восходящего сортировки ПК является то, что при нисходящем сортировке на каждом текущем этапе сортировки выполняется поочередное сортировки писем , направленных в накапливаемые АЛСМ на предыдущем этапе сортировки, а при восходящем сортировке - объединенное сортировки всех указанных писем.

Принципы автоматизированного составления таблиц двухэтапного нисходящего и восходящего сортировки ПК при и трехэтапного нисходящего и восходящего сортировки ПК при проиллюстрировано соответственно в табл. 3.7 и 3.8.

Таблица 3.7 - Иллюстрация принципов автоматизированного составления таблиц двухэтапного нисходящего и восходящего сортировки ПК при п = 125, т = 15625

нисходящее сортировка

восходящее сортировка

00000

(000) (000)

00000

(000) (000)

00001

(000) (001)

00125

(001) (000)

00124

(000) (124)

15500

(124) (000)

00125

(001) (000)

00001

(000) (001)

00126

(001) (001)

0126

(001) (001)

00249

(001) (124)

15501

(124) (001)

00250

(002) (000)

00002

(000) (002)

00251

(002) (001)

0127

(001) (002)

00374

(002) (124)

15502

(124) (002)

15500

(124) (000)

00124

(000) (124)

15501

(124) (001)

00249

(001) (124)

15624

(124) (124)

15624

(124) (124)

Таблица 3.8 - Иллюстрация принципов автоматизированного составления таблиц трехэтапного нисходящего и восходящего сортировки ПК при п = 125, т = 15625

нисходящее сортировка

восходящее сортировка

00000

(00) (00) (00)

00000

(00) (00) (00)

00001

(00) (00) (01)

00625

(01) (00) (00)

00024

(00) (00) (24)

15000

(24) (00) (00)

00025

(00) (01) (00)

00025

(00) (01) (00)

00026

(00) (01) (01)

00650

(01) (01) (00)

00049

(00) (01) (24)

15025

(24) (01) (00)

00600

(00) (24) (00)

00600

(00) (24) (00)

00601

(00) (24) (01)

01225

(01) (24) (00)

00624

(00) (24) (24)

15600

(24) (24) (00)

00625

(01) (00) (00)

00001

(00) (00) (01)

00626

(01) (00) (01)

00626

(01) (00) (01)

00649

(01) (00) (24)

15001

(24) (00) (01)

15600

(24) (24) (00)

00624

(00) (24) (24)

15601

(24) (24) (01)

01249

(01) (24) (24)

15624

(24) (24) (24)

15624

(24) (24) (24)

В табл. 3.9 и 3.10 приведены примеры нисходящего и восходящего двухэтапного сортировки писем, адресованных в разные ОПЗ, при п = 125, т = 15625, и нисходящего и восходящего трехэтапного сортировки тех же писем при п = 25 т - 15625 соответственно с использованием изложенных принципов автоматизированной сборки таблиц сортировки.

Таблица 3.9 - Пример нисходящего и восходящего двухэтапного сортировки ПК при n = 125, т = 15625

нисходящее сортировка

восходящее сортировка

этап 1

этап 2

этап 1

этап 2

1

2

3

4

5

6

7

8

9

10

00696

(005) (071)

(000)

00111

(111)

00111

(000)

08000

(000)

00111

15205

(121) (080)

(004)

00624

(032)

00532

(000)

01625

(004)

00532

08075

(064) (075)

(004)

00532

(124)

00624

(001)

03626

(004)

00624

00111

(000) (111)

(005)

00696

(060)

00685

(011)

01011

(005)

00685

05391

(043) (016)

(005)

00685

(071)

00696

(016)

05391

(005)

00696

03690

(029) (065)

(008)

01011

(011)

01011

(024)

01649

(008)

01011

04712

(037) (087)

(013)

01710

(000)

01625

(025)

15150

(013)

01625

01710

(013) (085)

(013)

01625

(024)

01649

(025)

05400

(013)

01649

15150

(121) (025)

(013)

01649

(085)

01710

(026)

04651

(013)

01710

00624

(004) (124)

(029)

03690

(001)

03626

(032)

00532

(029)

03626

05440

(043) (065)

(029)

03685

(060)

03685

(060)

03685

(029)

03685

08000

(064) (000)

(029)

03626

(065)

03690

(060)

00685

(029)

03690

01625

(013) (000)

(037)

04712

(026)

04651

(065)

03690

(037)

04651

01011

(008) (011)

(037)

04725

(087)

04712

(065)

05440

(037)

04712

03685

(029) (060)

(037)

04651

(100)

04725

(071)

00696

(037)

04725

04725

(037) (100)

(043)

05391

(016)

05391

(075)

08075

(043)

05391

08099

(064) (099)

(043)

05440

(025)

05400

(075)

15200

(043)

05400

15200

(121) (075)

(043)

05400

(065)

05440

(080)

15205

v 1 (043)

05440

00685

(005) (060)

(064)

08075

(000)

08000

(085)

01710

(064)

08000

01649

(013) (024)

(064)

08000

(075)

08075

(087)

04712

(064)

08075

00532

(004) (032)

(064)

08099

(099)

08099

(099)

08099

(064)

08099

04651

(037) (026)

_ (121)

15205

(025)

15150

(100)

04725

(121)

15150

05400

(043) (025)

(121)

15150

(075)

15200

(111)

00111

(121)

15200

03626

(029) (001)

(121)

15200

(080)

15205

(124)

00624

(121)

15205

Таблица 3.10 - Пример нисходящего и восходящего трехэтапного сортировки ПК при п - 25 т = 15625

N

N 25

нисходящее сортировка

восходящее сортировка

этап 1

этап 2

этап 3

этап 1

этап 2

этап 3

00696

(01) (02) (21)

(00)

00111

(04)

00111

(И)

00111

(00)

08075

(02)

00685

(00)

00111

15205

(24) (08) (05)

(00)

00624

(21)

00532

(07)

00532

(00)

15150

(02)

00696

(00)

00532

08075

02) (23) (00)

(00)

00532

(24)

00624

(24)

00624

(00)

08000

(04)

00111

(00)

00624

00111

(00) (04) (11)

(01)

00696

(02)

00696

(10)

00685

(00)

01625

(06)

15150

(01)

00685

05391

(08) (15) (16)

(01)

01011

(02)

00685

(21)

00696

(00)

04725

(08)

15200

(01)

00696

03690

(05) (22) (15)

(01)

00685

(15)

01011

(11)

01011

(00)

15200

(08)

15205

(01)

01011

04712

(07) (13) (12)

(02)

01710

( 15 )

01625

(00)

01625

(00)

05400

(11)

04651

(02)

01625

01710

(02) (18) (10)

(02)

01625

(15)

01649

(24)

01649

(01)

04651

(13)

04712

(02)

01649

15150

(24) (06) (00)

(02)

01649

(18)

01710

(10)

01710

(01)

03626

(14)

04725

(02)

01710

00624

(00) (24) (24)

(05)

03690

(20)

03626

(01)

03626

(05)

15205

(15)

01625

(05)

03626

05440

(08) (17) (15)

(05)

03685

(22)

03690

(10)

03685

(07)

00532

(15)

01011

(05)

03685

08000

(12) (20) (00)

(05)

03626

(22)

03685

(15)

03690

(10)

01710

(15)

05391

(05)

03690

01625

(02) (15) (00)

(07)

04712

(11)

04651

(01)

04651

(10)

03685

(15)

01649

(07)

04651

01011

(01) (15) (11)

(07)

04725

(13)

04712

(12)

04712

(10)

00685

(16)

05400

(07)

04712

03685

(05) (22) (10)

(07)

04651

(14)

04725

(00)

04725

(11)

00111

(17)

05440

(07)

04725

04725

(07) (14) (00)

(08)

05391

(15)

05391

(16)

05391

(11)

01011

(18)

01710

(08)

05391

08099

(12) (23) (24)

(08)

05440

(16)

05400

(00)

05400

(12)

04712

(20)

08000

(08)

05400

15200

(24) (08) (00)

(08)

05400

(17)

05440

(15)

05440

(15)

03690

(20)

03626

(08)

05440

00685

(01) (02) (10)

(12)

08075

(20)

08000

(00)

08000

(15)

05440

(21)

00532

(12)

08000

01649

(02) (15) (24)

(12)

08000

(23)

08075

(00)

08075

(16)

05391

(22)

03685

(12)

08075

00532

(00) (21) (07)

(12)

08099

(23)

08099

(24)

08099

(21)

00696

(22)

03690

(12)

08099

04651

(07) (11) (01)

(24)

15205

(06)

15150

(00)

15150

(24)

00624

(23)

08075

(24)

15150

05400

(08) (16) (00)

(24)

15150

(08)

15205

(00)

15200

(24)

08099

(23)

08099

(24)

15200

03626

(05) (20) (01)

(24)

15200

(08)

15200

(05)

15205

(24)

01649

(24)

00624

(24)

15205

Практическая реализация автоматизированного составления таблиц многоэтапного сортировки ПК сводится к созданию базы данных, содержащей записи о всех ПИ, каждая из которых включает три поля:

- Поле ПИ в десятичной системе счисления, которое является идентификатором записи;

- Поле номера ОПЗ в десятичной системе счисления, соответствующее полю ПИ (если ПИ не используется - в поле номера ОПЗ заносится 0);

- Поле номера ОПЗ в системе счисления с основанием я (я - количество накопителей АЛСМ), ПИК которого наносится на лист (ПИК 0 соответствует номеру справочного накопителя АЛСМ, предназначенного для передачи направленных к нему писем на ручную сортировку).

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

Поделиться материалом

Содержание