вівторок, 2 червня 2020 р.

Система числення

Сукупність прийомів та правил найменування й позначення чисел називається системою числення.
 Звичайною для нас і загальноприйнятою є позиційна десяткова система числення. Як умовні знаки для запису чисел вживаються цифри.
Система числення, в якій значення кожної цифри в довільному місці послідовності цифр, яка означає запис числа, не змінюється, називається непозиційною. Система числення, в якій значення кожної цифри залежить від місця в послідовності цифр у записі числа, називається позиційною.
Щоб визначити число, недостатньо знати тип і алфавіт системи числення. Для цього необхідно ще додати правила, які дають змогу за значеннями цифр встановити значення числа.
Найпростішим способом запису натурального числа є зображення його за допомогою відповідної кількості паличок або рисочок. Таким способом можна користуватися для невеликих чисел.
Наступним кроком було винайдення спеціальних символів (цифр). У непозиційній системі кожен знак у запису незалежно від місця означає одне й те саме число. Добре відомим прикладом непозиційної системи числення є римська система, в якій роль цифр відіграють букви алфавіту: І - один, V - п'ять, Х - десять, С - сто, Z - п'ятдесят, D -п'ятсот, М - тисяча. Наприклад, 324 = СССХХІV. У непозиційній системі числення незручно й складно виконувати арифметичні операції.
Загальновживана форма запису числа є насправді не що інше, як скорочена форма запису розкладу за степенями основи системи числення, наприклад
130678=1*105+3*104+0*103+6*102+7*101+8
Тут 10 є основою системи числення, а показник степеня - це номер позиції цифри в записі числа (нумерація ведеться зліва на право, починаючи з нуля). Арифметичні операції у цій системі виконують за правилами, запропонованими ще в середньовіччі. Наприклад, додаючи два багатозначних числа, застосовуємо правило додавання стовпчиком. При цьому все зводиться до додавання однозначних чисел, для яких необхідним є знання таблиці додавання.
Проблема вибору системи числення для подання чисел у пам'яті комп'ютера має велике практичне значення. В разі її вибору звичайно враховуються такі вимоги, як надійність подання чисел при використанні фізичних елементів, економічність (використання таких систем числення, в яких кількість елементів для подання чисел із деякого діапазону була б мінімальною). Для зображення цілих чисел від 1 до 999 у десятковій системі достатньо трьох розрядів, тобто трьох елементів. Оскільки кожен елемент може перебувати в десятьох станах, то загальна кількість станів - 30, у двійковій системі числення 99910=1111100, необхідна кількість станів - 20 (індекс знизу зображення числа - основа системи числення). У такому розумінні є ще більш економічна позиційна система числення - трійкова. Так, для запису цілих чисел від 1 до у десятковій системі числення потрібно 90 станів, у двійковій - 60, у трійковій - 57. Але трійкова система числення не дістала поширення внаслідок труднощів фізичної реалізації.
Cпосіб переходу від 
двійкової системи числення 
до десяткової системи числення:

(100011111)2=
=1*28+1*27+0*26+0*25+1*24+1*23+1*22+1*21+1*20=
=256+128+0+0+16 +8+4+2+1=(415)10.
Тому найпоширенішою для подання чисел у пам'яті комп'ютера є двійкова система числення. Для зображення чисел у цій системі необхідно дві цифри: 0 і 1, тобто достатньо двох стійких станів фізичних елементів. Ця система є близькою до оптимальної за економічністю, і крім того, таблички додавання й множення в цій системі елементарні:
+
0
1

*
0
1
0
0
1

0
0
0
1
1
10

1
0
1

Оскільки 23=8, а 24=16 , то кожних три двійкових розряди зображення числа утворюють один вісімковий, а кожних чотири двійкових розряди - один шістнадцятковий. Тому для скорочення запису адрес та вмісту оперативної пам'яті комп'ютера використовують шістнадцяткову й вісімкову системи числення. Нижче в таблиці 1 наведені перших 16 натуральних чисел записаних в десятковій, двійковій, вісімковій та шістнадцятковій системах числення.
Таблиця 1
10
2
8
16
0
0000
0
0
1
0001
1
1
2
0010
2
2
3
0011
3
3
4
0100
4
4
5
0101
5
5
6
0110
6
6
7
0111
7
7
8
1000
10
8
9
1001
11
9
10
1010
12
A
11
1011
13
B
12
1100
14
C
13
1101
15
D
14
1110
16
E
15
1111
17
F

Приклад 1 . Системи числення з основою‚ кратною 2:
а) вісімкове число 273‚54 переводиться у двійкову систему (8 = 23 ) так:
273‚548 = (010)(111)(011)‚(101)(100)=10111011‚10112 ;
б) двійкове число 11011‚0011 переводиться у вісімкову систему числення так:
1011‚00112 = 11(011)‚(001)1 = (011)(011)‚(001)(100) = 33‚148 ;
в) шістнадцяткове число A5,B1E переводиться в двійкову систему числення (16 = 24 ) так:

A5,B1E16 = (1010)(0101),(1011)(0001)(1110) = 10100101,101100011112
В процесі налагодження програм та в деяких інших ситуаціях у програмуванні актуальною є проблема переведення чисел з однієї позиційної системи числення в іншу. Якщо основа нової системи числення дорівнює деякому степеню старої системи числення, то алгоритм переводу дуже простий: потрібно згрупувати справа наліво розряди в кількості, що дорівнює показнику степеня і замінити цю групу розрядів відповідним символом нової системи числення. Цим алгоритмом зручно користуватися коли потрібно перевести число з двійкової системи числення у вісімкову або шістнадцяткову. Наприклад, 101102=10 110=268, 10111002=1011100=5C8
у двійковому відбувається за зворотнім правилом: один символ старої системи числення заміняється групою розрядів нової системи числення, в кількості рівній показнику степеня нової системи числення. Наприклад, 4728=100 111 010=1001110102, B516=10110101=101101012
Як бачимо, якщо основа однієї системи числення дорівнює деякому степеню іншої, то перевід тривіальний. У протилежному випадкові користуються правилами переведення числа з однієї позиційної системи числення в іншу (найчастіше для переведення із двійкової, вісімкової та шістнадцяткової систем числення у десяткову, і навпаки).
1. Для переведення чисел із системи числення з основою p в систему числення з основою q, використовуючи арифметику нової системи числення з основою q, потрібно записати коефіцієнти розкладу, основи степенів і показники степенів у системі з основою q і виконати всі дії в цій самій системі. Очевидно, що це правило зручне при переведенні до десяткової системи числення.
Наприклад:
з вісімкової в десяткову:
7358=7*1082+3*1081+5*1080= 7*8102+3*8101+5*8100=47710
з двійкової в десяткову:
1101001012=1*1028+1*1027+ 0*1026+1*1025+0*1024+0*1023+ 1*1022+0*1021+1*1020= 1*2108+1*2107+0*2106+1*2105+ 0*2104+0*2103+1*2102+0*2101+ 1*2100=42110
2. Для переведення чисел із системи числення з основою p в систему числення з основою q з використанням арифметики старої системи числення з основою p потрібно:
  • для переведення цілої частини:
    • послідовно число, записане в системі основою p ділити на основу нової системи числення, виділяючи остачі. Останні записані у зворотному порядку, будуть утворювати число в новій системі числення;
  • для переведення дробової частини:
    • послідовно дробову частину множити на основу нової системи числення, виділяючи цілі частини, які й будуть утворювати запис дробової частини числа в новій системі числення.
Цим самим правилом зручно користуватися в разі переведення з десяткової системи числення, тому що її арифметика для нас звичніша.
Приклади: 999,3510=1111100111,010112

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

для дробової частини:


Перевід дробової частини. Число q записують в p -мі системі числення. Дріб множимо в p -вій системі на q . Ціла частина добутку дорівнює першій цифрі запису числа. Дробову частину добутку знову множимо на q . Ціла частина добутку дорівнює наступній цифрі запису числа в системі числення з основою q . Процес продовжують до тих пір поки не отримаємо добуток у вигляді цілого числа або не отримаємо потрібної кількості цифр шуканого дробу.
Переведення чисел ( z)#р→( y)#10

 Відомо, що (125)#10=(7D)#16.
Як же здійснювати перехід з певної системи числення в десяткову і навпаки?
 Для цього необхідно абстрагувати систему числення, яка відмінна від десяткової, тобто подати її в узагальненому вигляді. Такою узагальненою системою є система числення з основою р. Алфавіт такої системи: 0, 1, …, р-1.
Наприклад, основа п’ятіркової системи числення – р=5.
Алфавіт цієї системи: 0, 1, … 5-1, тобто: 0, 1, 2, 3, 4.
Перехід числа з системи з основою числення р в десяткову здійснюється за такою формулою:
( а а а … аaа)#р = (а*р^k + а*р^k-1 + а*р^k-2 + … + a*p^2 + a*p^1 + a*p^0)#10
Раніше ми записали, що (144)#8=(100)#10.
Давайте перевіримо:
(144)#8 = 1*8^2 + 4*8^1 + 4*8^0 = 1*64 + 4*8 + 4*1 = 64+32+4 = (100)#10
Отже, для того, щоб перевести ціле число з системи, що має основу р, в десяткову систему числення, потрібно: 1. Проставити під цифрами даного числа справа наліво номер позиції починаючи з 0. 2. а) цифру найстаршого розряду числа з основою р (нехай це а) записати після знаку дорівнює; б) поставити знак множення; в) записати р; г) над числом р поставити степінь – номер позиції записаної цифри а; д) поставити знак плюс. 3. Виконати пункт 2 для цифри молодшого розряду. 4. Виконувати пункт 2, аж поки не дійдемо до цифри, позиція якої 0. 5. Виконати обчислення, записати число, поставити основу 10.
Задача. Перевести п’ятіркове число (2413)#5 в десяткове.
Розв’язання. (2413)#5=2*5^3+4*5^2+1*5^1+3*5^0=250+100+8=(358)#10
 Задача. Перевести шістнадцяткове число (7D)#16 в десяткове.
Розв’язання. (7D)#16=7*16^1+13*16^0=11^2+13=(125)#10

Завдання для самостійного опрацювання.
Здійснити перехід від однієї системи
числення до іншої системи числення:

1)(1022)3®(…)10
2)(2013)4®(…)10
3)(23041)5®(…)10
4)(2А)16®(…)10
5)(110010)2®(…)10
6)(15)6®(…)10
7)(29)10®(…)2
8) (38)10®(…)4
9)(401)10®(…)3
10) (267)10®(…)5

Задача Per_10_2
   Перевести натуральне число N із 10-ової в 2-ову систему числення.
  Технічні умови. Програма зчитує з клавіатури натуральне число N (N<=103). Програма виводить на екран шукане натуральне число - запис у 2-овій системі числення.
  Приклад
          Введення:   5     
          Виведення:  101

Задача  Per_10_a
   Перевести натуральне число N із 10-ової у систему числення за основою а (2<= a <10).
  Технічні умови. Програма зчитує з клавіатури натуральні числа N (N<=109) і а (2<= a <10). Програма виводить на екран шукане натуральне число - запис у а-овій системі числення.
  Приклад
          Введення:   54  7    
          Виведення:  105

Двійкова система числення. Десяткова система числення.

Задача N2_N10. Переведіть  натуральне число із двійкової системи числення в десяткову систему числення, використовуючи мову Pascal.
Технічні умови.  З клавіатури вводяться  числа із двійкової системи числення, використовуючи цілий тип даних longint. На виході  отримуємо це ж число, що записане у десятковій системі числення.
Приклад.  А)Введення:112, виведення:310;Б) Введення:10102, виведення:1010;  В)Введення:11112, виведення:1510; Г) Введення:100002 , виведення:1610. 
Розв’язання.Кодування мовою програмування Pascal: 
program n2_n10;
var  n10, n2,  ost, k : longint;
begin
write( ‘Введіть натуральне число в двійковій системі  із цифр  1 та  0,   n2=: ');
 read(n2); k:=1;  n10:=0;  while n2 > 0 do
begin
ost:= n2 mod 10;   if  ost=1 then  n10:= ost*k+n10;
n2:= n2 div 10;   k:= k*2; end;
writeln('  Число в десятковій  системі  має запис  n10 = ', n10);
end.
Задача N10_N2. Переведіть  натуральне число із десяткової  системи числення в двійкову систему числення , використовуючи мову Pascal.
Технічні умови.  З клавіатури вводяться  числа в десятковій системи числення, використовуючи цілий тип даних longint. На виході  отримуємо це ж число, що записане у двійковій системі числення.
Приклад.  А)Введення:310, виведення:112; Б)Введення:1010, виведення:10102; 
В)Введення:1510, виведення:11112; Г) Введення:1610,  виведення:100002. 
Розв’язання. Кодування мовою програмування Pascal: 
program n10_n2;
var a, b, n10, n2,  ost, k : longint;
begin
write( ‘Введіть натуральне число в десятковій  системі  числення  із цифр:  1,2,3,4,5,6,7,8,9,0,  n10=  ');
 read (n10);   k:=1; n2:=0;    while n10 > 0 do
begin
        ost:= n10 mod 2;   n10:= n10 div 2;  n2:= ost*k+n2;
        k:= k*10; 
end;
         writeln('   Число в двійковій  системі числення  має запис  n2 = ',n2);
         end.
Контрольні запитання.
1.    Наведіть синтаксис запису циклів з лічильником мовою Pascal?
2.    Наведіть синтаксис запису циклів з передумовою мовою Pascal?
3.    Наведіть синтаксис запису циклів з післяумовою мовою Pascal?
4.    Як записуються  розгалуження мовою Pascal?
5.    Як записуються  складені логічні  умови у форматі  if … then … else..;, що об'єднують декілька простих логічних умов?
6.    Наведіть синтаксис оператора одноальтернативного  розгалуження.
7.    До яких типів даних не може належати значення виразу-селектора в операторі вибору?
8.    У чому полягає відмінність між циклами з передумовою та циклами з післяумовою?
9.    Якому типу даних може належати лічильник у циклі  for?
10.   Яке значення має лічильник після завершення циклу  for?
11.   Що може спричинити «зациклення» програми?
12.   За яких умов цикли while та for не виконаються жодного разу?
13.   Коли цикл виконується лише один раз?
14.   У чому полягає відмінність між такими операторами циклів, як  for...to...do  та for...downto...do?
15.   Яка структура працює ефективніше: вкладені оператори іf ...then...else чи серія операторів іf...then? Відповідь обґрунтуйте.
16.   Як можна пропустити деякі оператори програми, що належать тілу циклу, не видаляючи ці оператори?
17.   Як підвищити ефективність роботи вкладених структур if...then...else?
В даному розділі розглянуто набір реалізацій А.Нікітін на мові Pascal стандартних алгоритмів, застосовуваних при вирішенні завдань олімпіадного програмування.

Опубліковано о Немає коментарів:

Структура процедури мовою програмування Pascal



До цього моменту часу ми використовували з розділу описів тільки опис змінних і типів. На цьому занятті ми почнемо вивчати процедури. Структура процедури повторює структуру програми.
 Зразок структурного програмування процедури(підпрограми)

procedure  <имя процедуры> (<параметри>);
label
   <розділ опису міток>;
const
   < розділ опису констант>;
type
   < розділ опису типів даних>;
var
   < розділ опису змінних>;
 <процедури та функції >;
begin
   <основное тело процедуры>;
end;

Напишемо для прикладу просту програму з процедурою, що додає два числа.

Кодування мовою програмування Pascal;
program  pr1;
var
  a, b, c: integer;
procedure sum(x, y: integer; var z: integer);
begin
  z := x + y;
end;
begin
  write('Введіть два числа: ');
  readln(a, b);
  sum(a, b, c); {процедура викликається своїм іменем, яке ви написали після зарезервованого слова procedure в описі}
  writeln(c);
end.


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

При описуванні процедури вказується список формальних параметрів. Кожен параметр є локальним по відношенню до описуваної процедури, до нього можна звертатися тільки в межах даної процедури (в нашому прикладі х, у, z - формальні параметри). Фактичні параметри - це параметри, які передаються процедурі при зверненні до неї (а, b, с - фактичні параметри). Число і тип формальних і фактичних параметрів повинні збігатися з точністю до їх слідування.
Іншими словами, передача параметрів за значенням. Копія фактичного параметра стає значенням відповідного формального параметра. Усередині процедури можна проводити будь-які дії з даними формальним параметром (допустимі для його типу), але ці зміни ніяк не відбиваються на значенні фактичного параметра, тобто яким він був до виклику процедури, то таким же і залишиться після завершення її роботи (х, у - параметри-значення).
Іншими словами, передача параметрів по посиланню. Це ті формальні параметри, перед якими стоїть ідентифікатор var. Передається адреса фактичного параметра (обов'язково змінної), після цього формальний параметр стає його синонімом. Будь-які операції з формальним параметром виконуються безпосередньо над фактичним параметром.
 Функція виглядає майже так само, як і процедура. Єдина відмінність в тому, що заголовок функції починається з ключового слова Function і закінчується типом повертаємого цією функцією значення.

Крім того, в тілі функції обов'язково повинен бути хоча б один оператор присвоювання, де в лівій частині стоїть ім'я функції або змінна result, а в правій - її значення.

Приклади кодування  допоміжної функції мовою програмування Pascal:

Program Zad1;
var
  a, b, c: integer;
function sum(x, y: integer): integer;
begin
  sum := x + y;
end;
begin
  readln(a, b);
  writeln(sum(a, b));
end.

Або так:

Program Zad2;
var
  a, b, c: integer;
function sum(x, y: integer): integer;
begin
  result := x + y;
end;
begin
  readln(a, b);
  writeln(sum(a, b));
end.



Завдання А для самостійного опрацювання
Завдання 1. Закодувати процедуру PowerA3(A, B), що обчислює третю степінь(куб) числа А і  повертає її в змінній В(А - вхідні дані; В - вихідні дані, обидва змінні є дійсними числами). За допомогою цієї процедури знайти третю степінь для шести даних чисел.
Завдання 2. Закодувати процедуру Mean(X, Y, AMean, GMean), що обчислює середнє арифметичне  AMean = (X+Y)/2 і  середнє геометричне GMean = (X * Y)^0.5 двох додатних чисел Х та У  повертає її  змінним AMean і GMean відповідно,(Х, У - вхідні дані; Amean,GMean - вихідні дані, обидва змінні є дійсними числами). За допомогою цієї процедури знайти середнє арифметичне і середнє геометричне для пари даних чисел(А;В), (А;С), (А;К), якщо дані А,В,С,К.
Завдання 3. Закодувати процедуру TrianglePS(a, P, S), що по даній стороні рівностороннього трикутника обчислює його периметр P = 3*a, площу a*a *(3)^0.5, повертає її  змінним P та S відповідно,(а - вхідні дані; P та S - вихідні дані, обидва змінні є дійсними числами). За допомогою цієї процедури знайти площу та периметр трикутників для трійки сторін(А;А;А), (С;С;С), (В;В;В), якщо дані А,В,С.
Завдання 4. Закодувати процедуру AddRightDigit(Р, K), що доповнює до цілого додатного числа К праворуч цифру Р, повертає її  змінним P та S відповідно,(К, Р (від 0 до 9)- вхідні цілі дані; К - вихідні дані, обидва змінні є цілими числами). За допомогою цієї процедури доповнити до даного числа К праворуч спочатку цифру Р1 а потім доповнити праворуч цифру Р2. Вивести результат кожного обновлення даного  числа.
Завдання 5. Закодувати процедуру AddRightDigit(Р, K), що доповнює до цілого додатного числа К ліворуч цифру Р, повертає її  змінним P та S відповідно,(К, Р (від 0 до 9)- вхідні цілі дані; К - вихідні дані, обидва змінні є цілими числами). За допомогою цієї процедури доповнити до даного числа К ліворуч спочатку цифру Р1 а потім доповнити ліворуч цифру Р2. Вивести результат кожного обновлення даного  числа.

Завдання Б для самостійного опрацювання
Func 21 °. Описати функцію SumRange (A, B) цілого типу, яка знаходить суму всіх цілих чисел від A до B включно (A і B - цілі). Якщо A> B, то функція повертає 0. З допомогою цієї функції знайти суми чисел від A до B і від B до C, якщо дано числа A, B, C. 
Func 22. Описати функцію Calc (A, B, Op) дійсного типу, що виконує над ненульовими дійсними числами A та B одну з арифметичних операцій і повертає її результат. Вид операції визначається цілим параметром Op: 1 - віднімання, 2 - множення, 3 - розподіл, інші значення - складання. За допомогою Calc виконати для даних A і B операції, які визначаються даними цілими N 1 , N 2 , N 3 . 
Func 13. Описати функцію SortDec3 (A, B, C), яка міняє вміст змінних A, B, C таким чином, щоб їх значення виявилися впорядкованими по спаданню (A, B, C - речові параметри, які є одночасно вхідними та вихідними). За допомогою цієї процедури впорядкувати по спадаючій два даних набору з трьох чисел:  
(A 1 , B 1 , C 1 ) і (A 2 , B 2 , C 2 ).
Func 15. Описати процедуру ShiftLeft3 (A, B, C), що виконує лівий циклічний зсув: значення A переходить в C, значення C - в B, значення B - в A (A, B, C - речові параметри, які є одночасно вхідними та вихідними). За допомогою цієї процедури виконати лівий циклічний зсув для двох даних наборів з трьох чисел: (A 1 , B 1 , C 1 ) і (A 2 , B 2 , C 2 ). 
Func 17. Описати функцію RootCount (A, B, C) цілого типу, яка визначає кількість коренів квадратного рівняння A · x 2 + B · x + C = 0 (A, B, C - речові параметри, A <> 0). З її допомогою знайти кількість коренів для кожного з трьох квадратних рівнянь з даними коефіцієнтами. Кількість коренів визначати за значенням дискримінанта:  D = B 2  - 4 * A * C. 
В даному розділі розглянуто набір реалізацій А.Нікітін на мові Pascal стандартних алгоритмів, застосовуваних при вирішенні завдань олімпіадного програмування.

Опубліковано о Немає коментарів:
Підписатися на: Дописи (Atom)