Зміст
Введення
Глава 1. Представлення даних у цифрових
автоматах (ЦА)
1.1 Представлення чисел у позиційних системах числення (ПСС)
1.2 Форми представлення даних в ЦА
1.3 Виконання арифметичних операцій з цілими числами, представленими в машинних кодах
1.4 Виконання логічних операцій з цілими числами, представленими в машинних кодах
Глава 2. Методи контролю
роботи ЦА
2.1. Коригуюча здатність кодів
2.2 Метод парності / непарності. Коди Хемінг
2.3
Контроль за модулем
Глава 3. Побудова алгоритму реалізації чисельного методу «швидкої сортування»
3.1
Математичне опис методу
3.2 Таблиця використовуваних змінних
Список використаних джерел
Додаток 1. Блок-схема алгоритму
Введення У своїй роботі я ставлю такі завдання:
- Навчитися представляти дані у ЦА;
- Вивчити методи контролю роботи ЦА і навчитися будувати код Хеммінга;
- Вивчити реалізацію алгоритму чисельного методу «швидкого сортування» і побудувати його блок-схему.
Глава 1. Представлення даних у цифрових автоматах (ЦА) 1.3 Представлення чисел у позиційних системах числення (ПСС) Система числення - це сукупність
символів і правил їх запису, необхідних для запису чисел.
У позиційній системі числення вага
символу залежить від позиції в якій розташований
символ. Наприклад, число 222 - перший символ цього числа має вагу 200, другий - 20, третій - 2.
Основною характеристикою ПСС є підстава.
Підстава ПСС - це кількість символів даної системи числення, які використовуються при складанні чисел. Залежно від
підстави ПСС існує чотири основні системи числення: двійкова, вісімкова, десятеричная і шістнадцяткова. Всі ці системи числення використовуються в ЦА і кожна має свої основні функції. Наприклад, числа, записані в двійковій системі числення, використовуються в ЦА для операцій вироблених
процесором: запис, зчитування, складання і т.д.; числа в шістнадцятковій системі числення - для адресації комірок пам'яті.
Переклад чисел з однієї ПСС в іншу При
перекладі чисел
з десяткової системи числення в систему з основою
P зазвичай використовують наступний алгоритм:
1) якщо переводиться ціла частина числа, то вона ділиться на
P, після чого запам'ятовується залишок від ділення. Отримане приватне знову ділиться на
P, залишок запам'ятовується. Процедура триває до тих пір, поки приватне не стане рівним нулю. Залишки від ділення на
P виписуються в порядку, зворотному їх отримання;
2) якщо переводиться дробова частина числа, то вона множиться на
P, після чого ціла частина запам'ятовується і відкидається. Знову отримана дробова частина множиться на
P і т.д. Процедура триває до тих пір, поки дробова частина не стане рівною нулю. Цілі частини виписуються після двійковій комою в порядку їх отримання. Результатом може бути або кінцева, або періодична двійкова дріб. Тому, коли дріб є періодичною, доводиться обривати множення на будь-якому кроці і задовольнятися наближеною записом вихідного числа в системі з основою
P. Переклад числа з системи числення з основою
P1 в систему числення з основою
P2, можна виконати за таким же алгоритмом, але все обчислення потрібно проводити в системі числення з основою
P1. Другий спосіб перевести число можна в два етапи: перевівши це число в десяткову систему числення, а потім з десяткової до системи числення з основою
P2. Щоб перевести число з системи числення з основою
P в десяткову систему числення, потрібно знайти суму творів вмісту розряду на вагу цього розряду в системі числення з основою
P. Де розряд - номер позиції в числі, нумеруються справа наліво, починаючи з нуля; вага розряду - число,
рівне основи системи числення певною мірою номери розряду.
Щоб перевести число
з двійкової системи числення
у вісімкову (шістнадцяткову) систему числення, потрібно розбити число на трійки (четвірки) цифр, у разі необхідності слід доповнити цілу і дробову частини числа нулями (цілу ліворуч, дробову праворуч). Потім замінити отримані групи цифр
відповідними їм вісімковими (шестнадцатерічнимі) цифрами. Наприклад, число 11010010.10
2 треба перевести у вісімкову систему числення. Розіб'ємо число на трійки цифр: 011 010 010. 100, замінимо трійки цифр на відповідними їм вісімковими цифрами. Отримаємо 11010010.10
2 = 322.4
8 Щоб перевести число
з вісімковій (шістнадцятковій) системи числення в двійкову систему числення, потрібно замінити кожну цифру числа відповідними їм трійками (четвірками) двійкових цифр.
Завдання. Здійснити
переклад числа (А + В), представленого в 10-ій системі з однієї системи числення в інші, за схемою малюнка.
(А + В)
10 Рішення. А + В = 307 +6.6 = 313.6
10 313.6 10 = () 2 Спочатку переводимо цілу частину числа, ділимо на підставу 2:
313 / 2 = 156 залишок - 1;
156 / 2 = 78 залишок - 0;
78 / 2 = 39 залишок - 0;
39 / 2 = 19 залишок - 1;
19 / 2 = 8 залишок - 1;
9 / 2 = 4 залишок - 1;
4 / 2 = 4 залишок - 0;
2 / 2 = 1 залишок - 0;
Далі ділити не можна, тому збираємо всі залишки, починаючи з кінця і враховуємо кінцевий результат від ділення тобто 2 / 2 = 1. Отримаємо 313
10 = 100111001
2 Тепер переводимо дробову частину числа, множимо на підставу 2:
*
| 6
| | *
| 2
| | *
| 4
| | *
| 8
| |
2
| | 2
| | 2
| | 2
| |
1
| 2
| | 0
| 4
| | 0
| 8
| | 1
| 6
| |
Отримаємо 0.6
10 = 0.1001
2, значить,
313
10 »100111001.1001
2 100111001.1001 2 = () 8 Розіб'ємо число на трійки цифр: 100 111 001. 100 100, замінимо трійки цифр на відповідними їм вісімковими цифрами тобто 100
2 = 4
8; 111
2 = 7
8; 001
2 = 1
8. Отримаємо 100111001.1001
2 = 471.44
8 100111001.1001 2 = () 10 1
| 0
| 0
| 1
| 1
| 1
| 0
| 0
| 1
| .
| 1
| 0
| 0
| 1
| Число
|
8
| 7
| 6
| 5
| 4
| 3
| 2
| 1
| 0
| | -1
| -2
| -3
| -4
| Розряди числа
|
100111001.1001
2 = 1 * 2
-4 + 1 * 2
-1 + 1 * 2
0 + 1 * 2
3 + 1 * 2
4 + 1 * 2
5 + 1 * 2
8 =
= 0.0652 + 0.5 + 1 + 8 + 16 + 32 + 256 = 313.5652
10 »313.6
1910 100111001.1001 2 = () 16 Розіб'ємо число на четвірки цифр:
0001 0011 1001. 1001, замінимо четвірки цифр на відповідними їм шестнадцатерічнимі цифрами тобто 0001
2 = 1
16; 0011
2 = 3
16; 1001
2 = 9
16. Отримаємо 100111001.1001
2 = 139.9
16 313.6 10 = () 8 Спочатку переводимо цілу частину числа, ділимо на підставу 8:
313 / 8 = 39 залишок - 1;
39 / 8 = 4 залишок - 7.
Отримаємо 313
10 = 471
8 Тепер переводимо дробову частину числа, множимо на підставу 8:
*
| 6
| | *
| 8
| | *
| 4
| | *
| 2
| |
8
| | 8
| | 8
| | 8
| |
4
| 8
| | 6
| 4
| | 3
| 2
| | 1
| 6
| |
Отримаємо 0.6
10 = 0.4631
8, значить,
313
10 »471.4631
8 471.4631 8 = () 2 Кожен символ числа 471.4631
8 запишемо у двійковій системі числення: 4
8 = 100
2, 7
8 = 111
2, 1
8 = 001
2, 6
8 = 110
2, 3
8 = 011
2. Отримаємо 471.4631
8 = 100111001.100110011001
2 471.4631 8 = () 10 4
| 7
| 1
| .
| 4
| 6
| 3
| 1
| Число
|
2
| 1
| 0
| | -1
| -2
| -3
| -4
| Розряди числа
|
471.4631
8 = 1 * 8
-4 + 3 * 8
-3 + 6 * 8
-2 + 4 * 8
-1 + 1 * 8
0 + 7 * 8
1 + 4 * 8
2 =
= 0.0002 + 0.0058 + 0.0937 + 0.5 + 1 + 56 + 256 = 313.5997
10 »313.6
10 471.4631 8 = () 16 Переклад числа з вісімковій системи числення в шістнадцяткову проведемо у два етапи: спочатку переведемо число в десяткову систему числення, потім з десятеричной в шістнадцяткову.
Переклад числа 471.4631
8 у десяткову систему числення вже здійснено вище: 471.4631
8 = 313.6
10. Далі переведемо 313.6
10 в шістнадцяткову систему числення:
313.6 10 = () 16 Спочатку переводимо цілу частину числа, ділимо на підставу 16:
313/16 = 19 залишок - 9;
19/16 = 1 залишок - 3.
Отримаємо 313
10 = 139
16 Тепер переводимо дробову частину числа, множимо на підставу 16:
Отримаємо 0.6
10 = 0.99
16, значить,
313
10 »139.99
16 139.99 16 = () 2 Кожен символ числа 139.99
1916 запишемо у двійковій системі числення: 1
16 = 0001
2, 3
16 = 0011
2, 9
16 = 1 001
2. Отримаємо 139.99
16 = 100111001.10011001
2 139.99 16 = () 8 Переклад числа з шістнадцятковій системи числення у вісімкову будемо виконувати в один етап, роблячи все обчислення в шістнадцятковій системі числення.
Спочатку переводимо цілу частину числа, ділимо на підставу 8:
Далі ділити не можна, тому збираємо всі залишки, починаючи з кінця і враховуємо кінцевий результат від ділення тобто 20 / 8 = 4. Отримаємо 139
16 = 471
8 Тепер переводимо дробову частину числа, множимо на підставу 8:
*
| 99
| | *
| С8
| | *
| 40
| |
8
| | 8
| | 8
| |
4
| С8
| | 6
| 40
| | 2
| 00
| |
Отримаємо 0.99
16 = 0.4620
8, значить,
139.99
16 »471.4620
8 139.99 16 = () 10 A
| | -A
| |
0 | 000000100110011
| | 1 | 111111011001101
| Число
|
0 | 000001001100110
| | 1 | 111110110011010
| Результат зсуву вліво
|
C
| | -C
| |
0 | 000000001011011
| | 1 | 111111110100101
| Число
|
0 | 000000000101101
| | 0 | 111111111010010
| Результат зсуву вправо
|
д) провести логічний циклічний зсув: вліво для чисел А і-А, вправо для чисел С і-С
A
| | -A
| |
0 | 000000100110011
| | 1 | 111111011001101
| Число
|
0 | 000010011001100
| | 1 | 111101100110100
| Результат зсуву вліво на 2 біти
|
C
| | -C
| |
0 | 000000001011011
| | 1 | 111111110100101
| Число
|
0 | 000000000010110
| | 0 | 011111111101001
| Результат зсуву вправо на 2 біти
|
e) провести арифметичний зсув: вліво для чисел А і-А, вправо для чисел С і-С
A
| | -A
| |
0 | 000000100110011
| | 1 | 111111011001101
| Число
|
0 | 000001001100110
| | 1 | 111110110011010
| Результат зсуву вліво
|
C
| | -C
| |
0 | 000000001011011
| | 1 | 111111110100101
| Число
|
0 | 000000000101101
| | 1 | 011111111010010
| Результат зсуву вправо
|
Глава 2. Методи контролю роботи ЦА 2.1 Коригувальна здатність кодів При роботі ЦА можуть відбутися ті або інші збої, що призводять до спотворення інформації. Тому при проектуванні ЦА повинні передбачатися кошти, що дозволяють контролювати, виявляти і виправляти виникаючі помилки. Вирішення всіх завдань контролю стає можливим тільки при наявності певної надмірності інформації, яка супроводжує основну інформацію. Інакше кажучи, при представленні числа в будь-якому коді, необхідно предусмотретьв цьому коді додаткові (
контрольні) розряди.
Систематичний код - це код, який містить в собі
інформаційні та
контрольні розряди. До
контрольних розряди записується деяка
інформація про вихідний числі, тому систематичний код має надмірністю.
При цьому абсолютна надмірність буде виражатися кількістю контрольних розрядів -
k, а відносна надмірність -
, Де
m - кількість
інформаційних розрядів.
Поняття корегуючої здатності коду пов'язують з можливістю виявлення та виправлення помилки. Кількісно коригуюча здатність коду визначається імовірністю виявлення або виправлення помилки. Коригуюча здатність коду пов'язана
поняттям кодового відстані.
Кодова відстань (Хемінгово відстань) d для кодових комбінацій A і B визначається як вага такої третьої комбінації, яка виходить складанням початкових комбінацій за модулем 2. Вага кодової комбінації V - це кількість одиниць містяться в кодової комбінації.
Наприклад, A = 100111001 і B = 011011100. Звідси ваги кодових комбінацій будуть рівні: V (A) = 5, V (B) = 5. Кодова комбінація C = A + B = 111100101, вага цієї кодової комбінації дорівнює V (C) = 6. Таким чином кодова відстань для A і B - d (A, B) = V (C) = 6.
У будь-якій позиційній системі числення мінімальне кодова відстань дорівнює 1. У теорії
кодування показано, що систематичний код має здатність виявлення помилки лише тоді, коли код відстані для нього більше або дорівнює 2t. Отже,
, Де t - кратність виявлених помилок. Це означає, що між сусідніми кодовими комбінаціями повинна існувати, принаймні одна кодова комбінація.
2.2 Метод парності / непарності. Коди Хемінг Якщо в математичному коді виділений один
контрольний розряд, то до кожного бінарного числа додається один надлишковий розряд. До цього розряду записується 1 або 0 з такою умовою, щоб сума цифр за модулем 2 була дорівнює 0 для випадку парності або 1 для випадку непарності. Поява помилки в кодуванні обнружівается з порушення парності / непарності. При такому кодуванні допускається, що може виникнути тільки одна помилка.
Приклад реалізації методу парності:
Число
| Контрольний розряд
| Перевірка
|
10101011
| 1
| 0
|
11001010
| 0
| 0
|
10010001
| 1
| 0
|
11001011
| 0
| 1 - помилка
|
Можна уявити і дещо видозмінений спосіб контролю за методом парності / непарності. Довге
слово розбивається на групи, кожна з яких містить
n розрядів.
Контрольні розряди -
k, виділяються всім групам по рядках і стовпцях згідно з наступною схемою:
Збільшення надмірності призводить до
того, що з'являється можливість не тільки виявити помилку, але і виправити її.
Наприклад: число 1000111011010101110010101 представимо за згаданою вище схемою, отримаємо:
1
| 0
| 0
| 0
| 1
| 0
|
| 1
| 0
| 1
| 1
| 0
|
0
| 1
| 0
| 1
| 0
| 0
|
1
| 1
| 1
| 0
| 0
| 1
|
1
| 0
| 1
| 0
| 1
| 1
|
0
| 1
| 0
| 0
| 1
| |
Тепер, якщо при передачі було отримано число:
1
| 0
| 0
| 0
| 1
| 0
|
1
| 1
| 0
| 1
| 1
| 0
|
0
| 1
| 0
| 0
| 0
| 0
|
1
| 1
| 1
| 0
| 0
| 1
|
1
| 0
| 1
| 0
| 1
| 1
|
0
| 1
| 0
| 0
| 1
| |
Тоді перевірка показує, що помилка виникла в інформації третього рядка і четвертого стовпця. Отже, розряд, що містить помилкову інформацію, знаходиться на перетині третього рядка і четвертого стовпця. Помилку можна усунути змінивши 0 на 1.
Код Хеммінга - біочний систематичний код, тобто складається з інформаційних та коригувальних символів, рассположенних за строго визначеною системою, що мають однакову довжину і завжди займають строго визначені місця в кодових комбінаціях.
При передачі коду може бути спотворений або не спотворений будь-який символ. Якщо довжина коду -
n символів, то
- Повна кількість комбінацій коду. За методикою Хеммінга можна визначити число інформаційних символів коду, що виявляє і коригуючого одиночну помилку наступним чином:
, Де
- Число інформаційних символів в коді;
- Число контрольних символів;
- Довжина коду Хеммінга.
Співвідношення
n, і
для коду Хеммінга можна представити у вигляді таблиці:
Таблиця 2.2.a
n
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
| 13
| 14
| 15
| 16
|
| 0
| 0
| 1
| 1
| 2
| 3
| 4
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 11
|
| 1
| 2
| 2
| 3
| 3
| 3
| 3
| 4
| 4
| 4
| 4
| 4
| 4
| 4
| 4
| 5
|
Нехай необхідно передати число 11
10 = 1011
2. Значить
. Використовуючи таблицю 2.2.a отримуємо:
,
.
Далі необхідно визначити на якій позиції повинні знаходитися контрольні коефіцієнти. Позиція контрольних коефіцієнтів -
k в коді обчислюється за формулою -
, Де
i - порядковий номер коефіцієнта
k. Отримуємо 7-розрядний код:
Таблиця 2.2.c
1
| 2
| 3
| 4
| 5
| 6
| 7
| Розряди коду Хеммінга
|
k1
| k2
| И4
| k3
| И3
| И2
| І1
| Призначення розрядів
|
| | 1
| | 0
| 1
| 1
| Значення розряду
|
Де k
i -
контрольний коефіцієнт (відлік йде зліва на
право); І
i -
інформаційний символ (відлік йде справа на ліво).
Значення контрольних коефіцієнтів за правилом: якщо сума одиниць на перевірочних позиціях парна, то значення
контрольного коефіцієнта дорівнює 0, у противному випадку - 1.
Таблиця 2.2.d
Позиція контрольного коефіцієнта
| Перевірочні позиції
|
1
| 1, 3, 5, 7, 9, 11, 13 ...
|
2
| 2, 3, 6, 7, 10, 11, 14 ...
|
4
| 4, 5, 6, 7, 12, 13, 14 ...
|
8
| 8, 9, 10, 11, 12, 13, 14 ...
|
Отже, використовуючи таблицю 2.2.d назодім значення контрольних коефіцієнтів k
i: k
1 = 1 + 0 + 1 = 0;
k
2 = 1 + 1 + 1 = 1;
k
3 = 0 + 1 +1 = 0.
Отримаємо код Хеммінга 0110011 для передачі числа 11
10. Тепер розглянемо приклад коригування отриманого кодованого в коді Хеммінга числа, в якому є збій. Отримали число 0110001. Для виправлення помилки необхідно визначити позицію, в якій стався збій. Для цього визначаємо значення контрольних коефіцієнтів, використовуючи таблицю 2.2.d:
k
1 = 0 + 1 + 0 + 1 = 0 - немає помилки;
k
2 = 1 + 1 + 0 + 1 = 1 - помилка;
k
3 = 0 + 0 +0 +1 = 1 - помилка.
Номер помилкового розряду співпадає з сумою позицій контрольних коефіцієнтів, що вказали на наявність помилки тобто 2 + 4 = 6. Для виправлення помилки досить інвертувати значення 6-го розряду.
Завдання. Побудувати код Хеммінга для числа А.
A = 307
10 = 100 110 011
2 Використовуючи таблицю 2.2.a отримуємо:
,
.
1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
| 13
| Розряди коду Хеммінга
|
k1
| k2
| И9
| k3
| І8
| И7
| І6
| k4
| И5
| И4
| И3
| И2
| І1
| Призначення розрядів
|
| | 1
| | 0
| 0
| 1
| | 1
| 0
| 0
| 1
| 1
| Значення розряду
|
k
1 = 1 + 0 + 1 + 1 + 0 + 1 = 0;
k
2 = 1 + 0 + 1 + 0 + 0 = 0;
k
3 = 0 + 0 +1 + 1 + 1 = 1;
k
4 = 1 + 0 + 0 + 1 + 1 = 1.
Отримаємо код Хеммінга 0011001110011.
При передачі, отримали код з помилкою 0011001110111. Перевіряємо:
k
1 = 0 + 1 + 0 + 1 + 1 + 1 + 1 = 1; - помилка;
k
2 = 0 + 1 + 0 + 1 + 0 + 1 = 1; - помилка;
k
3 = 1 + 0 + 0 +1 + 1 + 1 = 0; - немає помилки;
k
4 = 1 + 1 + 0 + 1 + 1 + 1 = 1 - помилка.
Помилка знаходиться в розряді 1 + 2 + 8 = 11, інвертуємо 11-й розряд і отримуємо вихідний код Хеммінга.
2.3 Контроль за модулем Контроль виконання арифметичних і логічних операцій можна здійснювати за допомогою контрольних кодів, що представляють собою залишки від ділення чисел на деякий модуль.
Такий контроль називають
контролем за модулем. Для двійкових чисел цей модуль зазвичай равер або більше 3. Розрізняють числової і цифровий контроль по модулю.
При числовому методі код заданого числа визначається як найменший позитивний залишок від ділення числа на обраний модуль. Наприклад, визначити контрольний код числа 160 по модулю 6. Для цього ділимо 160 на 6, отримуємо залишок - 4.
При цифровому методі контролю, контрольний код числа утворюється діленням суми цифр числа на обраний модуль. Наприклад, визначити контрольний код числа 160 по модулю 6. Сума цифр числа 160 дорівнює 7, ділимо її на 6. Отримаємо залишок 1, значить це, контроль числа 160 по модулю 6, при цифровому методі контролю.
Числовий метод контролю Арифметичні операції можна уявити у вигляді
послідовності наступних елементарних операцій: передача слова, зсув, взяття зворотного коду, складання.
Операцію зсуву можна представити як передачу слова з i-го розряду в (i + x) розряд. Тому, контроль зсуву можна здійснити за методом парності / непарності.
Контроль виконання арифметичних операцій: додавання, віднімання, множення можна здійснити методом контролю за модулем. Для цього застосовують формули:
K
A = A mod P K
B = B mod P
K
A + B = (A + B) mod P = (K
A + K
B) mod P
K
A * B = (A * B) mod P = (K
A * K
B) mod P
Наприклад, знайдемо контрольний код чисел A, B і контрольний код арифметичних операцій над ними, отримаємо:
A
| B
| A + B
| A - B
| A * B
| Арифметичні операції над числами
|
89
| 57
| 146
| 33
| 5073
| Значення чисел
|
8
| 3
| 2
| 6
| 6
| Контроль за модулем 9
|
Перевірка виконаних операцій:
- Помилка, значить ця операція виконана неправильно;
|
|
K
A + B = (8 + 3) mod 9 = 2 - немає помилки;
K
A - B = (8 - 3) mod 9 = 5
K
A * B = (8 * 3) mod 9 = 6 - немає помилки.
Завдання. Визначити контрольні коди чисел A і C за модулем P, а також контрольні коди суми A + C і різниці A - C.
До
А = 307 mod 9 = 1;
K
C = 91 mod 9 = 1;
K
A + C = (307 +91) mod 9 = 398 mod 9 = 2; перевірка:
K
A + C = (1 + 1) mod 9 = 2 mod 9 = 2 - немає помилки.
K
A - C = (307-91) mod 9 = 216 mod 9 = 0; перевірка:
K
A - C = (1 - 1) mod 9 = 0 mod 9 = 0 - немає помилки.
Цифровий метод контролю Контроль виконання арифметичних операцій: додавання, віднімання, множення виконується за темже формулами, тільки при цифровому методі контролю, контрольний код числа утворюється діленням суми цифр числа на обраний модуль.
Завдання. Визначити контрольні коди чисел A і C за модулем P, а також контрольні коди суми A + C і різниці A - C.
До
А = (3 +0 +7) mod 9 = 1;
K
C = (9 +1) mod 9 = 1;
K
A + C = (3 +0 +7 +9 +1) mod 9 = 20 mod 9 = 2; перевірка:
K
A + C = (1 + 1) mod 9 = 2 mod 9 = 2 - немає помилки.
K
A - C = (3 +0 +7-9-1) mod 9 = 0 mod 9 = 0; перевірка:
K
A - C = (1 - 1) mod 9 = 0 mod 9 = 0 - немає помилки.
Глава 3. Побудова алгоритму реалізації чисельного методу «швидкої сортування» 3.1 Математичне опис методу Алгоритм
сортування К. Хоорі називають
сортуванням з поділом або «швидкої сортуванням». В основу алгоритму покладено метод послідовного дроблення масиву на частини.
Алгоритм «швидкого сортування» можна проаналізувати на прикладі. Нехай дано
масив M [i] = (9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5). Після першого виклику процедури QuickS у вихідному масиві буде визначено його середина (10-й елемент) і змінної X присвоєно значення m [10], тобто 18. Після цього
масив ділиться на дві частини. Далі виконується
обмін елементами за наступним правилом:
При перегляді лівій частині масиву зліва направо виполниется пошук такого елемента масиву, що M [i]> X, потім при перегляді правій частині справа наліво відшукується
такий елемент, що M [i] <X. Виконується обмін місцями даних елементів, поки всі елементи ліворуч від середини, що задовольняють умові M [i]> X, не будуть обмінені з елементами, рассположеннимі праворуч від середини і задовольняють умові M [i] <X. У результаті цього отримаємо масив з двох частин такого вигляду:
9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5 Число ітерацій = 1
19, 20, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 11, 9, 2, 5 Число ітерацій = 2
19, 20, 20, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 3
19, 20, 20, 19, 19, 1, 5, 17, 10, 18, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 4
19, 20, 20, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 5
Далі ліва частина в свою чергу дробиться на дві частини, і викликається процедура для сортування лівої частини (з 1-го по 6-й елемент)
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 6
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 7
Після того як ліва частина масиву відсортована, знову рекурсивно викликається процедура, в якій визначається середина даної частини масиву, і виконується обмін елементів.
Масив стає таким:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 8
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 9
Далі знову рекурсивно викликається процедура для сортування, поки в кожній з частин залишиться по одному елементу.
Потім рекурсивно викликається процедура для аналогічної сортування правій частині (з 7-го по 13-й елемент). Результат послідовних етапів сортування масиву відображається так:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 10
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 11
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 12
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 3, 3, 5, 9, 12, 12, 11, 1, 2, 5 Число ітерацій = 13
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 3, 5, 9, 12, 12, 3, 1, 2, 5 Число ітерацій = 14
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 5, 9, 12, 3, 3, 1, 2, 5 Число ітерацій = 15
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 16
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 17
20, 20, 19, 19, 19, 18, 17, 17, 12, 9, 11, 12, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 18
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 19
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 20
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 21
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 22
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 23
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 24
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 25
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 3, 2, 1 Число ітерацій = 26
Як видно з прикладу, даний масив буде відсортований за 26 ітерацій методом «швидкої сортування». Той же масив відсортований лінійним методом, буде відсортований за 190 ітерацій,
бульбашковим методом за 170 ітерацій.
Як видно з наведених прикладів, алгоритм «швидкого сортування» дає кращі результати.
3.2 Таблиця використовуваних змінних Ім'я змінної
| Тип змінної
| Опис змінної
|
M [i]
| Цілий / Речовий
| Сортований масив чисел
|
i j
| Цілий
| Використовуються в циклі при зверненні до елементу масиву
|
X
| Цілий / Речовий
| Значення елемента в середині масиву
|
First Last
| Цілий
| Межі сортованого масиву
|
tmp
| Цілий / Речовий
| Тимчасове зберігання значення елемента масиву при обміні
|
Примітка: так як процедура сортування масиву -
рекурсія, то
змінні i, j, X - повинні бути локальними.
Висновок У
процесі виконання курсової роботи, я дізнався як представляються дані в ЦА, навчився переводити числа з однієї системи числення в іншу, навчився представляти числа у машинному коді і виконувати над ними арифметичні та
логічні операції. При вивченні методу контролю роботи ЦА, я навчився будувати код Хеммінга, а також виявляти помилки в даних, закодованих кодом Хеммінга. При вивченні реалізації алгоритму чисельного методу «швидкої сортування», я побачив
перевагу даного методу у відмінності від інших методів сортування.
Таким чином, при виконанні курсової роботи, я отримав нові
знання та навички для своєї професійної діяльності.
Список використаних джерел 1. Пономарьов В.С., Красніков В.В.
Методичні вказівки з курсу «Організація і функціонування ЕОМ і систем». Ч.1. Арифметичні основи ЕОМ. ДДТУ, 1996.
2. Інтернет-ресурс «Системи числення: двійкова, вісімковий, шестнадцатірічное»
http://www.pascalstudy.narod.ru/tems/pas_5.html
3. Коштоев В.В., Кіпіані К.К. Навчальний посібник «Основи прикладної теорії цифрових автоматів» Тбілісі, 1998.
4. Інтернет-ресурс «Теоретичні основи інформатики. Коди Хеммінга »
http://de.uspu.ru/Informatics/Metodes/DPP/F/08/1/glavs/5/564.htm
5. Інтернет-ресурс «Контроль за модулем арифметичних операцій у десятковій і двійкової СС»
http://distance-onu.by.ru/metod/11.htm
6. Інтернет-ресурс «Глава 3. Вирази та Операції. Побітові операції зсуву »
http://pyramidin.narod.ru/jscript/coreguide15/expr.html
7.
Turbo Pascal для
школярів: Учеб. посібник .- 3-е доп.ізд .- М.:
Фінанси і
статистика, 2002.-528 с.
Додаток 1. Блок-схема алгоритму