Презентація ,до модуля:"Математичні основи інформатики", на тему: "Цілочисельна арифметика в обмеженому числі розрядів"

Цілочисельна арифметика в обмеженому числі розрядів. Підготувала: вчитель інформатики Бойко Оксана Іллівна

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

Арифметичні дії Нам необхідно виконати арифметичні дії над дуже великими числами, наприклад30! = 265252859812191058636308480000000  У таких випадках ми самі повинні потурбуватися про представлення чисел в машині і про точне виконання арифметичних операцій над ними. Числа, для представлення яких в стандартних комп'ютерних типах даних не вистачає кількості двійкових розрядів, називаються "довгими".

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

Арифметичні операції Якщо ми реалізовуватимемо арифметичні операції над цим числом, то розмір масиву має бути достатнім, аби розмістити в ньому і результат, наприклад, множення. Існують і інші представлення "довгих" чисел. Розглянемо одне з них. Представимо наше число 30! = 265252859812191058636308480000000 у вигляді:30! =2• (104)8+6525• (104)7+2859• (104) 6+ 8121• (104)5 + 9105• (104)4+ 8636• (104)3 + 3084• (104)2 + 8000• (104)1 + 0000• (104)0.

Даний запис наштовхує на думку про масив, представлений в таблиці. {08 FB837 D-C827-4 EFA-A057-4 D05807 E0 F7 C}Номер елементу в масиві А0123456789 Значення9080003084863691058121285965252

Множення довгого числа на коротке. Виконується множення "в стовпчик" на одноцифрове число. Дана операція може бути корисна для виконання простих операцій, таких як множення на 2 або використана при діленні довгого числа на довге. Різниця між множенням на коротке число і множенням на довге полягає в тому, що при множенні на коротке число нам не потрібно множити розряди довгого числа на відповідні розряди короткого числа.

Наприклад. Ввести "довге" число. Рішення задачі почнемо з опису даних. Const Max. Dig=1000;{Максимальна кількість цифр — чотиризначних!}Osn=10000;{Основа нашої системи числення, в елементах масиву зберігаємо чотиризначні числа} Type Tlong=Array[0.. Max. Dig] Of Integer;Ми можемо вважати, що наше "довге" число представлене в 10000—10 системі числення (десятитисячно-десяткова система числення, а "цифрами" числа є чотиризначні числа.

Алгоритм введення "довгого" числа з файлу розглянемо на конкретному прикладі. Нехай  в файлі записано число 23851674 і основою системи (Osn) є 1000 (зберігаємо по три цифри в элементі таблиці А). Зміна значень елементів таблиці А в процесі введення (посимвольного в змінну ch) відображено в таблиці

Якщо виводите масив, де в кожній комірці знаходиться по декілька цифр - можливі проблеми з виведенням ведучих нулів. Якщо нам потрібно вивести, наприклад, число 12030002, і в кожній комірці знаходтться по 4 цифри, то ми отримуємо масив з двох комірок, T[1]=2, та T[2]=1203. Під час виведення за допомогою функції, наведеної вище, ми отримаємо 12032. Ми втрачаємо три розряди, значення яких дорівнюють 0.

В такому випадку необхідно застосувати форматований вивід. Для цього скористаємось двома флагами форматованого виведення: Додавання цілих довгих чисел. Процес додавання довгих чисел – це реалізація додавання чисел "в стовпчик". Перше число – масив T1, друге число – масив T2, результат – T3. Наприклад:

Програма додавання двох "довгих" додатніх чисел.  Назвемо процедуру додавання Sum. Long. Two. Тоді програма введення двох "довгих" чисел і виведення результату їх складання матиме такий вигляд: Var A,B,C: Tlong;Begin  Assign(Input,'Input.txt'); Reset(Input) ;  Read. Long(A);Read. Long(B) ;  Close (Input) ;  Sum. Long. Two(A,B,C);]  Assign(Output,'Output.txt') ;  Rewrite(Output);  Write. Long(C) ;  Close(Output) ;End.

Алгоритм процедури Алгоритм процедури додавання можна пояснити на простому  прикладі. Нехай А = 870613029451,В = 3475912100517461{3 C2 FFA5 D-87 B4-456 A-9821-1 D502468 CF0 F}i. A[i]B[i]С[1]С[2]С[3]С[4]19451746169121002130251691213540  38706912169121354782714034756912135478273476

Порівняння довгих чисел. Функція порівняння довгих чисел повертає 0 – коли числа рівні, 1 - коли перше число більше за друге і -1 - коли друге число більше першого. Під час реалізації спершу порівнюється кількість цифр. Якщо кількість цифр різна, то у більшого числа більше кількість цифр. Якщо ж кількість цифр однакова, то порівнюють всі цифри по порядку, починаючи зі старшого розряду. Даний алгоритм буде працювати правильно і у випадку коли в одній комірці пам’яті масиву будемо зберігати декілька цифр.

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