18292

НЕДЕСЯТКОВІ ПОЗИЦІЙНІ СИСТЕМИ ЧИСЛЕННЯ

Лекция

Математика и математический анализ

Лекція 19 НЕДЕСЯТКОВІ ПОЗИЦІЙНІ СИСТЕМИ ЧИСЛЕННЯ Недесяткові позиційні системи числення: запис читання і порівняння чисел в них. Алгоритми додавання і віднімання чисел в недесяткових позиційних системах числення. Таблиці додавання. Алгоритми множення і д...

Украинкский

2013-07-07

158 KB

33 чел.

Лекція 19

НЕДЕСЯТКОВІ ПОЗИЦІЙНІ СИСТЕМИ ЧИСЛЕННЯ

  1.  Недесяткові позиційні системи числення: запис, читання і порівняння чисел в них.
  2.  Алгоритми додавання і віднімання чисел в недесяткових позиційних системах числення. Таблиці додавання.
  3.  Алгоритми множення і ділення чисел в недесяткових позиційних системах числення. Таблиці множення.
  4.  Перехід від запису чисел в одній позиційній системі до запису в іншій.
  5.  Обчислювальні прилади, що використовуються при обчисленнях

д) Подільність цілих невід’ємних чисел.

  1.  Недесяткові позиційні системи числення: запис,

читання і порівняння чисел в них

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

Для запису чисел у різних позиційних системах числення користуються цифрами десяткової системи числення. Наприклад, цифрами системи числення з основою g = 2 є 0 і 1, а при g = 5 – 0, 1, 2, 3 і 4. Якщо ж основа системи числення g > 10, то її цифри, як багатоцифрові числа десяткової системи числення, беруться в дужки. Наприклад, якщо основа системи числення g = 12, то цифрами її будуть 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (10), (11).

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

Записом натурального числа у позиційній системі числення з основою g ³ 2 називається подання його у вигляді

a = an·gn + an1·gn1 + … + a1·g + a0,

де a0, a1, …, an1, an – цифри системи числення і an ¹ 0.

Сума a = an·gn + an1·gn1 + … + a1·g + a0 коротко записується .

Числа 1 = g0, g1, g2, …gn–1, gn називаються розрядними одиницями, а доданки a0, a1·g1, a2·g2, …, an–1·gn–1, an·gnрозрядними доданками.

При читанні числа, записаного у позиційній системі числення з основою g, послідовно називають цифри числа, починаючи з найвищого розряду, і основу системи числення. Наприклад, число 250648 читається: "два п'ять нуль шість чотири у системі числення з основою вісім".

Запис числа у позиційній системі числення з основою g показує скільки одиниць найнижчого розряду містить дане число і як вони розподілені у числі як одиниці вищих розрядів.

Теорема 5. Запис натурального числа у позиційній системі числення з основою g > 1 завжди існує і єдиний.

► І. Доведення існування запису числа у позиційній системі числення з основою g > 1 проведемо методом математичної індукції.

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

Припустимо, що твердження істинне для всіх натуральних чисел b таких, що g – 1 £ b < a.

Доведемо, що твердження істинне і для натурального числа a. Поділимо a на g з остачею

a = g × q + a0,  a0 < g.

(1)

Оскільки за властивістю ділення q < a, то за припущенням

q qk·gk + qk–1·gk–1 + … + q1·g + q0.

Звідси, користуючись (1), одержуємо

a = (qk·gk + qk–1·gk–1 + … + q1·g + q0g + a0.

А тому за дистрибутивним законом множення відносно додавання

a = qk·gk+1 + qk1·gk + … + q1·g2 + q0·g + a0,

де qk, qk1, …, q0, a0 – цифри даної системи числення і qk ¹ 0. Отже, твердження істинне і для числа a.

Тоді за принципом математичної індукції зазначене вище твердження буде істинним для будь-якого натурального числа a.

II. Доведемо тепер єдиність запису натурального числа у позиційній системі числення з основою g.

Припустимо, що існує принаймні два записи числа a:

a = an·gn + an1·gn1 + … + a1·g + a0

і

a = cs·gs + cs1·gs1 + … + c1·g + c0.

На основі транзитивності відношення рівності маємо

a = an·gn + an1·gn1 + … + a1·g + a0 = cs·gs + cs1·gs1 + … + c1·g + c0.

(2)

Користуючись законами операцій додавання і множення, рівність (2) можна записати

(an·gn1 + an1·gn2 + … + a2·g + a1g + a0 =

= (cs·gs1 + cs1·gs2 + … + c2·g + c1g + c0.

Числа an·gn1 + an-1·gn2 + … + a2·g + a1 i cs·gs1 + cs1·gs2 + … + c2·g + c1 є неповними частками, a0 і c0 – остачами при діленні a на g. За теоремою про ділення з остачею неповна частка і остача єдині, отже,

an·gn1 + an-1·gn2 + … + a2·g + a1 = cs·gs1 + cs1·gs2 + … + c2·g + c1 і a0 = c0 .

Міркуючи аналогічно, через скінченне число кроків отримаємо n = s, a0 = c0, a1 = c1, … , an–1 = cn–1, an = cn.  ◄

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

  1.  Алгоритми додавання і віднімання чисел в недесяткових позиційних системах числення. Таблиці додавання
  2.  Алгоритми множення і ділення чисел в недесяткових

позиційних системах числення. Таблиці множення

Порівняння цілих невід'ємних чисел і алгоритми виконання арифметичних операцій над ними у різних позиційних системах числення здійснюється так само, як і у десятковій системі числення, при цьому тільки потрібно враховувати основу системи числення і пам'ятати, що g одиниць нижчого розряду дорівнюють одній одиниці наступного вищого розряду, і, навпаки, одна одиниця вищого розряду дорівнює g одиницям сусіднього нижчого розряду. Наприклад, число 324057 > 323667, бо 3 = 3, 2 = 2, а 4 > 3.

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

Задача 2. Обчислити значення виразу, який складений з чисел, що записані у системі числення з основою 6:

(23456 + 32356) : 246 + (50026 – 25346) · 356.

► 1. Складемо таблиці додавання і множення одноцифрових чисел у системі числення з основою 6.

+

0

1

2

3

4

5

×

0

1

2

3

4

5

0

0

1

2

3

4

5

0

0

0

0

0

0

0

1

1

2

3

4

5

10

1

0

1

2

3

4

5

2

2

3

4

5

10

11

2

0

2

4

10

13

14

3

3

4

5

10

11

12

3

0

3

10

13

20

23

4

4

5

10

11

12

13

4

0

4

12

20

24

32

5

5

10

11

12

13

14

5

0

5

14

23

32

41

2. Користуючись побудованими таблицями, виконаємо операції:

1)

+

2

3

4

5

2)

5

0

0

2

3)

1

0

0

2

4

2

4

3

2

3

5

2

5

3

4

5

2

2

1

4

1

0

0

2

4

2

0

2

4

4

2

2

4

1

4

4

1

4

4

0

4)

Ч

2

0

2

4

5)

+

1

1

5

4

1

2

3

5

2

1

4

+

1

4

2

1

2

1

2

0

0

3

0

1

0

1

2

0

1

1

5

4

1

2

Відповідь: 1200306.  ◄

Особливо просто виконуються арифметичні операції у двійковій системі числення. Наприклад:

1)

+

1

0

1

1

1

2)

×

1

1

0

1

3)

1

1

1

0

1

1

4)

1

0

0

0

1

1

1

0

1

1

1

0

1

1

0

1

1

0

0

1

1

0

1

0

1

1

1

1

1

0

0

1

0

0

+

1

1

0

1

1

0

1

0

1

1

1

1

1

1

0

1

1

0

1

1

0

0

0

0

0

1

1

0

1

1

0

1

0

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

  1.  
    Перехід від запису чисел в одній позиційній

системі до запису в іншій

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

Нехай натуральне число записано у системі числення з основою g і потрібно записати його у системі числення з основою h. За теоремою 5 такий запис існує і єдиний. Отже,

a = bk·hk + bk–1·hk–1 + … + b1·h + b0,

(1)

де b0, b1, … , bk–1, bk ¹ 0 – цифри позиційної системи числення з основою h.

Скориставшись законами операції додавання і множення цілих невід'ємних чисел, рівність (1) можна записати

a = (bk·hk–1 + bk–1·hk–2 + … + b2·h + b1h + b0,  b0 < h.

(2)

Позначимо

q0 = bk·hk–1 + bk–1·hk–2 + … + b2·h + b1.

Тоді рівність (2) запишеться

a = h·q0 + b0,  b0 < h,  q0 < a.

(3)

Відношення (3) показують, що b0 є остачею, а q0 – неповною часткою при діленні a на h з остачею.

Застосуємо до числа q0 ті ж самі міркування, що й до числа a, і будемо мати

q0 = (bk·hk–2 + bk–1·hk–3 + … + b3·h + b2h + b1,  b1 < h.

(4)

Якщо ввести позначення q1 = bk·hk–2 + bk–1·hk–3 + … + b3·h + b2, то відношення (4) запишуться

q0 = h·q1 + b1,  b1 < h1,  q1 < q0.

(5)

Відношення (5) показують, що числа q1 і b1 є відповідно неповною часткою і остачею при діленні числа q0 на h з остачею.

Такі міркування проводяться поки на кроці з номером k – 1 не одержимо qk–1 < h і будемо мати bk = qk–1.

Отже, можемо визначити всі цифри запису числа a у системі числення з основою h.

Таким чином, метод ділення виконується за такою схемою.

1. Якщо дане число менше від основи h нової системи числення, то воно запишеться у ній як одноцифрове число.

2. Якщо число не менше від основи h нової системи числення, то воно у цій системі містить і одиниці вищих розрядів. Щоб знайти їх кількість, потрібно поділити дане число на h. Частка від ділення вказує, скільки одиниць другого розряду є у числі, а остача – скільки одиниць першого розряду. Якщо одержана частка не менша від h, то дане число містить одиниці ще вищого третього розряду. Щоб знайти їх кількість, слід одержану частку поділити на h. Цей процес продовжується поки не одержиться частка, яка менша від h. Вона буде вказувати кількість одиниць найвищого розряду, а всі остачі вказуватимуть кількість одиниць наступних нижчих розрядів у запису даного числа у позиційній системі числення з основою h.

3. Усі операції виконуються у старій системі числення з основою g, а тому цим способом зручно користуватися, коли g > h, бо тоді h записується як одноцифрове число у системі числення з основою g і остачі від ділення будуть менші від h, отже, вони будуть одноцифровими числами у новій системі числення.

Методом ділення зручно користуватися також, коли g = 10, бо тоді добре відомі алгоритми виконання операцій.

Задача 3. Число 25647 записати у системі числення з основою 6.

► Оскільки 7 > 6, то скористаємося методом ділення. Послідовно ділимо число 25647 і частки, які отримуються, на число 6. Дістанемо

2

5

6

4

7

6

2

4

3

2

1

6

1

6

2

4

3

6

6

1

5

5

1

3

3

4

1

4

5

1

3

6

0

5

Відповідь: 25647 = 43056.   ◄

Теоретичною основою способу множення є таке представлення числа a, записаного у позиційній системі числення з основою g:

a = an·gn + an–1·gn–1 + an–2·gn–2 + … + a2·g2 + a1·g + a0 =

= ((…(an·g + an–1)×g + an–2g + … + a2g + a1g + a0.

Якщо виконати усі зазначені тут операції у системі числення з основою h, то одержане число буде також записане у системі числення з основою h.

Суть методу множення можна викласти так:

1. Якщо дане число менше h, то воно запишеться у ній як одноцифрове.

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

3. Обчислення проводяться у новій системі числення. А тому методом множення користуються тоді, коли g < h, бо тоді всі цифри і основа старої системи числення є цифрами нової системи числення, або ж коли переходять від будь-якої системи числення до десяткової.

Задача 4. Число 5301428 записати у десятковій системі числення.

► Переходимо до десяткової системи числення, а тому скористаємося методом множення. Обчислення проводяться у десятковій системі числення.

5·8+3

=43

 

× 8

344

+0

=344

×   8

2572

+1

=2753

×     8

22024

+4

=22028

×       8

176224

+2

=176226

Відповідь: 5301428 = 176226.  ◄

Задача 5. Число 23134 записати у системі числення з основою 6.

► Оскільки 4 < 6, то скористаємося методом множення. Обчислення проводимо у системі числення з основою 6.

2·4+3

=15

 

× 4

112

+1

=113

×   4

500

+3

=5036

Відповідь: 23134 = 5036.  

  1.  Обчислювальні прилади, що використовуються при обчисленнях

д) Подільність цілих невід’ємних чисел.

Люди досить давно стали конструювати і використовувати обчислювальні прилади. Спочатку «лічильні дошки» і рахівниці, а потім арифмометри, мікрокалькулятори та ЕОМ.

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

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

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

Для виконання дії віднімання відкладають зменшуване і послідовно, починаючи від вищого розряду числа, відкладають від'ємник. Якщо в деякому розряді на дротині не вистачає кісточок, то знімають одну кісточку на сусідньому верхньому розряді, а в даному розряді додають доповнення до десяти числа даного розряду, яке треба було відняти.

Виконують на рахівниці операції множення і ділення. Проте виконання цих операцій громіздке. Ці операції зручно виконувати на арифмометрі, клавішних автоматичних машинах, мікрокалькуляторах та ЕОМ.

Найбільш широке використання набули ЕОМ. Вони зберігають всю необхідну для розв'язування задачі інформацію, переробляють її і автоматично керують обчислювальним процесом, згідно зі складеною програмою.

За короткий час від початку перших машин до машин четвертого покоління, швидкість виконання операцій зросла від 50 до мільярдів операцій за секунду. Сучасна ЕОМ це складна система різноманітних електронних і механічних пристроїв. Основними з них є:

запам'ятовуючий пристрій (пам'ять), який сприймає, зберігав і видає команди програми й оброблювану інформацію;

процесор, який складається з керуючого пристрою і арифметико-логічного пристрою;

пристрій для введення програм і вхідних даних;

пристрій для виведення результатів;

пульт керування.

Усі ці пристрої з'єднані каналами зв'язку, по яких передається інформація. Пам'ять ЕОМ складається з оперативної і зовнішньої. У пам'ять вся інформація надходить у закодованому вигляді. Код цифровий еквівалент деякого символу. Кожному символу ставиться у відповідність деяке число. Для запам'ятовування інформації виділяються фіксовані ділянки пам'яті — комірки. Усі комірки однакові. У кожний розряд комірки можна помістити цифру 0 чи 1 двійкової системи числення (один біт інформації). Всі комірки оперативної пам'яті послідовно нумеруються, тобто кожній комірці присвоюється певний номер (адреса).

Зараз оцінюють ємність пам'яті ЕОМ у байтах. Кожний байт складається з 8 бітів.

Зовнішні запам'ятовуючі пристрої це магнітні стрічки, диски, барабани тощо.

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

5144. Наследственная патология 87.5 KB
  Наследственная патология Программа геном человека завершена в 2012 году. 2% генома кодируют белки, а большинство последовательность. 25.000 генов содержат информацию о 100.000 белковых молекул. Геномика Геномика – это наука занима...
5145. Биотрансформация. Виды трансформаций. Метаболическая трансформация 62 KB
  Биотрансформация. Виды: Метаболическая трансформация – превращение веществ за счет окисления, восстановления и гидролиза. Конъюгация – это биосеинтетический процесс, сопровождающийся присоединением к лекарственным веществ или его ...
5146. Государственное регулирование внешнеэкономической деятельности 47.09 KB
  Государственное регулирование внешнеэкономической деятельности Государство, выражая интересы всего общества, устанавливает правила ведения внешнеэкономической деятельности и воздействует на участников данной деятельности различными способами. Госуда...
5147. Правовой статус российских и иностранных субъектов внешнеторговой деятельности 18.19 KB
  Правовой статус российских и иностранных субъектов внешнеторговой деятельности Субъектами внешнеторговой деятельности являются российские юридические лица, а также физические лица, имеющие постоянное или преимущественное местожительство на территори...
5148. Внешнеторговый договор купли-продажи 44.35 KB
  Внешнеторговый договор купли-продажи Внешнеторговый договор(контракт) - это вид хозяйственной сделки, т.е. соглашение экономических агентов, один из которых не является резидентом Российской Федерации либо, являясь резидентом РФ, имеет за рубе...
5149. Особенности разрешения внешнеэкономических споров 22.37 KB
  Понятие арбитражного суда в международном частном праве отличается от применяемого в российском законодательстве. Под третейским (арбитражным) судом мировая практика понимает суд, избранный сторонами для разрешения спора между ними. Состав суда определяется сторонами.
5150. Страна на берегах Нила и ее жители 79.5 KB
  Страна на берегах Нила и ее жители 1. Нил - река жизни. Пять с половиной тысяч лет тому назад в Африке в нижнем течении реки Нил зародилась цивилизация Древнего Египта, ровесница Древнего Шумера. Река Нил берет начало в Центральной Африке и течет на...
5151. Общая характеристика методов проектирования систем и типовые модели анализа и синтеза 114.5 KB
  Основные положения проектирования сложных систем. Проектирование имеет целью обеспечить эффективное функционирование и взаимодействие системы в среде её практической деятельности. Именно качественное проектирование обеспечивает создание такой сис...
5152. Регулирование деятельности в области воздушных перевозок 59.5 KB
  Регулирование деятельности в области воздушных перевозок Регулированием является выдача официального указания по созданию и поддержания желаемой степени порядка. Всякое регулирование включает процесс регулирования, различные виды деятельности людей...