від наступного розряду визначити цифрою 0 (с := 0) і перейти доп. 7.
5.Якщо at = 0 і с = 1, то це означатиме, що треба позичити 1 від наступного розряду, тобто at := 10. Ознака позики 1 від на ступного розряду не змінюється, тобто с := 1.
6.Зменшити значення поточної цифри зменшуваного на значення с, тобто відняти 1, у разі, якщо у попередньому роз
ряді була зроблена позика: at := at - с. Таким чином значення at підготовлене для операції віднімання розрядів.
7.Якщо at ^ bt, тоді визначити rezt := at - bt с і перейти до
п.9.
8.Якщо аі < bt, тоді визначити значення і-го розряду числарезультату як rezi := а1 + 10 - bt, а значення ознаки позики 1 у наступному розряді визначити так: с := 1.
9.Якщо і < п, то і := і + 1 і перейти до п. 3.
10.Вивести елементи масиву rez.
Перейдемо до реалізації алгоритму мовою Pascal, адже нас насамперед цікавить виконання даного алгоритму на комп'ю тері.
Введення початкових даних для алгоритму віднімання має такий самий вигляд, як і для додавання. Тому не має сенсу на водити цю процедуру ще раз. А от процедура, що реалізує алго ритм виконання арифметичної дії віднімання у разі викорис тання довгих цілих чисел у п. 2-9, значно відрізняється від процедури додавання. Це видно з описаного вище алгоритму. Вона може виглядати так:
procedure sub(var a: mas; b: mas; var k: word);
var i: word; |
|
|
|
x: mas; |
|
|
|
begin |
|
|
|
c := 0; |
|
|
{Позик ще немає.} |
for і := 1 to П do |
|
{Обробка цифр усіх розрядів зменшуваного.} |
|
begin |
|
{Якщо поточна цифра не нуль і була позика, то} |
|
if (а[І] О 0) and (С = 1) |
{зменшення поточної цифри на 1 і зняття} |
||
then begin а[і] := а[і] - 1; с := 0 end |
{ознаки позики.} |
||
|
|
|
{Якщо поточна цифра нуль} |
else if (а[і] = 0) and (с = 1)thena[i] := 10; {і була позика, то буде 10.} |
|||
а[і] := а[І] - с; |
{Зменшення значення поточної цифри на значення позики.} |
||
if а[І] >= Ь[І] |
{Якщо поточна цифра зменшуваного не менша від поточної} |
||
then а[І] := а[І] - Ь[І] |
{цифри від'ємника, то виконання дії віднімання,} |
||
else |
|
|
|
begin |
|
{інакше спочатку збільшення поточної} |
|
І а[і] := а[і] + 10 - b[i]; с := 1 |
{цифри зменшуваного на 10.} |
||
end; |
|
|
|
end; |
|
|
|
end; |
|
|
|
11
Як бачимо, і в цьому випадку для отримання результату з метою економії пам'яті ми використали масив а.
Як вивести отриманий результат, адже внаслідок виконан ня операції віднімання може зменшитися розрядність? Для цього можна організувати таку послідовність дій:
|
|
{Пропускаємо старші цифри, що} |
while (а[п] = 0) and (п > 0) do dec(n); |
{дорівнюють о.} |
|
if П=0 |
|
{Якщо результат 0, то виведення '0'.} |
thenwrite('O') |
|
|
else |
|
|
begin |
|
|
for і := n downto 1 do |
|
|
write(a[i]); |
{Виведення результату, починаючи з ненупьової цифри.} |
|
end; |
|
|
writeln; |
|
|
Чи можна виконати віднімання, розбиваючи наші аргумен ти на групи, що містять більше однієї цифри? Спробуємо відпо вісти на це запитання за допомогою прикладу.
Розглянемо, наприклад, такі два числа 5638 і 4742. Вико наємо традиційну дію віднімання і отримаємо 5638 - 4742 = = 896. Тепер за нашим задумом розіб'ємо кожне число на групи по 2: 5638 = 5600 + 38 та 4742 = 4700 + 42. Виконаємо відніман ня: (5600 + 38) - (4700 + 42) = (5600 - 4700) + (38 - 42) = 900 + + (-4) = 896. Таким чином на довільному прикладі ми про демонстрували, що, розбивши обидва числа на групи по дві цифри, можна виконувати дію віднімання над кожною з них, як і над групами з однією цифрою. А це означає, що з мірку вань економії пам'яті та кількості виконуваних циклів можемо використати ефективніший з цієї точки зору тип word.
Реалізуємо процедуру віднімання двох цілих довгих чисел, враховуючи їх розбиття на групи по 4 цифри, починаючи з молодших розрядів, і використовуючи для цього тип word:
procedure sub(var a: mas; b: mas); var i: word;
x: mas; begin
C := 0; |
{На першому кроці позика 0.} |
for і := 1 to n do |
|
begin |
|
if (a[i]<>0)and(c= 1) |
|
then begin a[i] := a[i] - 1; c := 0 end |
|
{Якщо поточна цифра нуль і була}
else if (а[і] = 0) and (с = 1) then а[і] := 10 000; {позика, то беремо 10 000.} а[і] :=а[і]-с;
12
ifa[i] >=b[i] |
|
|
then a[i] := a[i] - b[i] |
|
|
else |
|
|
begin |
|
|
I a[i] := a['] + Ю000 - b[i]; c := 1 |
{Перед відніманням збільшення} |
|
e n d ; |
{поточної цифри зменшуваного на 10 000.} |
|
end; |
|
|
end;
Процедура введення початкових даних і запису груп цифр у тип word та сама, що і в алгоритмі додавання, а тому немає потреби її наводити.
Фрагмент програми, що реалізує виведення отриманого ре зультату, має дещо інший вигляд. Це пов'язано з тим, що у ре зультаті віднімання може зменшитися розрядність різниці по відношенню до зменшуваного, а також елементи масиву at мо жуть бути менші за 1000, що потребує доповнення їх відповід ною кількістю нулів:
w h i l e (а[п] = 0) a n d (п > 0) do d e c ( n ) ; |
{Пропуск старших нульових цифр.} |
||
if п = 0 |
|
|
|
thenwrite('O') |
|
|
|
else |
|
|
|
begin |
|
|
|
w r i t e ( a [ n ] ) ; |
{Виведення першої групи з ненульовим значенням.} |
||
for і := п - 1 downto 1 do |
|
|
|
begin |
|
|
|
Str(a[i], st); |
{Представлення поточної групи у вигляді рядка.} |
||
|
|
|
{Доповнення значення} |
for j := 1 to 4 - length(st) do write('O'); |
{групи нулями.} |
||
w r i t e ( a [ i ] ) ; |
|
{Виведення значення поточної групи.} |
|
end; |
|
|
|
end;
writeln;
Ефективність розбиття зменшуваного і від'ємника на групи по кілька цифр для виконання операції віднімання базується на тих самих причинах, що і при додаванні. Оскільки логіка побудови самого алгоритму віднімання не змінюється, лише дещо модифікуються ті фрагменти програми, де йде обробка груп цифр з урахуванням обраного типу (word або longint), то можна говорити про ефективність такого підходу до роботи з довгими числами.
Визначимося з коректним тестуванням алгоритму. Тесту вання можна почати з перевірки виконання алгоритму для двох невеликих і однакових за розрядністю чисел, перше з яких більше від другого, всі цифри яких відмінні від 0 і цифри відповідних розрядів першого числа більші від другого.
13
Наступною перевіркою може бути віднімання від числа 100...0 числа 1. Розрядність першого числа може бути досить великою, наприклад 100 цифр.
Перевірка коректності виконання операції віднімання чи сел 101 010 та 90 909 продемонструє правильність реалізації кількаразового віднімання більшої цифри від меншої.
Одним з останніх тестів може бути той, в якому використо вуються всі зазначені вище випадки для значно великих чисел.
Завдання
1.Розробити діалогову меню-орієнтовану програму віднімання цілих додатних чисел, використовуючи тип byte, і протесту вати її за такими критеріями:
-обидва числа однакової розрядності, що кратна числу 2, та різниця яких має таку саму розрядність;
-обидва числа однакової розрядності, що кратна числу 2, та різниця яких має більшу розрядність;
-розрядність першого числа більша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 2;
-розрядність першого числа більша від розрядності другого, але при цьому розрядність одного з них не кратна числу 2;
-розрядність першого числа менша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 2;
-розрядність першого числа менша від розрядності другого, але при цьому розрядність одного з них не кратна числу 2.
2.Розробити діалогову меню-орієнтовану програму відніман ня цілих додатних чисел, використовуючи тип word:
-обидва числа однакової розрядності, що кратна числу 4, та різниця яких має таку саму розрядність;
-обидва числа однакової розрядності, що кратна числу 4, та різниця яких має більшу розрядність;
-розрядність першого числа більша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 4;
-розрядність першого числа більша від розрядності другого, але при цьому розрядність одного з них не кратна числу 4;
-розрядність першого числа менша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 4;
-розрядність першого числа менша від розрядності дру гого, але при цьому розрядність одного з них не кратна чис лу 4.
3.Розробити діалогову меню-орієнтовану програму віднімання цілих додатних чисел, використовуючи тип longint:
-обидва числа однакової розрядності, що кратна числу 9, та різниця яких має таку саму розрядність;
14
-обидва числа однакової розрядності, що кратна числу 9, та різниця яких має більшу розрядність;
-розрядність першого числа більша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 9;
-розрядність першого числа більша від розрядності дру гого, але при цьому розрядність одного з них не кратна чис лу 9;
-розрядність першого числа менша від розрядності друго го, але при цьому розрядність обох чисел кратна числу 9;
-розрядність першого числа менша від розрядності другого, але при цьому розрядність одного з них не кратна числу 9.
4.Виконати завдання 1-3 для вхідних даних довжиною 32 000 цифр, згенерованих випадковим чином, що вводяться із файлу.
5.Зробити письмовий аналіз виконання завдань 1-4.
у |
Запитання для самоконтролю |
1.Опишіть алгоритм віднімання довгих цілих чисел, який виконує дії над окремими цифрами.
2.Як ввести початкові дані для виконання алгоритму віднімання? Запишіть процедуру введення мовою Pascal.
3.Запишіть фрагмент програми, який дає змогу вивести отрима ний результат віднімання двох довгих цілих чисел при обробці їх окремими цифрами.
4.Чи можна виконати віднімання двох довгих цілих чисел, розби ваючи їх на групи по кілька цифр і виконуючи дії віднімання над цими групами? Обґрунтуйте свою відповідь на конкретному прикладі.
5.Яким чином необхідно модифікувати процедуру віднімання ок ремих цифр для виконання цієї дії над групами цифр, використо вуючи тип змінних word?
6.Як вивести отриманий результат віднімання, якщо воно відбува лося розбиттям вхідної інформації на групи з використанням ти пу word?
7.Наведіть аргументи щодо ефективності виконання операції віднімання над двома довгими цілими числами, використовуючи розбиття їх цифр на групи.
Множення довгих цілих чисел
Наступною дією, яку логічно розглянути, є множення. З од ного боку, можна говорити про множення як про виконання певної кількості разів дії додавання. Але має право на існуван ня й алгоритм множення, який відомий усім ще з початкової ніколи, як множення двох чисел у стовпчик. Розглянемо його.
1. Нехай п - кількість цифр у першому числі, а т - у друго му. Визначити першим множником той, у якого розрядність більша: k = тах(п, т).
15