Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

0 < а[і] < 65 535, то можна зробити висновок, що елементи масиву треба описати типом word.

По-друге, якщо для значень змінної і даються обмеження

1 < N < 100, то можна передбачити, що не виключено застосу-

вання прямих методів, які не дуже оптимізують обробку еле-ментів цього масиву. Якщо ж 1 < N < 32 000, то це підказує, що при використанні середовища програмування з обмеженою пам'яттю, тобто 64 Кб, ми не зможемо розмістити додатковий масив. Тому треба розробляти алгоритм з використанням лише одного заданого масиву значень. Якщо ж 1 < N < 1 000 000, то такий масив елементів неможливо одночасно розмістити у па-м'яті комп'ютера, тому доцільно розробляти алгоритм, який обробляє його елементи покроково під час введения.

По-трете, треба дуже уважно описувати результуючі змінні. Інколи результат обчислення може бути дуже великим числом. Треба оцінити можливе його максимально значения і описати відповідним типом, інакше можна втратити правильне значен­ия результуючої величини. Як це може статися, детальніше розглянемо в розділі II. Тому уважна опднка результату вико-нання алгоритму може підказати, яким типом треба ЇЇ описати: word, longint. А можливо, навіть цей результат виходить за ме-жі стандартних типів і для збереження його значения треба застосовувати спеціальні алгоритми. Прикладом можуть бути задачі на обчислення JV! та a^N, де N набуває великих значень.

Звичайно, наведені поради є відносними, але й вони свідчать про те, що навіть з умови задачі можна зробити дуже корисні висновки щодо розробки алгоритму.

/ Запитання для самоконтролю

1. Що розуміють під плануванням роботи над алгоритмом?

2. Який процес називається покроковою деталізацією алгоритму? У чому він полягає? Наведіть власний приклад покрокової дета-лізації алгоритму.

3. Яким чином робота над представлениям алгоритму у вигляді програми може допомогти у його розробці?

4. Який спосіб розробки алгоритму називають структурним пло­дом до його побудови?

5. Яку роль у структурному підході до побудови алгоритму ВІДІ-грають допоміжні алгоритми?

6. Яке програмування носить назву низхідного?

І7. Яке програмування носить назву висхідного? 8. Яку роль у доведены розробленого алгоритму до остаточного варіанта відіграє тестування? Наведіть власний приклад алго­ритму та його тестування. 9. Яким чином можна фіксувати час виконання Pascal-програми? 10. У чому полягає методика використання «заглушок» у програмі?

25

СИСТЕМИ ЧИСЛЕННЯ. ПРЕДСТАВЛЕНИЯ ІНФОРМАЦІЇ У КОМП'ЮТЕРІ

а о

0. оо

1. о

У вас, мабуть, виникло запитання: чим можна пояснити зв'язок між комп'ютерами та системами числения? А справа ось у чому. Ми з вами звикли у своему повсякденному житті користуватися числами, що задаються за допомогою десяти цифр - від 0 до 9. Але виявляеться, що комп'ютер безпосе-редньо такі числа сприйняти не може. Справа в тому, що стан електронних елементів будь-яких комп'ютерів залежить від того, проходить чи ні в даний момент через них електричний струм. Ці два стани можна позначити цифрами 0 та 1. Тобто вся інформація, яку обробляє комп'ютер, повинна бути закодована тільки цифрами 0 та 1. Це означав, що комп'ютер оперуе не числами, записаними за допомогою цифр від 0 до 9, а їхніми аналогами, представленими за допомогою цифр 0 та 1. Для то­го щоб представити результат обчислення у зручній для корис-тувача формі, відбувається зворотний процес.

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

Поняття систем числення

Під системою числення розуміють сукупність правил на-йменування та запису чисел.

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

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

26

Тепер можна пояснити, чому система числения, з якою ви знайомі з дитинства і якою користуються всі навколо вас, нази-вається десятковою. Саме десять цифр міститься в інтервалі між 0 та 9.

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

Наприклад, поряд із десятковою системою числення існува-

ла ще й дванадцяткова. Залишки її є і в наш час. Інколи замість

«дванадцять» кажемо «дюжина». Сервіруючи святковий стіл,

рахуємо виделки, ложки, ножі порціями по дванадцять, всі

• сервізи комплектуются на дванадцять персон.

Багато африканських племен користувалися п'ятірковою системою числення.

У народів майя та ацтеків була поширена двадцяткова си­стема числення.

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

Були системи числення, які, за припущенням істориків, утворилися злиттям кількох систем числення. Прикладом то­му може бути система числення з основою 60, що існувала у Ва-вилоні. Є різні думки та припущення щодо утворення ЦІЄЇ системи числення. Одні дослідники вважають, що вона утвори-лася злиттям шісткової та десяткової систем числення, якими користувалися два різні племені. Інші вважають, що відбулося злиття п'ятіркової та дванадцяткової систем числення. При­найми!, мабуть, саме таким чином між ними було досягнуто згоди. Нам сьогодні складно уявити, яким же чином рахували ці люди! Але історія залишається історією.

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

Розрізняють два типи систем числення - позиційні та не-позиційні.

Позиційними системами числення називають такі системи, в яких «вага» кожної цифри в числі заложить від 'її місцепо-ложення в записі цього числа. Системи числення, які побу­дивши на іиших принципах, називають непозиційними.

27

Наприклад, у записі числа 1212 у десятковій системі числен­ня використано всього дві цифри 1 та 2, кожна з яких зустрі-чається в числі двічі. Перша цифра 1 зліва означає кількість тисяч у числі, а наступив одиниця - кількість десятків. Ліва цифра 2 означає кількість сотень у записаному числі, а остання цифра 2 показує кількість одиниць у числі. Цей приклад де-монструє те, що кожна цифра робить свій внесок у значения числа, який залежить від позиції цифри.

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

Наприклад, I - один, V - п'ять, X - десять, L - п'ятдесят, С - сто, D - п'ятсот, М - тисяча і т. д.

Наведемо приклади деяких чисел у цій системі числення та їхні аналоги у десятковій системі:

LXXXVII - 87; XCIX - 99; MLIV - 1054; CLXVI - 166.

Ви, мабуть, звернули увагу на те, що числа в римській систе-мі числення компонуються із символів у порядку спадання їх значень. Виняток складають лише числа IV (4), IX (9), XL (40), ХС (90), СМ (900) i т. д. Тобто якщо менше за «вагою» число пе­редув більшому, то його треба не додавати до результату, а від-німати. Справді, запис IV (4) компактніший, ніж ИИ, а ХС (90) -компактніший, ніж LXXXX, хоча за значениями вони рівні.

Слід зауважити, що поняття основи системи числення на непозиційні системи не поширюються.

Надалі матимемо справу лише з позиційними системами числення. Для того щоб подальша інформація не викликала зайвих труднощів, давайте спробуемо порахувати предмета у вашій кімнаті в різних системах числення. Будемо пам'ятати, що числа в будь-якій позиційній системі числення утворюють-ся комбінацією цифр цієї системи числення. А саме, коли, ра-хуючи в десятковій системі числення, ми доходимо до числа 9, то переходимо на двоцифрові числа, комбінуючи спочатку циф­ру 1 з усіма іншими цифрами (10, 11,12,..., 19), потім цифру 2 з тими самими цифрами (20, 21, 22, ..., 29) і так далі, поки не дійдемо до числа 99. Шсля цього починаемо утворювати три-цифрові числа за тими самими правилами: 100, 101, ..., 109, 110, 111, ..., 199, 200, 201, .... 999. На перший погляд досить банальні речі! Але саме розуміння цього принципу допоможе вам створювати числа у різних системах числення, коли будете

28

рахувати предмети. Для прикладу давайте розглянемо 10-ву, 8-ву та 5-ву системи числения.

10-ва: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ... 8-ва: 0, 1, 2, 3, 4, 5, 6, 7,10, 11, 12, 13, 14, 15, 16, 17, 20, ... 5-ва: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31, ...

Бачимо, що в ycix системах числения зустрічаються одні й ті самі числа, але значения їхнє в різних системах різне. Для того щоб визначати, в якій системі числения записане дане число, вказуватимемо індексом біля цього числа основу системи чис­ления, в якій воно записане: 5₈, 10₁₆, 101₂.

Ще один важливий висновок зробимо з наведеного прикла­ду - чим менша основа системи числення, тим раніше з'яв-ляється в рахунку число 10, а потім 20 і т. д. Справді, адже цифр в арсеналі таких систем числення менше, тому й дово­диться раніше переходити на створення двоцифрових, трициф-рових чисел.

Зазначимо ще один цікавий факт. Виявляється, що у 10-й системі числення остання цифра 9, у 8-й - 7, а у 5-й - 4. Оскільки першою цифрою в будь-якій системі числення є циф­ра 0, остання можлива цифра в ній завжди на одиницю менша за основу цієї системи числення.

I на останок, звернімо увагу на таку закономірність:

8_1в=10₈;б₁₀-10₆.

Аналогічні рівності можна отримати при порівнянні будь-якої системи числення з десятковою: 2₁₀ = Ю₂, 4₁₀ = 10₄, 16₁₀ = 10₁₆.

Щоб завершити початкове ознайомлення з позиційними системами числення, давайте порахуємо в системі числення з основою 2:

0,1,10,11,100,101,110, 111,1000, 1001,1010, 1011,1100, 1101,...

Жахливо, чи не так? Замість двоцифрового десяткового чис­ла 13 треба записувати чотирицифрове двійкове число 1101, а далі - ще більшеі Однак виявляється, що для комп'ютера це дуже зручно.

АРИФМЕТИЧНІ ДІЇ В ПОЗИЦІЙНИХ СИСТЕМАХ ЧИСЛЕННЯ

На уроках математики в початковій школі ви вивчили пра­вила користування чотирма арифметичними діями: додаван-ня ( + ), віднімання (-), множення (•) та ділення (:). Виявляєть-ся, що ці правила абсолютно однакові для всіх позиційних систем числення. Але тепер вам треба створити нові таблиці додавання та множення.

29

Перш ніж почати рахувати в різних системах числення, зробимо ще одне суттєве зауваження. Ви, мабуть, звернули увагу на те, що всі розглянуті системы числення використо-вують відомі нам цифри десяткової системи. Це тому, ЩО ЇХНЯ основа менша за десять. При цьому деякі цифри навіть вияв-ляються зайвими! Якщо ж розглянути, наприклад, шістнад-цяткову систему числення, то там справа буде зовсім іншою. Але про це трохи пізніше. А зараз не будемо забувати, що наве­ден! приклади стосуються тільки систем числення, в яких ос­нова менша за 10.

Розглянемо спочатку дію додавання. Додаватимемо числа в стовпчик по розрядах - спочатку одиниці, потім десятки, після них сотні і т. д.

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

Приклади:

2₃ + 2₃«(2₃ + 1₃) + 1₃«11₃; 5₈ + 5₈ = (5₈ + 3₈) + 2₈-12₈; 8_e + 7_n«(8₉ + l_e) + 6_e-16₉.

Наводимо приклад додавання більших чисел:

4532_в

+ ^в

5315₆

14251_в

Тепер розглянемо дію віднімання. Пригадаємо, що коли при відніманні в десятковій системі числення в деякому роз-ряді зменшуване менше за від'ємник, то ви позичаєте одиницю у найближчого зліва від нього розряду, значения якого більше за 0. Цей принцип застосовуеться в будь-якій позиційній системі числення. Як ілюстрацію дії віднімання розглянемо приклад:

_50062₈ 37654₈ 10206₈

Спробуйте отримати результат цього прикладу, виконавши всі дії покроково. А щоб перевірити отриманий результат, ви-конайте додавання:

37654₈ + 10206₈ = ?????„.

30

Наступна дія - множення. Хоча її можна розглядати як ба-гатократне додавання, але всі ми пам'ятаємо таблиці множен­ня, які заучували для швидкого виконання цієї дії. Звичайно, що пам'ятати таблиці множення для різних систем числення неможливо. Треба лише забути про десяткову систему числення і перейти у «світ» тієї системи числення, в якій працюємо. При пьому треба користуватися лише цифрами цієї системи числен­ня. Якщо все ж таки важко зорієнтуватися в новій системі чис­лення, то слід замінити множення на багатократне додавання.

Розглянемо приклад, результатом якого можна скористати-ся для перевірки власного результату обчислення:

_х5413.

34500„

Насамкінець розглянемо дію ділення. Здається, що вона виглядає найскладнішою серед усіх арифметичних дій, але і з нею нескладно розібратися. Розглянемо такий приклад:

2546₇: 12₇ = ?_.

Виконуватимемо дію ділення у стовпчик так само, як і в десятковій системі числення.

Розглянемо перший етап ділення: 25. : 12- = ?-. Скористае-мося тим, що в якій би системі числення ми не рахували, реальна кількість того, що рахуємо, і не збільшиться, і не змен-шиться. Переведемо числа, з якими маемо справу, в десяткову систему числення і виконаємо дії в ній. Число 25₇ мае два сім-кових «десятки», абодвідесятковісімки: (2 • 10). = (2 ■ 7)_]0 = 14₁₀. У числі 25. ще лишилося п'ять сімкових «одиниць». Але ми знаемо, що 5₇ = 5₁₀, тому нам лишилося виконати дію: 14₁₀ + -г 5₁₀ = 19₁₀. Аналогічно переведемо число 12₇ у десяткову си­стему числення:

12.-(1*10 + 2)₇-(1*7 + 2)₁₀-9₁₀.

Тепер треба лише виконати дію:

1"ю ^: "ю ⁼ МО*

За правилами виконання дії' ділення у стовпчик треба вико­нати ділення націло, тобто виділити частку й остачу:

19 9_ 18 ²

1

Зробимо висновок з отриманого результату: якщо значения 9₁₀ поміститься двічі у числі 19₁₀, то й 12₇ так само двічі поміс-

31

титься у числі 25₇, а остача в обох випадках буде однаковою (1₇ - 1₁₀). Шсля такого детального пояснения подальше вико-нання дій не викликатиме труднощів:

2546,4₇

_14₇ 12,

26₇ 24,

24₇

12,

212,2₇

Доведіть, що, використовуючи такий принцип ділення в системах числення з основами, меншими за 10, завжди мати-мемо результат, цифри якого належать даній системі числен­ня. Це твердження справедливе і для систем числення з осно­вою, більшою за 10, але спершу треба домовитися, якими сим­волами позначатимемо цифри, більші за 9.

А тепер представимо у вигляді окремих функцій алгоритми виконання арифметичних дій у заданих системах числення. Для спрощення розглянемо випадок, коли основи цих систем числення не перевищують 9. В іншому випадку необхідно буде домовлятися, яким чином позначати цифри цих систем чис­лення. Обмежимося також цілими числами та відсутністю пе-ревірки коректності введения початкових даних.

Функція додавання може виглядати так:

function add (n, m: longint; p: byte): longint; var c, a: byte; k, rez: longint; begin

k := 1; с := 0; rez := 0; while (n > 0) or (m > 0) do begin

{Порозрядне підсумовування цифр двох чисел І значения с.) a:=(nmod 10) + (mmod 10) +с;

If а > = р (Якщо отримана сума більша за р,)

{то визначаємо кількість одиниць і десятків.} then begin с := a div p; a := a mod p end

else с '.= О', {У протилежному випадку кількість десятків с = 0.)

(Накопичуємо отриманий результат, додавши}

rez := rez + k * а; {наступну цифру у наступний розряд.)

к := к * 10; {Збільшуємо розрядність результату.)

{Відсікаємо оброблену цифру першого числа.} {Відсікаємо оброблену цифру другого числа.}

I n:=ndiv10; | m:=mdiv10; end;

add := rez + k*c; {Повертаємо в основну програму отриманий результат.}

end;

Функція віднімання:

function sub (n, m: longint; p: byte): longint; var c, a: byte; pr: shortint; k, rez: longint; begin pr:= 1; if m > П then {Визначаємо більше з двох чисел і знак результату.}

begin с := n; n := m; m := c; pr := -1 end; k:= 1;c:=0;rez:=0; while (n >0)or(m >0)do

begin {Якщо поточна цифра першого числа не дорівнює 0}

{і для попереднього розряду позичена 1,} if (п mod 10 <> 0) and (с = 1)

{то від поточноі цифри віднімемо 1 І с = 0.} then begin а := (n mod 10) - 1; с := 0 end

{Якщо поточна цифра першого числа дорівнює 0} {І позичена з попереднього розряду 1,}

else if (n mod 10 = 0) and (с = 1)

then a := p {то значения рівне p.)

{У протилежному випадку поточна цифра не змінюється.} else а := n mod 10; а := а — с; {Визначення поточної цифри першого числа.}

{Якщо поточна цифра першого числа більша} if а > = (m mod 10) {за поточну цифру другого,}

then а := а — (m mod 10) {то знаходимо різницю.}

else begin

{Інакше позичимо у старшого розряду десяток, тобто р,} а := а + р - (m mod 10);

с := 1; {визначимо ознаку 1 позичення від старшого розряду.} end;

{Накопичуємо результат віднімання,}

rez := rez + а * к; к:=к*10; n :=ndiv 10; m :=mdiv 10; end; sub := pr * rez; end;

{дописуючи нову цифру у старший розряд.}

{Збільшуємо розрядність результату.}

{Відкидаємо оброблену цифру першого числа.}

{Відкидання обробленої цифри другого числа.}

{Повертаемо результат в основну програму.}

2 Вдюршпшт.» 1» и

33

Функція множення:

function mult(n, m: longint: p: byte): longint; var c, a: byte;

k, k_n, rez, new_n, rez_n: longint; begin

rez_n :=0; k_n := 1;

{Перше число більше, друге - менше.} if m > n then begin с := n; n := m; m := с end;

while m > 0 do {Покрокове множення на кожну цифру другого числа.}