C _Учебник_МОНУ

значення основи системи q. Ділення виконується, допоки наступна частка не буде меншою за основу q. Остача, обчислена на останньому кроці, є старшою (першою) цифрою переведеного числа. Результатом переведення такого числа до q-тої системи числення є запис останньої частки і всіх остач у зворотному порядку. Наприклад, переведення числа 133 з десяткової системи числення до вісімкової виконується у такий спосіб:

133 : 8 = 16 (5)

16 : 8 = 2 (0)

Результат: 13310 = 2058. Остачі від ділення записані в дужках після часток. Остання частка є старшою цифрою вісімкового числа, до якого дописуються решта остач у порядку, зворотному до порядку її обчислення.

Переведемо те саме число 133 до двійкової системи числення:

133 : 2 = 66 (1)

66 : 2 = 33 (0)

33 : 2 = 16 (1)

16 : 2 = 8 (0)

8 : 2 = 4 (0)

4 : 2 = 2 (0)

2 : 2 = 1 (0) Результат: 13310 = 100001012.

Переведення числа 133 до шістнадцяткової системи числення має вигляд: 133 : 16 = 8 (5)

Результат: 13310 = 8516.

Переведення десяткового дробу виконується послідовним множенням дробу і дробових частин результатів на основу системи q. Множення виконується аж до віднаходження нульової дробової частини або до обчислення числа із заданою точністю. Запис у прямому порядку всіх цілих частин добутку дає зображення даного дробу в q-тій системі числення.

Для прикладу переведемо десяткове число 0.125 почергово до двійкової, вісімкової та шістнадцяткової систем числення:

1)до двійкової:

0.125 2 = 0.25;

0.252 = 0.5;

0.5 2 = 1 Результат: 0.12510 = 0.0012;

2) до вісімкової:

0.125 8 = 1 Результат: 0.12510 = 0.18;

3) до шістнадцяткової:

0.125 16 = 2 Результат: 0.12510 = 0.216.

А тепер наведемо приклад переведення десяткового числа з цілою та дробовою частинами 122.6 до двійкової системи числення з точністю у шість значущих цифр дробової частини.

Результат: 122.610 = 1111010.1001102.

Отже, при переведенні цілої частини числа остачі, які залишаються у перебігу послідовного ділення часток, є цифрами цілої частини числа у новій системі числення. Остача, обчислена на останньому кроці, є старшою (першою) цифрою переведеного числа. А при переведенні дробової частини числа цілі частини чисел, які здобувають при множенні, не беруть участі у наступних множеннях. Вони є цифрами дробової частини результату. Значення першої цілої частини є першою цифрою після десяткової крапки переведеного числа тощо. Якщо при переведенні дробової частини виходить періодичний дріб, то здійснюють округлення, керуючись заданою точністю обчислень.

Для перевірки зробимо зворотне переведення здобутого двійкового числа 1111010.100110 до десяткової системи числення за допомогою поліному (див. п. 1.4.1). Невелику точність обчислень дробової частини у цьому прикладі зумовлено малою кількістю значущих цифр у попередньому перетворюванні.

1111010.1001102 =

=1 26 +1 25 +1 24 +1 23 +0 22 +1 21 +0 20 +1 2–1 +0 2–2 +0 2–3 +1 2–4 +1 2–5 +0 2–6 =

=64+32+16+8+2+0.5+0.0625+0.03125 = 122.59375 122.6

Переведення десяткових чисел до вісімкової системи числення здійснюється аналогічно. За приклад переведемо вищенаведене число 122.6 і до вісімкової системи числення:

Результат: 122.610 = 172.4631468.

Зворотне переведення з вісімкової системи числення до десяткової здобутого вище числа 172.4631468 має вигляд:

172.4631468 = 1 82+7 81+2 80+4 8–1+6 8–2+3 8–3+1 8–4+4 8–5 = = 64+56+2+0.5+0.09375+0.0058598+0.00024414+0.00003052

122.599884 122.6

0.6 16 = 9.6

0.6 16 = 9.6 Результат: 122.610 = 7А .999916.

Зворотне переведення з шістнадцяткової системи числення до десяткової здобутого числа 7А.999916 матиме вигляд:

7А.99916 = 7 161+10 160+9 16–1+9 16–2+9 16–3 +9 16–4 = = 112+10+0.5625+0.03515325+0.0021972656+0.000137329= =122.599987845 122.6

Переведення вісімкового числа до двійкової системи числення й навпаки здійснюються за допомогою табл. 1.2. Для цього треба виписати відповідні двійкові тріади усіх вісімкових цифр числа, розпочинаючи зі старшого розряду, наприклад:

2378 = 10 011 1112

5048 = 101 000 1002

145.268 = 001100101.010110 = 1100101.010112

Початкові й кінцеві незначущі нулі можна вилучити.

Для переведення двійкового числа до вісімкової системи числення треба виокремити тріади бітів спочатку цілої частини справа наліво, а потім – дробової частини зліва направо, доповнюючи їх, за потреби, незначущими нулями. Потім кожну тріаду слід замінити на відповідну вісімкову цифру, наприклад:

110001002 = 11 000 100 = 3048

1011.111012 = 001 011.111 010 = 13.728

Алгоритм переведення із вісімкової системи числення до двійкової є зворотнім попередньому:

3048 = 11 000 1002

401.048 = 100 000 001.000 12

Переведення шістнадцяткових чисел до двійкової системи числення й навпаки здійснюється за допомогою тетрад (від грецької – чотири), тобто кожен шістнадцятковий розряд подається чотирма двійковими. Правила переведення є аналогічні до правил для вісімкової системи числення, наприклад:

1AF816 = 1 1010 1111 10002 14.2816 = 1 1010.0010 10112

11001000010112 = 1 1001 0000 1011 = 190В16 1011010.010112 = 101 1010.0101 1000 = 5А.5816

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

лі степені числа 2: 23 = 8, 24 = 16. Найбільш застосовувана шістнадцяткова система числення широко використовується програмістами, оскільки подавання чисел у цій системі є більш компактним, аніж у двійковій чи вісімковій, і переведення з цієї системи до двійкової та навпаки виконується доволі просто.

Наведемо приклади усіх можливих перетворювань до наведених систем числення для десяткового цілого числа 263:

1)з десяткової до двійкової:

263 : 2 = 131 (1)

131 : 2 = 65 (1)

65 : 2 = 32 (1)

32 : 2 = 16 (0)

16 : 2 = 8 (0)

8 : 2 = 4 (0)

4 : 2 = 2 (0)

2 : 2 = 1 (0)

Результат: 26310 = 1000001112;

2) з двійкової до десяткової:

1000001112 = 1 28 +1 22 +1 21 +1 20 = 256 + 4 + 2 + 1 = 26310 Результат: 1000001112 = 26310;

3) з десяткової до вісімкової:

263 : 8 = 32 (7)

32 : 8 = 4 (0)

Результат: 26310 = 4078; 4) з вісімкової до десяткової:

4078 = 4 82 +7 80 = 256 + 7 = 26310

Результат: 4078 = 26310; 5) з десяткової до шістнадцяткової:

263 : 16 = 16 (7)

16 : 16 = 1 (0)

Результат: 26310 = 10716; 6) з шістнадцяткової до десяткової:

10716 = 1 162 +7 160 = 256 + 7 = 26310

Результат: 10716 = 26310;

7)з шістнадцяткової до двійкової:

Результат: 10716 = 1 0000 01112;

8)з двійкової до шістнадцяткової:

Результат: 1000001112 = 0001 0000 0111 = 10716;

9) з вісімкової до двійкової:

Результат: 4078 = 100 000 111 = 1000001112;

10) з двійкової до вісімкової:

Результат: 1000001112 = 100 000 111 = 4078.

1.4.5 Арифметичні операції в різних системах числення

Основними арифметичними операціями над числовими даними в будьякій системі є додавання, віднімання, множення й ділення. Правила виконування цих операцій в різних системах числення є аналогічними до загальновідомих і застосовуваних у десятковій системі. Відмінністю є лише те, що за потреби перенесення до наступного розряду при додаванні чи позичанні зі старшого розряду при відніманні виступає відповідна основа системи числення: для двійкової – 2, для вісімкової – 8, для шістнадцяткової – 16.

Приклади на додавання (крапками над числами позначають перенесення

1.5 Етапи розв’язування обчислювальних задач на комп’ютері

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

1)постановка задачі – окреслення вимог щодо програми (приміром, визначення початкових даних, їхнього формату, параметрів введення). Результатом цього етапу розробляння є докладний словесний чи математичний опис алгоритму;

2)побудова математичної моделі задачі – опис задачі за допомогою ма-

тематичних формул, визначення переліку початкових даних та шуканих результатів, вихідні умови, точність обчислень;

3)вибір методу розв‟язування, оскільки одну й ту саму задачу може бути розв‟язано за допомогою різних методів. Вибір методу має визначатися багатьма чинниками, основними з яких є точність результатів, час розв‟язування, обсяг займаної оперативної пам‟яті. У кожному конкретному випадку за критерій вибору методу беруть один зі згаданих критеріїв;

4)розробляння схеми алгоритму розв‟язування задачі, тобто оптимальної логічної послідовності дій з урахуванням обраного методу розв‟язування для здобуття певних результатів;

5)написання та введення розробленої програми алгоритмічною мовою програмування до комп‟ютера;

6)налагодження програми, тобто пошук і виправлення можливих синтаксичних та алгоритмічних помилок у програмі;

7)тестування – перевірка правильності роботи програми.

Ця послідовність є притаманна для розв‟язування якої завгодно задачі у програмний спосіб. Однак при підготовці задачі кожен етап може мати більш чи менш виражений характер.

1.6Алгоритм, його властивості й засоби описування. Поняття програми

Алгоритм (algorithm) – це система формальних правил, які чітко й однозначно окреслюють послідовність дій обчислювального процесу від початкових даних до шуканого результату. Алгоритм визначає певні правила перетворювання інформації, тобто він зазначає певну послідовність операцій опрацювання даних, щоб здобути розв‟язок задачі.

Походження слова алгоритм: понад тисячу років тому у Багдаді жив Абу Джафар Мухамад ібн Муса аль-Хорезмі, який у своїй праці «Трактат альХорезмі про арифметичне мистецтво індусів» з арифметики та алгебри сформулював правила і окреслив послідовність дій при додаванні та множенні чисел. При переведенні латиною ім‟я автора перетворили в Algorithmi, а з часом методи розв‟язування задач стали називати алгоритмами.

Основні властивості алгоритмів:

детермінованість (визначеність) – однозначність результату обчислювального процесу за заданих початкових даних;

дискретність – поділ обчислювального процесу на окремі елементарні кроки, виконувані послідовно;

ефективність – простота та швидкість розв‟язання задачі за мінімальних потрібних засобів;

результативність – забезпечення здобуття розв‟язку через певну кінцеву кількість кроків;

масовість – забезпечення розв‟язання якої завгодно задачі з класу однотипних.

Задавати алгоритми можна у різні способи:

словесне описування послідовності дій;

аналітичне описування у вигляді формул;

графічне подавання у вигляді схеми алгоритму (блок-схеми);

записування алгоритмічною мовою програмування.

Великого поширення набув графічний спосіб задавання алгоритмів у вигляді схем алгоритмів (блок-схем).

Схема алгоритму (блок-схема) – графічне зображення його структури, в якому кожен етап процесу опрацювання даних подається у вигляді різних геометричних фігур (блоків).

Форма блока зумовлює спосіб дій, а записи всередині – деталі (параметри) відповідного етапу (табл. 1.3). Біля блока можуть бути розміщені певні коментарі.

Блоки поєднуються поміж собою лініями потоку, які для кожного етапу визначають напрямок дій. Усім блокам присвоюють порядкові номери, які проставляються у розриві лінії контуру у лівій частині верхньої сторони зображен-

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

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

Розмір а має бути кратним до 5, наприклад: а = 20 мм. Розмір b = 1.5а. Перевагою блок-схем є те, що за їхньої допомоги можна наочно зобрази-

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

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

Розрізняють три базових алгоритмічних структури: лінійна (послідовність), розгалужена та циклічна (повторювання). Алгоритмічні структури будьякої складності утворюються поєднанням послідовності цих базових алгоритмів. Приклади алгоритмічних структур та їхньої реалізації детально будуть розглянуті у наступних розділах.

Запис алгоритму алгоритмічною мовою програмування має бути зрозумілим не лише людині, а й комп‟ютерові, а тому потребує точного дотримання правил цієї мови. Такий спосіб подавання алгоритму буде розглянутий далі при вивченні мови програмування С++.

Програма – упорядкована послідовність команд, які належить виконувати. Принцип програмного керування, який є основним принципом будови всіх сучасних ЕОМ, за Дж. фон Нейманом, полягає у тому, що всі обчислення, відповідно до алгоритму розв‟язання задачі, мають бути подані у вигляді програми. Кожна команда програми містить вказівки стосовно конкретної виконуваної операції, місця розташування (адреси) операндів та низки службових ознак. Операнди – змінні, значення яких беруть участь в операціях опрацювання даних. Список усіх змінних (початкових даних, проміжних значень та результатів обчислень) є ще одним неодмінним елементом будь-якої програми.

Для доступу до програм, команд та операндів використовуються їхні адреси. За адреси слугують номери комірок пам‟яті ПК, призначених для зберігання об‟єктів.

Питання та завдання для самоконтролю

1)Назвіть основні принципи архітектури комп‟ютерів фон Неймана.

2)В чому полягає принцип відкритої архітектури?

3)Вкажіть основні складові типового персонального комп‟ютера.

4)Яке призначення мікропроцесора?

5)Назвіть енергозалежні та енергонезалежні пристрої пам‟яті.

6)Назвіть призначення програмного забезпечення та його складові.

7)Які функції призвана виконувати операційна система?

8)Що називається файлом?

9)Чим файл відрізняється від теки (каталогу)?

10)Чи може тека зберігати інформацію?

11)Яке призначення мають файли-ярлики?

12)Чи можна створити файл у середині іншого файла?

13)З чого складається ім‟я файла?

14)Які є обмеження на імена файлів? Наведіть приклади правильних і неприпустимих імен файлів.

15)Про що свідчить розширення файла? Які типи файлів Ви знаєте?

16)В який спосіб можна змінити ім‟я файла?

17)Наведіть способи створення текстового файла. Як зберегти набраний текст у файлі?

18)Чим схожі й чим відрізняються текстові редактори Notepad (Блокнот)

іMS Word? Чи можна відкрити файл з розширенням txt у редакторі MS Word? А у редакторі Paint?

19)Що таке біт і байт? Назвіть відомі Вам одиниці вимірювання інфор-

мації.

20)Що таке позиційна система числення і як віднайти значення числа за його записом у певній позиційній системі?

21)Чому інформація в комп‟ютері записується у двійковій системі чис-

лення?

22)Перевести десяткові числа 50, 127, 255, 25.5 до двійкової та шістнадцяткової систем числення.

23)Перевести двійкові числа 1010, 11111, 1010101 до десяткової та шістнадцяткової систем числення.

24)Подати шістнадцяткові числа 3F, 80, F07 у десятковій та двійковій системах числення.

25)Обчислити у двійковій системі числення: 101101 + 1100, 11001 – 101.

26)Обчислити у шістнадцятковій системі числення: А06 + FB, АC6 – E9.

27)Назвіть призначення та способи подання алгоритмів.

28)Перелічіть блоки, використовуванні в схемах алгоритму.

29)Назвіть базові алгоритмічні структури.

30)Що таке програма? Опишіть процес створювання програм.