Практичне заняття 1. Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда (стр. 8 )

qs>=n, s= [logqn]

де [logqn] – значення logqn, округлене до найближчого більшого цілого

Оскільки при q >= п задача маршрутного сортування тривіальна, розглянемо реальний випадок q< п.

В цьому випадку для виконання маршрутного сортування необхідно скласти сортувальні таблиці, що визначають номери накопичувачів, в які повинні направлятися поштові відправлення, адресовані за певними напрямами, на кожному з етапів сортування.

Наведений нижче алгоритм складання сортувальних таблиць заснований на поданні напрямів сортування у вигляді чисел, записаних у позиційній системі числення з основою q

В такій системі числення ціле число N дорівнює

N = ns-1qs-1+ ns-2qs-2+…+ n0q0

і записується у вигляді s - розрядного числа

N= ns-1 ns-2… n0

де ns-1, ns-2,…,n0 - цифри числа N, що можуть приймати значення 0, 1, ...,q-1

Наприклад, десяткове число 1310 у двійковій, трийковій та четвірковій системах числення набуває виду:

1310 = 1*23 + 1*22 + 0*21 + 1*2° = 11012,

1310=1*32+1*31 + 1*30 =111з,

1310 = 3*41 + 1*4° =314.

Позначимо q накопичувачів, що використовуються для маршрутного сортування, як A0,A1, ..., Аq-1

Тоді алгоритм складання сортувальних таблиць полягає у наступному: на першому етапі сортування поштові відправлення направ­ляються в накопичувачі, .номери яких збігаються зі значеннями перших (молодших) цифр напрямів сортування; на другому етапі - зі значеннями других цифр і т. д.; на останньому етапі - зі значеннями останніх (старших) цифр.

Так, поштове відправлення за згаданим напрямом 13 буде направля­тися:

- при використанні двох накопичувачів Ао, A1 — на першому, тре­тьому і четвертому етапах сортування в накопичувач A1, а на другому етапі – в накопичувач А0,

- при використанні трьох накопичувачів Ао, А1, Аг - на всіх трьох етапах сортування в накопичувач А1,

- при використанні чотирьох накопичувачів Ао, А1, А2, A3 - на першому етапі сортування в накопичувач A1, а на другому етапі - в накопичувач А3;

- при використанні десяти накопичувачів Ао, А1 ...,А9 – на першому етапі сортування в накопичувач А3, а на другому етапі — в накопичувач
А1

Нижче наведені приклади побудови сортувальних таблиць: табл. 1 при q=2, s = 4, п = 16; табл. 2 - при q = 3, s= 3, п = 27; табл. З - при q = 4, s= 2,

п = 16; табл. 4 - при q= 10, 5, s= 2, п = 100. Для зручності порівняння напрями сортування у табл. 1, 2, 3 крім десяткової подані відповідно в двійковій, трийковій і четвірковій системах числення. Цифри, за якими здійснюється упорядкування в двійковій, трийковій, четвірковій і десятко­вій системах числення, а також напрями 13 в десятковій системі числення підкреслені.

Таблиця 1

Етап сортування	Накопичувач	Номери напрямів сортування
Двійкова система числення	Десяткова система числення
1	А0 А1	0000,0010,0100,0110,1000,1010,1100,1110 0001,0011,0101,0111,1001,1011,1101,1111	00,02,04,06,08,10,12,14 01,03,05,07,09,11,13,15
2	А0 А1	0000,0001,0100,0101,1000,1001,1100,1101 0010,0011,0110,0111,1010,1011,1110,1111	00,01,04,05,08,09,12,13 02,03,06,07,10,11,14,15
3	А0 А1	0000,0001,0010,0011,1000,1001,1010,1,0101,0110,0111,1100,1101,1110,1111	00,01,02,03,08,09,10,11 04,05,06,07,12,13,14,15
4	Ао Аі	0000,0001,0010,0011,0100,0101,0110,0,1001,1010,1011,1100,1101,1110,1111	00,01,02,03,04,05,06,0708,09,10,11,12,13 14,15

Таблиця 2

Етап сорту вання	Накопич увач	Номери напрямів сортування
Трійкова система числення	Десяткова система числення
1	А0 А1 А2	000,010,020,100,110,120,200,210,,011,021,,121,201,211,,012,022,102,112,122,202,212,222	00,03,06,09,12,15,18,21,24 01,04,07,10,13,16,19,22,25 02,05,08,11,14,17,20,23,26
2	А0 А1 А2	000,001,002,100,101,102,200, 201,,011,012,110,111,112,210,211,021,022,120,121,122,220, 221,222	00,01,02,09,10,11,18,19,20 03,04,05,12,13,14,21,22,23 06,07,08,15,16,17,24,25,26
3	А0 А1 А2	000,001,002,010,011,012,020,021,022 100,101,102,110,111,112,120,121,,201,202,210,211,212,220,221,222	00,01,02,03,04,05,06,07,08 09,10,11,12,13,14,15,16,17 18,19,20,21,22,23,24,25,26

Таблиця З

Етап сорту вання	Накопич увач	Номери напрямів сортування
Четвіркова система числення	Десяткова система числення
1	А0 А1 А2 А3	00,10,20,30 01,11,21,31 02,12,22,32 03,13,23,33	00,04,08,12 01,05,09,13 02,06,10,14 03,07,11,15
2	Ао А1 А2 А3	00,01,02,03 10,11,12,13 20,21,22,23 30,31,32,33	00,01,02,03 04,05,06,07 08,09,10,11 12,13,14,15

Таблиця 4

Етап сорту вання	На- копич увач	Номери напрямів сортування
Десяткова система числення
1		00,10,20,30,40,50,60,70,80,90
	А1	01,11,21,31,41,51,61,71,81,91
	А2	02,12,22,32,42,52,62,72,82,92
	А3	03,13,23,33,43,51,63,73,83,93
	А4	04,14,24,34,44,54,64,74,84,94
	А5	05,15,25,35,45,55,65,75,85,95
	А6	06,16,26,36,46,56,66,76,86,96
	А7	07,17,27,37,47,57,67,77,87,97
	А8	08,18,28,38,48,58,68,78,88,98
	А9	09,19,29,39,49,59,69,79,89,99
2	А0	00,01,02,03,04,05,06,07,08,09
	А1	10,11,12,13,14,15,16,17,18,19
	А2	20,21,22,23,24,25,26,27,28,29
	А3	30,31,32,33,34,35,36,37,38,39
	А4	40,41,42,43,44,45,46,47,48,49
	А5	50,51,52,53,54,55,56,57,58,59
	А6	60,61,62,63,64,65,66,67,68,69
	А7	70,71,72,73,74,75,76,77,78,79
	А8	80,81,82,83,84,85,86,87,88,89
	А9	90,91,92,93,94,95,96,97,98,99

У табл. 5 поданий приклад маршрутного сортування наведеної раніше послідовності напрямів сортування поштових відправлень при використанні чотирьох накопичувачів Ао, А1, Аг Аз за два етапи (використовується сортувальна таблиця, наведена в табл. 3).