Зверніть увагу на те, що для отримання результату додаван ня використовується масив а. Це робиться з метою економи пам'яті комп'ютера і тому, що після обробки поточна цифра масиву а вже надалі не потрібна.
Для використання цієї процедури в основній програмі треба зробити такий опис власних типів:
type mas = array[1..1000] of byte;
І ще одна пропозиція: для того щоб користувачу не доводи лося вводити цифри масивів окремо по одній, можна організу вати імітацію цього введення, як звичайного числа:
procedure input(var х: mas; var k: word); var i: word;
err: integer; begin
for і := k downto 1 do begin
ch := ReadKey; write(ch); val(ch, x[i], err);
end;
writeln;
end;
Звернемо увагу на те, що у запропонованому алгоритмі та відповідній процедурі розглядалося додавання чисел по одній цифрі з описом змінних, що зберігають їх значення, типом byte. Однак це неекономне використання даного типу, оскіль ки максимальне значення цього типу 255. Природно виникає запитання: чи не можна під час додавання обробляти одночас но двоцифрові числа?
Розглянемо приклад: 1234 + 5642 = 6876.
Розіб'ємо обидва числа таким чином: 1234 = 1200 + 34, 5642 = = 5600 + 42. Зрозуміло, що відповідь від цього не зміниться, але додавання тепер може відбуватися так: (1200 4- 5600) + (34 + + 42). Отже, можна вдосконалити алгоритм, розбиваючи за дані числа, тобто елементи масивів, на групи по дві цифри, і ви конувати їх додавання. При цьому отриманий результат розділяємо на такі дві частини: перша - останні дві цифри, дру га - кількість сотень. Перша - це і буде результат додавання поточних двох розрядів, а друга - інформація, що запам'ято вується для додавання наступних двох розрядів. А чи не вийде мо під час додавання двоцифрових чисел за межі типу byte? Найбільші числа, які ми можемо додавати, це 99, а їхня сума дорівнює 198. Отже, усе залишиться в межах обраного типу.
Логічними є наступні міркування: а чому не тип word? Справ ді, користуючись таким типом, можна розбивати задані числа на групи по 4 цифри, починаючи з найменшої цифри. При цьо-
6
му додавання максимально можливих чотирицифрових чисел (9999 + 9999 = 19 998) не вийде за межі даного типу (65 535). Якщо взяти тип longint, то можна розбивати числа на групи по 9 цифр, оскільки максимальним значенням цього типу є десятицифрове число 2 147 483 647. Перевірка додавання двох максимальних за значенням дев'ятицифрових чисел 999 999 999 + 999 999 999 = 1 999 999 998 указує, що ми не виходимо за межі обраного типу.
Що дає розбиття заданих чисел на групи, більші за кількіс тю цифр? Аргументи не потребують доведення:
-значно зменшується кількість циклів під час додавання чисел;
-використовуються готові алгоритми для додавання двох цілих чисел.
Модифікована процедура введення вхідних даних з вико ристанням типу word виглядатиме так:
procedure input(var х: mas; var k: word); var і, j, L: word;
err: integer; begin
k := k div 4; L := k m o d 4; |
{Визначення кількості k повних і L неповних груп.} |
|||
if L О 0 |
|
|
|
{Якщо є неповна група, то вводяться її цифри.} |
t h e n |
|
|
|
|
b e g i n |
|
|
|
|
inc(k); |
st |
:= |
"; |
|
f o r i := |
1 |
to |
L do |
|
b e g i n |
|
|
|
|
ch := R e a d K e y ; w r i t e ( c h ) ; |
||||
st := st + ch; |
|
|||
e n d ; |
|
|
|
|
val(st, x [ k ] , err); |
|
|||
d e c ( k ) |
|
|
|
|
e n d ; |
|
|
|
|
f o r І := 1 to k do |
|
{Вводяться повні групи цифр.} |
||
b e g i n |
|
|
|
|
s t : = " ; |
|
|
|
|
f o r j :- 1 to 4 do |
{Посимвольно вводяться цифри поточної групи.} |
|||
b e g i n |
|
|
|
|
ch := R e a d K e y ; w r i t e ( c h ) ; |
||||
st := St + Ch; |
{Накопичення цифр поточної групи.} |
|||
end; |
|
|
|
|
val(st, x[i], err); |
{Переведення у числовий вигляд.} |
|||
end; |
|
|
|
|
if L <> 0 t h e n inc(k); |
{Якщо існує старша неповна група, то кількість груп} |
|||
|
|
|
|
{збільшується на 1.} |
w r i t e l n ; e n d ;
7
Модифікований варіант процедури додавання з використан ням типу word може бути таким:
procedure add(var a, b: mas; var k: word); var i: word;
begin
if n > m then k := n else k := m; c:=0;
for і := 1 to k do begin
c:=a[i] + b[i] + c;
a[i] := C m o d 10000; |
{Виділення результуючої групи цифр.} |
|
С := С div 10000 |
{Виділення цифри, що виходить за розрядність групи.} |
|
e n d ; |
|
|
if с <> 0 t h e n b e g i n inc(k); a[k] |
:= c e n d ; |
|
e n d ;
Звернемо увагу також і на той момент, що, як і для варіанту обробки довгих чисел окремими цифрами, для отримання ре зультату додавання двох довгих чисел розбиттям на групи не використовується ще один результуючий масив. Для економії пам'яті комп'ютера можна використовувати вже оброблені еле менти масиву а.
Виведення результату можна виконати за допомогою такого фрагмента програми:
w r i t e ( a [ k ] ) ; |
{Виведення першої групи цифр.} |
f o r і := k - 1 d o w n t o 1 do |
|
b e g i n |
|
Str(a[i], St); |
{Представлення м групи цифр у вигляді рядка.} |
f o r j := 1 to 4 - length(st) do |
{Виведення на початку ;'-ї групи цифр} |
write('O'); |
{необхідної кількості нулів.} |
w r i t e ( a [ i ] ) ; |
{Виведення /-Ї групи цифр.} |
e n d ; |
|
Процес тестування складених алгоритмів необхідно поча ти з додавання «зручних» чисел, сума цифр відповідних роз рядів яких не перевищує 9, а самі цифри коливаються в межах від 1 до 8. Наступним кроком тестування може бути перевірка додавання чисел, серед цифр яких є 0, однак сума цифр відповідних розрядів не перевищує 9. Складнішою перевіркою має бути додавання чисел, сума цифр яких перевищує 9, але цифрами наступних старших розрядів обох чисел є 0.1 останньою перевіркою може стати тест для двох чисел, сума цифр яких пе ревищує 9.
Усі ці тести необхідно застосувати до алгоритмів додавання з однаковою розрядністю доданків, різною розрядністю до данків та з різним описом вхідних даних.
8
Завдання
1.Розробити діалогову меню-орієнтовану програму додавання цілих додатних чисел, використовуючи тип byte, і протесту вати її за такими критеріями:
-обидва числа однакової розрядності, що кратна числу 2, та сума яких має таку саму розрядність;
-обидва числа однакової розряд ності, що кратна числу 2, та сума яких має більшу розряд ність;
-розрядність першого числа більша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 2;
-розрядність першого числа більша від розрядності другого, але при цьому розрядність одного з них не кратна числу 2;
-розрядність першого числа менша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 2;
-розрядність першого числа менша від розрядності другого, але при цьому розрядність одного з них не кратна числу 2.
2.Розробити діалогову меню-орієнтовану програму додавання цілих додатних чисел, використовуючи тип word:
-обидва числа однакової розрядності, що кратна числу 4, та сума яких має таку саму розрядність;
-обидва числа однакової розрядності, що кратна числу 4, та сума яких має більшу розрядність;
-розрядність першого числа більша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 4;
-розрядність першого числа більша від розрядності другого, але при цьому розрядність одного з них не кратна числу 4;
-розрядність першого числа менша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 4;
-розрядність першого числа менша від розрядності другого, але при цьому розрядність одного з них не кратна числу 4.
3.Розробити діалогову меню-орієнтовану програму додавання цілих додатних чисел, використовуючи тип longint:
-обидва числа однакової розрядності, що кратна числу 9, та сума яких має таку саму розрядність;
-обидва числа однакової розрядності, що кратна числу 9, та сума яких має більшу розрядність;
-розрядність першого числа більша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 9;
-розрядність першого числа більша від розрядності другого, але при цьому розрядність одного з них не кратна числу 9;
-розрядність першого числа менша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 9;
-розрядність першого числа менша від розрядності другого, але при цьому розрядність одного з них не кратна числу 9.
4.Виконати завдання 1-3 для вхідних даних довжиною 32 000 цифр, згенерованих випадковим чином, що вводяться із файлу.
5.Зробити письмовий аналіз виконання завдань 1-4.
9
z |
|
Запитання для самоконтролю |
1. Які алгоритми називають алгоритмами роботи з довгими чис |
||
|
|
лами? |
|
2. |
У чому полягає необхідність створення цих алгоритмів? Обґрун |
|
|
туйте свою відповідь. |
|
3. |
Яким чином представляються числа в алгоритмах довгої ариф |
|
|
метики? |
|
4. |
Опишіть алгоритм додавання цілих чисел. |
|
5. |
Представте алгоритм додавання цілих довгих чисел у вигляді |
|
|
процедури мовою Pascal. |
|
6. |
Яким чином краще організувати введення початкових даних для |
|
|
алгоритму додавання цілих довгих чисел? |
|
7. |
Яким чином можна модифікувати процедуру додавання цілих |
|
|
довгих чисел? |
|
8. |
У чому полягають переваги розбиття цифр довгих чисел на гру |
|
|
пи, в яких більше однієї цифри у кожній? |
|
9. |
Яку роль у раціональному розбитті цифр довгих чисел на групи |
|
|
відіграють стандартні типи змінних, що описують цілі числа у |
|
|
Pascal? |
10. Запишіть модифікований варіант процедури введення почат кових даних у разі використання типу word для зберігання груп цифр доданків.
11. Запишіть модифікований варіант процедури додавання двох довгих цілих чисел у разі використання типу word для зберіган ня груп цифр цих чисел.
Віднімання довгих цілих чисел
Алгоритм віднімання довгих чисел так само, як і додавання, базується на алгоритмі виконання цієї дії над двома числами у стовпчик.
Домовимося розглядати випадок, коли зменшуване не пере вищуватиме від'ємник. Інакше необхідно спочатку задані числа поміняти місцями, а обчислений результат виводити зі знаком «-». Саме тому в наведеному далі алгоритмі перевірка необхідності обміну початкових даних відсутня.
Розглянемо спочатку випадок, коли дії віднімання викону ються над окремими цифрами заданих чисел. Нагадаємо сам алгоритм, який нам відомий з початкової школи.
1.Нехай п - кількість цифр у зменшуваному, а т - у від'ємнику. Для обчислення результату віднімання визначимо кількість переглядів елементів масивів я.
2.Визначити і := 1, с := 0 (с - ознака позичення 1 у наступ ному розряді).
3.Нехай at - t-та цифра зменшуваного, bt - від'ємника, a rezl - результату.
4.Якщо аі > 0 і с = 1, тобто з цього розряду у попередньому відніманні позичена 1, то зменшити аі на 1, ознаку позики 1
10