"Довга" арифметика » Українські реферати
Теми рефератів
Авіація та космонавтика Банківська справа Безпека життєдіяльності Біографії Біологія Біологія і хімія Біржова справа Ботаніка та сільське гос-во Бухгалтерський облік і аудит Військова кафедра Географія
Геодезія Геологія Держава та право Журналістика Видавнича справа та поліграфія Іноземна мова Інформатика Інформатика, програмування Історія Історія техніки Комунікації і зв'язок Краєзнавство та етнографія Короткий зміст творів Кулінарія Культура та мистецтво Культурологія Зарубіжна література Російська мова Маркетинг Математика Медицина, здоров'я Медичні науки Міжнародні відносини Менеджмент Москвоведение Музика Податки, оподаткування Наука і техніка Решта реферати Педагогіка Політологія Право Право, юриспруденція Промисловість, виробництво Психологія Педагогіка Радіоелектроніка Реклама Релігія і міфологія Сексологія Соціологія Будівництво Митна система Технологія Транспорт Фізика Фізкультура і спорт Філософія Фінансові науки Хімія Екологія Економіка Економіко-математичне моделювання Етика Юриспруденція Мовознавство Мовознавство, філологія Контакти
Українські реферати та твори » Информатика, программирование » "Довга" арифметика

Реферат "Довга" арифметика

"Довга" арифметика

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

30! = 265252859812191058636308480000000?

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

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

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

Існують й інші уявлення "довгих" чисел. Розглянемо одне з них. Уявімо наше число

30! = 265252859812191058636308480000000

в вигляді:

30! = 2 * (104) 8 + 6525 * (104) 7 + 2859 * (104) + 8121 * (104) 5 + 9105 * (104) 4 + 8636 * (104) 3 + 3084 * (104) 2 + 8000 * (104) 1 + 0000 * (104) 0. </p>

Це уявлення наштовхує на думку про масиві, представленому в табл. 1.

Таблиця 1

Номер елемента в масиві А 0 1 2 3 4 5 6 7 8 9 Значення 9 0 8000 3084 8636 9105 8121 2859 6525 2

Ми можемо вважати, що наше "довге" число представлено в 10000-10 системі числення (десятитисячних-десяткова система числення, приведіть аналогію з вісімкова-десятковою системою числення), а "цифрами" числа є чотиризначні числа.

Виникають питання. Що за 9 в А [0], чому число зберігається "задом наперед"? Відповіді очевидні, але почекаємо з передчасними поясненнями. Відповіді на запитання будуть зрозумілі з тексту.

Примітка. Ми працюємо з позитивними числами!

Перша задача. Ввести "довге" число з файлу. Рішення задачі почнемо з опису даних.

Const MaxDig = 1000; {Максимальна кількість цифр - чотиризначних!}

Osn = 10000; {Підстава нашої системи числення,

в елементах масиву зберігаємо чотиризначні числа}

Type Tlong = Array [0 .. MaxDig] Of Integer;

{Максимальне кількість десяткових цифр у нашому числі}

Алгоритм введення "довгого" числа з файлу розглянемо на конкретному прикладі.

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

Таблиця 2

А [0] А [1] А [2] А [3] Ch Примітка 3 674 851 23 - Кінцеве стан 0 0 0 0 2 Початкове стан 1 2 0 0 3 1-й крок 1 23 0 0 8 2-й крок 1 238 0 0 5 третій крок 2 385 2 0 1 4-й крок: старша цифра елемента А [1] перейшла в поки "порожній" елемент А [2] 2 851 23 0 6 5-й крок 2 516 238 0 7 6-й крок 3 167 385 2 4 7-й крок 3 674 851 23

Проаналізуємо таблицю (і отримаємо відповіді на поставлені вище питання).

1. В А [0] зберігаємо кількість задіяних (ненульових) елементів масиву А - це вже очевидно.

2. При обробці кожної чергової цифри вхідного числа старша цифра елемента масиву з номером i стає молодшою ​​цифрою числа в елементі i +1, а запроваджувана цифра буде молодшою ​​цифрою числа з А [1]. В результаті роботи нашого алгоритму ми отримали число, записане "задом наперед".

Примітка (Методичний): Можна обмежитися цим поясненням і розробку процедури винести на самостійне завдання. Можна продовжити пояснення. Наприклад, виписати фрагмент тексту процедури перенесення старшої цифри з A [i] в ​​молодшу цифру А [i +1], тобто зсув вже введеної частини числа на одну позицію вправо:

For i: = A [0] DownTo 1 Do

Begin

A [i + l]: = A [i + l] + (Longint (A [i]) * 10) Div Osn;

A [i]: = (LongInt (A [i]) * 10) Mod Osn;

End;

Нехай ми вводимо число 23851674 і перші 6 цифр вже розмістили "задом наперед "в масиві А. У символьну змінну вважали чергову цифру "Довгого" числа - це "7". На нашу алгоритмом ця цифра "7" повинна бути розміщена молодшої цифрою в А [1]. Виписаний фрагмент програми "звільняє" місце для цієї цифри. У таблиці відбиті результати роботи цього фрагмента.

i А [1] А [2] А [3] ch 2 516 238 0 7 2 516 380 2 1 160 385 2

Після цього залишається тільки додати поточну (зчитану в ch) цифру "довгого" числа до А [1] і змінити значення А [0].

В Зрештою процедура повинна мати наступний вигляд:

Procedure ReadLong (Var A: Tlong);

Var ch: char; i: Integer;

Begin

FillChar (A, SizeOf (A), 0);

Read (ch);

While Not (ch In ['0 '.. '9']) Do Read (ch);

{пропуск не цифр у вхідному файлі}

While ch In ['0 '.. '9'] Do

Begin

For i: = A [0] DownTo 1 Do

Begin

{"протягування" старшої цифри в числі з A [i]

в молодшу цифру числа з A [i + l]}

A [i + l]: = A [i + l] + (LongInt (A [i]) * 10) Div Osn;

A [i]: = (LongInt (A [i]) * 10) Mod Osn

End;

A [1]: = A [l] + Ord (ch) - Ord ('0 ');

{додаємо молодшу цифру до числа з А [1]}

If A [A [0] +1]> 0 Then Inc (A [0]);

{змінюємо довжину, число задіяних елементів масиву А}

Read (ch)

End

End;

Друга задача. Висновок "довгого" числа в файл або на екран.

Здавалося б, немає проблем - виводь число за числом. Однак у силу обраного нами представлення "довгого" числа ми повинні завжди пам'ятати, що в кожному елементі масиву зберігається не послідовність цифр "довгого" числа, а значення числа, записаного цими цифрами. Нехай в елементах масиву зберігаються чотиризначні числа. Тоді "довге" число 128400583274 буде в масиві А представлено наступним чином:

A [0] A [1] A [2] A [3] ...


Страница 1 из 3Следующая страница

Друкувати реферат
Замовити реферат
Замовлення реферату
Реклама

Наверх Зворотнiй зв'язок