Материал: 1-23

2.Визначити і := 1.

3.Визначити / := 1, с := 0 (с - кількість десятків у множенні попереднього розряду).

4.Визначити ft := / + і - 1 - порядковий номер цифри-ре- зультату поточного множення.

5.Нехай at - і-та цифра першого множника, Ьі - другого, а хк - результату. Визначити хк := at* bt + с.

6.Якщо хк > 10, тоді визначити значення і-го розряду числарезультату як xk := <кількість одиниць числа хк> , а значення, яке необхідно буде додати у наступному розряді, - як с := <кількість десятків числа xh> і перейти до п. 8.

7.Якщо хк< 10, тоді визначити с := 0.

8.Якщо ;' < п, то j := j + 1 та перейти до п. 4.

9.Якщо с Ф 0, то k := k + 1, хк := с.

10.Визначити суму rezt := rezl+ xt.

11.Якщо і ^ т, то і := і + 1 та перейти до п. 3.

12.Вивести елементи масиву rez.

Які особливості наведеного алгоритму? Давайте розглянемо той крок алгоритму, де відбувається множення двох розрядів і виділення кількості одиниць і десятків для виконання мно­ ження наступного розряду заданих чисел. Чи не станеться тут якоїсь прикрості стосовно виходу отриманого результату за межі двозначного числа? Розглянемо спочатку найгірший ви­ падок, який може трапитися під час множення цифр наймен­ шого розряду: 9 * 9 = 81. Це означає, що найбільша цифра, яку нам доведеться додавати до результату множення у наступному розряді, це 8. Наступний найгірший випадок може статися, коли множаться найбільші цифри і з попереднього розряду переходить також найбільша цифра: 9 * 9 + 8 = 89. Отже, ми довели, що отримати більше від двозначного числа під час множення будь-якого розряду неможливо.

Оскільки більше ніяких особливостей наш алгоритм не перед­ бачає, то перейдемо до його реалізації мовою програмування:

procedure mult(var a: mas; b: mas; var n: word);

16

Наводити фрагменти програми, що реалізують введення і виведення інформації, немає сенсу, ОСКІЛЬКИ вони лишаються тими самими, що й у попередніх діях.

Під час ознайомлення з побудовою алгоритмів попередніх арифметичних дій ми обговорювали питання раціональності розбиття початкових даних на групи і виконання дій над ними. У випадку з алгоритмом множення при такому розбитті виника­ ють проблеми щодо перетворення типів, оскільки під час мно­ ження двох чисел типу word зі значенням 9999 (9999 * 9999 = = 99 980 001) отримуємо результат, який виходить за межі цьо­ го типу. Отже, можна говорити про розбиття вхідних даних на групи по 4 цифри, використовуючи при цьому тип longint. У та­ кому разі дещо зменшується обсяг вільної пам'яті комп'ютера, але економиться кількість виконуваних дій. Для дуже великих довгих чисел ця економія досить суттєва, оскільки кількість ви­ конання дій над числами зменшується вчетверо.

Зробимо такий опис масивів, що зберігатимуть вхідну та проміжну інформацію:

type mas = array[1..1000] of longint; Процедура виглядатиме так:

procedure mult(var a: mas; b: mas; var n: word); var k, i, j: word;

x, rez: mas; c, pr: longint; err: integer;

17

begin

if m > n then begin

k := m; m := n; n := k; x :=a; a :=b; b :=x end;

FillChar(rez, n + m, 0); i:=1;

while і <= m do begin c:=0;j:=1; FillChar(x, k, 0); while j <= n do

begin

k:=j + i - 1 ;

pr := a[j] * b[i] + C; {Визначення результату поточного множення.} if pr > 9999 {Якщо результат більший за максимальне чотиризначне число,}

{то визначення перевищення,} then begin с := pr div 10000; x[k] := pr mod 10000 end

{інакше запис результату на своє місце у масиві.} else begin x[k] := pr c := 0 end;

inc(j)

end;

if c <> 0 then begin inc(k); x[k] := c end; add(rez, x, k);

inc(i)

end;

n := k; a := rez end;

Процедури введення, виведення початкових даних і проце­ дура додавання двох довгих чисел, що використовуються під час множення, ті самі, що й у раніше розглянутих операціях.

Тестування алгоритму множення повинно передбачати всі можливі випадки: від простих до складних.

Одними із перших тестів можуть бути такі, що перевіряють множення будь-якого числа на 0 та на 1.

Наступний тест повинен перевірити реалізацію можливості збільшення розрядності добутку, наприклад перше число 9999, а друге 2.

Далі можна перевірити коректність множення на число, розрядність якого більша за 1. Прикладом таких чисел може бути 123 та 11. Цікавою також є перевірка отримання резуль­ тату множення будь-якого числа, наприклад, на 1 000 000.

Простим здається множення, наприклад, 123 на 10 000 001, але насправді така перевірка виявляється корисною.

Для завершення тестування невеликих чисел можна піді­ брати тест, що враховує всі попередні випадки.

18

Обов'язковою є перевірка випадку, коли перший множник менший від другого, а також множення досить великих чисел за схемою тестування, визначеною вище.

Завдання

1.Розробити діалогову меню-орієнтовану програму множення цілих додатних чисел, використовуючи тип byte, і протесту­ вати її за такими критеріями:

-обидва числа однакової розрядності, що кратна числу 2, та добуток яких має таку саму розрядність;

-обидва числа однакової розрядності, що кратна числу 2, та добуток яких має більшу розрядність;

-розрядність першого числа більша від розрядності друго­ го, але при цьому розрядність обох чисел кратна числу 2;

-розрядність першого числа більша від розрядності дру­ гого, але при цьому розрядність одного з них не кратна числу 2;

-розрядність першого числа менша від розрядності друго­ го, але при цьому розрядність обох чисел кратна числу 2;

-розрядність першого числа менша від розрядності друго­ го, але при цьому розрядність одного з них не кратна чис­ лу 2.

2.Розробити діалогову меню-орієнтовану програму множення цілих додатних чисел, використовуючи тип longint:

-обидва числа однакової розрядності, що кратна числу 4, та добуток яких має таку саму розрядність;

-обидва числа однакової розрядності, що кратна числу 4, та добуток яких має більшу розрядність;

-розрядність першого числа більша від розрядності друго­ го, але при цьому розрядність обох чисел кратна числу 4;

-розрядність першого числа більша від розрядності дру­ гого, але при цьому розрядність одного з них не кратна числу 4;

-розрядність першого числа менша від розрядності друго­ го, але при цьому розрядність обох чисел кратна числу 4;

-розрядність першого числа менша від розрядності друго­ го, але при цьому розрядність одного з них не кратна чис­ лу 4.

3.Виконати завдання 1-2 для вхідних даних довжиною 32 000 цифр, згенерованих випадковим чином, що вводяться із файлу.

4.Зробити письмовий аналіз виконання завдань 1-3.

19