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

begin

к := 1; с := 0; rez := 0; new_n := n;

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

{Результат множення двох цифр і додавання с.} a:=(new_n mod 10) * (m mod 10) +с;

if a > = p {Якщо результат множення більший за р,}

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

{У протилежному випадку нічого не переноситься} else с := 0; {в наступний розряд.}

{Накопичення результату приписуванням} rez := rez + k * а; {ново? цифри у старший розряд.}

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

{Відсікання обробленоТ цифри першого числа.} new_n .= new_n div 10; end; m := m div 10; {Відсікання обробленої цифри другого числа.}

{Зсув результату на позицію цифри другого числа.} rez := (rez + k * с) * k_n;

{Додавання результату попереднього І поточного множень.} rez_n := add (rezn, rez, p);

k_n := k_n * 10 {Збільшення розрядності результату.}

end; mult := rez_n {Повернення результату в основну програму.}

end;

Функція ділення:

function divis (n, m: longint; p: byte): longint;

var st_n, st_m, st_a: string;

a, b, i: byte;

rez, new_a, ml, k, k1, k2: longint; begin

rez := 0;

Str (n, St_n); {Представления діленого у вигляді рядка.}

Str (m, st_m); {Представления дільника у вигляді рядка.}

ml :=0;k1 :=1;

34

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

for i := 1 to length (strn) do

begin

ml :=m1 + ((m divkl) mod 10)*k1; k1 := k1 * p end; k := 1; {Визначення кількості старших цифр,}

for і := 1 to length (st_n) - length (st_m) {які можна ділити на дільник.}

dok:=k"10; if (n div k) <m then k := k div 10;

{Відсікання тієї частини діленого,} a := n div k; {яка буде ділитися на дільник (а)}

repeat

Str (a, st_a); {Представления значения а у вигляді рядка.}

new_a:=0; k1 := 1;k2:= 1;

{Переведения а в систему числення з основою р.} for i := 1 to length (st_a) do begin

I new_a := new_a + ((a div k2) mod 10) * k1; | k1 :=k1 *p;k2:=k2* 10 end; b := newa div ml; {Визначення поточної цифри у результаті ділення.} rez := rez* 10 + b; {Накопичення результату ділення.}

{Визначення залишку від поточного ділення.} а := sub (a, mult(m, b, р), р);

к := к div 10; {Зменшення розрядності діленого.}

{Знесеиня наступноі цифри діленого для наступного ділення.} if к > 0 then а := а * 10 + ((n div к) mod 10);

{Дописування цифри 0 до результату ділення у разі} while (а < m) and (к > = 10) do {неможливостіділенняанадільник.} begin

rez := rez* 10; k:=kdiv10;

a := a*10 + ((n div k) mod 10); end; until k= 1; str (a, St_a); {Представления а у вигляді рядка.}

new_a:=0;k1 := 1; k2:= 1;

{Переведения а в систему числення з основою р.} for i := 1 to length (st_a) do begin

new_a := new_a + {{a div k2) mod 10) * k1; k1 :=k1 *p;k2:=k2*10 end; b := new_a div m 1; {Визначення результату ділення а на дільник.}

rez := rez * 10 + b; {Дописування останньоТ цифри до результату ділення.} divis := rez; {Повернення результату в основну програму.}

end;

35

ПЕРЕВЕДЕНИЯ ЧИСЕЛ 3 ОДНІЄЇ СИСТЕМИ ЧИСЛЕННЯ В ІНШУ

Ми вже частково торкнулися проблеми переведения чисел 3 однієї системи числення в іншу, маючи справу з системами числення, основа яких менша за 10. Тепер розглянемо загальні правила переведения чисел з однієї системи числення в іншу.

Переведения чисел з 10-Ї системи числення в систему числення 3 ОСНОВОЮ Р

Розглянемо спочатку цілі числа і для прикладу візьмемо деяке число у 10-й системі числення. Нехай це буде число 123₁₀. За законами арифметики можемо про це число сказати, що в ньому одна сотня, два десятки й три одиниці. 3 іншого бо­ку, щоб дізнатися, скільки в заданому числі одиниць, треба визначити остачу від ділення цього числа націло на 10:

123

120

3

10 12

Молодшу цифру числа ми визначили - це 3. Для визначення наступної цифри - кількості десятків - треба частку від по-переднього ділення (12) знову розділити на 10 і знайти остачу:

10 1

12

~10

2

На цьому кроці ми визначили ще й кількість сотень! Адже знайдену частку від ділення (1) вже не треба більше ділити на 10, бо вона менша за 10 і озпачає кількість сотень. Це прави­ло дійсне для виділення цифр будь-якого десяткового числа.

А тепер проаналізуємо наші дії з точки зору системи чис­лення з основою 10. На першому кроці ми поділили число на основу цієї системи числення, щоб з'ясувати, скільки в цьому числі повних десятків. Отримана остача від цього ділення ви-значає кількість одиниць. Далі цей процес продовжили для визначення останніх цифр, поки не отримали частку, меншу за основу цієї системи числення, тобто 10. Так само можна ви-значитися з переведениям числа 123 у сімкову систему числен­ня. Згадавши, що 10₇ = 7₁₀, виконуватимемо ділення в зручній десятковій системі числення, тобто на 7₁₀. Остача від такого ділення націло дасть кількість одиниць у заданому числі у сім-ковій системі числення. Зауважимо, що результат такого ді-лення буде завжди меншим за 7, тобто є цифрою цієї системи

36

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

123 7

2

"₇ 17 7_

53 14

49 "

4-—I Стрілками показаний шлях запису отриманого числа у сім-ковій системі числення. Справді, перша отримана цифра — це кількість одиниць, а остання - кількість 7² {7²₁₀ = 10,):

123₁₀ = 234₇.

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

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

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

Десятков! дроби треба переводити в іншу систему числення в два етапи: окремо цілу частину і окремо дробову. Правило для переведения дробової частини десяткового числа формулюєть-сятак:

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

37

Розглянемо такий приклад:

Виконуючи дії за сформульованим правилом, отримаємо:

Запишемо результат переведения 0,125₁₀ = 0,043₆. У цьому прикладі нам повезло, бо настав момент, коли на третьому кро-ці отримано нульову дробову частину. Тобто заданому числу відповідає точний аналог в іншій системі числення. Але таке бу-вае не завжди. У цьому випадку треба обмежитися деякою точ-ністю при переведенні заданого числа в іншу систему числення.

Доведіть, що при переведенні дробової частини десяткових чисел в іншу систему числення цілі частини, ЯКІ ВІДОК-ремлюються при множенні, завжди будуть цифрами тіє'ї систе-ми числення, в яку здійснюється переведения!

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

procedure to_p (n: longint; p: byte); begin

k := 1; {Контроль завершения процесу переведения.}

while n > = р do begin

a[k] := n mod p; {Визначення поточної цифри переведеного числа.} П := П div p; {Визначення поточної частки від ділення.}

{Визначення порядкового номера наступної цифри результату.) inc(k); end;

{Запис у результуючий масив останньої визначеної} a[k] := п {цифри, яка є останньою часткою.}

end;

Виведення результату переведения заданого числа в систему числення з основою Р можна здійснити за допомогою такого циклу:

for i := k downto 1 do write(a[i]);

38

Переведения чисел із системи числення з основою Р у 10-ву систему числення

Для визначення правила переведения чисел із будь-якої си­стеми числення в десяткову пригадаємо, що кожне число мож-на представити у вигляді суми, записано! за степенями основи пдєї системи числення.

Розглянемо це на прикладі:

123₁₀ - (1 • 100 + 2 • 10 + 3)₁₀ - (1 • 10² + 2 • 10¹ + 3 ■ 10°)₁₀.

Але це справджується не лише для десяткової системи чис­лення. Наприклад, у числі 234₇ двічі присутнє число 100₇, три рази число 10₇, чотири рази число 1_г Це означав, що справед-ливий запис:

234₇ = (2 • 10⁸ + 3 • 10¹ + 4 • 10°)₇.

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

(а,_а1а₂...а_п)_р = (а₀ • 10" + а,- Ю-¹ + а₂ • Ю""² + ... + а„ • 10°)_р.

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

234₇ = (2 • 10² + 3 ■ 10^і + 4 • 10°). = = (2 ■ 7² + 3 • 7^і + 4 • 7°)₁₀ - 123₁₀.

Отже, ми перевірили результат попереднього переведения 3 десяткової системи числення у сімкову, яке виконали раніше.

Сформулюємо правило переведения чисел із системи чис­лення з основою Р у десяткову систему числення.

^: Для переведения будь-якого числа із системи числення з ос­новою Р у десяткову систему числення треба задане число записати у вигляді суми за степенями основи даної системи числення, тобто 10 , потім замінити усі числа на відповідні їм десяткові числа та виконати вказані арифметичні дії в десятковій системі числення.

При переведенні дробових чисел із системи числення з осно­вою Р в десяткову систему числення треба користуватися тим самим правилом, враховуючи лише, що для дробової частини показники основи системи числення будуть від'ємними:

39

321,12, = (3 • 10² + 2 • 10^і + 1 • 10° + 1 • 10"¹ + 2 • 10'²)₄ = = (3 • 4² + 2 • 4¹ + 1 ■ 4° + 1 • 4"¹ + 2 • 4"²)₁₀ - 57, 375₁₀.

Перейдемо до представления алгоритму переведения чисел із системи числення з основою Р у десяткову у вигляді процеду-ри мовою Pascal. Розглянемо випадок, коли Р < 10:

procedure to 10 (n: longint; р: byte; var rez: iongint); var k: longint; begin

k := 1; rez := 0;

while n > 0 do {Контроль завершения процесу переведения.}

begin {Формування результату переведения додаванням а, * f*.}

rez := rez + (n mod 10) * k;

П := П div 10; {Визначення наступно! цифри заданого числа.}

к := к * р; {Визначення степенів основи системи числення.}

end; end;

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

ЗВ'ЯЗОК МІЖ СИСТЕМАМИ ЧИСЛЕННЯ 3 ОСНОВОЮ 2*

Між системами числення з основами 2, 8 і 16 є чудовий зв'язок. Розглянемо спочатку співвідношення між цифрами ві-сімкової системи числення та відповідними їм числами двійко-вої системи (табл. 1).

Таблица 1

40

Отримати цю таблицю неважно і немае потреби її запам'я-товувати, оскільки, збільшуючи цифри вісімкової системи чис­ления, одночасно збільшуємо відповідні їм числа двійкової си­стеми. Пам'ятаючи це, завжди можна відтворити цю таблицю. Зверніть увагу на те, що в правій частині таблиці містяться всі можливі комбінації двійкових цифр у трьох позиціях. Ці три цифри називають тріадою. Тобто можна сказати, що кожній цифрі вісімкової системи числення відповідає певна тріада двійкових цифр. Чому саме тріада, а не менше і не більше? А справа у тім, що 2³ = 8. Справді, створюючи у трьох позиціях за допомогою двох цифр 0 та 1 усі можливі комбінації, зможе-мо нарахувати їх тільки вісім. Враховуючи цю закономірність, сформулюємо правило переведения чисел.

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

Наприклад,

35106₈ = 011 101 001 000 110₂ = 11101001000110₂.

Для переведення чисел із двійкової системи числення у ВІ-сімкову треба розбити двійкове число на тріади справа налі-во і замінити кожну тріаду відповідною вісімковою цифрою, зберігаючи послідовність тріад, а саме:

10100110000011101₂ = 010 100 110 000 011 101₂ = 246035₈.

Тепер перейдемо до ознайомлення з шістнадцятковою си­стемою числення таїї зв'язком із двійковою системою. Розгля-немо таблицю 2.

Таблиця2