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

     

     

     

     

     

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

     

    Інформатика, програмування

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

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

    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.

    Це подання наштовхує на думку про масиві, представленому в табл. 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         

    3-й крок             

    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]             

    3         

    3274         

    58         

    1284     

    При виведенні "довгого" числа з масиву нам необхідно вивести 0058, інакше буде втрата цифр. Отже, незначущий нулі також необхідно виводити. Процедура виводу має вигляд:

    Procedure WriteLong (Const A: Tlong);

    Var ls, s: String; i: Integer;

    Begin

    Str (Osn Div 10, Is);

    Write (A [A [0]]; (виводимо старші цифри числа)

    For i : = A [0] - l DownTo 1 Do

    Begin

    Str (A [i], s);

    While Length (s)

    (доповнюємо незначущий нулями)

    Write (s)

    End;

    WriteLn

    End;

    Третє завдання. Попередня робота по опису способу зберігання, введення і виведення "довгих" чисел виконана.

    У нас є все необхідні "цеглинки", наприклад, для написання програми складання двох "довгих" позитивних чисел. Вихідні числа і результат зберігаємо у файлах. Назвемо процедуру складання SumLongTwo.

    Тоді програма введення двох "довгих" чисел та виведення результату їх складання буде мати такий вигляд:

    Var A, B, C: Tlong;

    Begin

    Assign (Input, 'Input.txt'); Reset (Input);

    ReadLong (A); ReadLong (B);

    Close (Input);

    SumLongTwo (A, B, C);

    Assign (Output, 'Output.txt');

    Rewrite (Output);

    WriteLong (C);

    Close (Output)

    End.

    Алгоритм процедури складання можна пояснити на простому прикладі. Нехай А = 870613029451, В = 3475912100517461.        

    i         

    A [i]         

    B [i]         

    C [1]         

    C [2]         

    C [3]         

    C [4]             

    1         

    9451         

    7461         

    6912         

    1         

    0         

    0             

    2         

    1302         

    51         

    6912         

    1354         

    0         

    0             

    3         

    8706         

    9121         

    6912         

    1354         

    7827         

    1             

    4         

    0         

    3475         

    6912         

    1354         

    7827         

    3476     

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

    Результат: С = 3476782713546912.

    Нижче наведено текст процедури складання двох "довгих" чисел.

    Procedure SumLongTwo (A, B: Nlong; Var C: Tlong);

    Var i, k: Integer;

    Begin

    FillChar (C, SizeOf (C), 0);

    If A [0]> B [0] Then k: = A [0] Else k: = B [0];

    For i: = l To k Do

    Begin З [i +1] : = (C [i] + A [i] + B [i]) Div Osn;

    C [i]: = (C [i] + A [i] + B [i]) Mod Osn

    (Чи є в цих операторах помилка?)

    End;

    If C [k + l] = 0 Then C [0]: = k Else C [0]: = k + l

    End;

    Четверта завдання. Реалізація операцій порівняння для "довгих" чисел (А = В, АВ, А = В).

    Function Eq (A, B: TLong): Boolean;

    Var i: Integer;

    Begin

    Eq: = False;

    If A [0] B [0] Then Exit

    Else Begin

    i: = l;

    While (i В також прозора.

    Function More (A, B: Tlong): Boolean;

    Var i: Integer;

    Begin If A [0]

    Else If A [0]> B [0] Then More: = True

    Else Begin

    i: = A [0];

    While (i > 0) And (A [i] = B [i]) Do Dec (i);

    If i = 0 Then More: = False

    Else If A [i]> B [i] Then More: = True

    Else More: = False

    End

    End;

    Решта функції реалізуються через функції Eq і More.

    Function Less (A, B: Tlong): Boolean; (A

    Begin

    Less: = Not (More (A, B) Or Eq (A, B))

    End;

    Function More_Eq (A, B: Tlong): Boolean; (A> = B)

    Begin

    More_Eq: = More (A, B) Or Eq (A, B)

    End;

    Function Less_Eq (A, B: Tlong): Boolean; (A B [0] + sdvig Then More: = 0

    Else

    If A [0]

    Else Begin

    i: = A [0];

    While (i> sdvig) And

    (A [i] = B [i-sdvig]) Do Dec (i);

    If i = sdvig Then Begin

    More: = 0;

    (збіг чисел з урахуванням зсуву)

    For i : = 1 To sdvig Do

    If A [i]> 0 Then Exit;

    More: = 2;

    (числа рівні, "хвіст" числа А дорівнює нулю)

    End

    Else More: = Byte (A [i]

    End

    End;

    П'ята задача. Множення довгого числа на коротке. Під коротким розуміється ціле число типу LongInt.

    Процедура дуже походить на процедуру складення двох довгих чисел.

    Procedure Mul (Const A: TLong; Const До: Longlnt; Var З: TLong);

    Var i: Integer;

    (результат - значення змінної С)

    Begin

    FillChar (С, SizeOf (С), 0);

    If K = 0 Then Inc (С [0]) (множення на нуль)

    Else Begin

    For i: = l To A [0] Do

    Begin

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

    C [i] : = (LongInt (A [i]) * K + C [i]) Mod Osn

    End;

    If C [A [0] +1]> 0 Then C [0]: = A [0] + 1

    Else C [0]: = A [0]

    (визначаємо довжину результату)

    End

    End;

    Шоста задача. Віднімання двох довгих чисел з урахуванням зсуву

    Якщо поняття зсуву поки не зрозуміло, то залиште його в спокої, насправді віднімання з урахуванням зсуву буде потрібно при реалізації операції ділення. На початку з'ясуйте логіку роботи процедури при нульовому зсуві.

    Введемо обмеження: число, з якого віднімають, більше числа, яке віднімається. Працювати з "довгими" негативними числами ми не вміємо.

    Процедура була б схожа на процедури додавання та множення, якби не одне "але" -- запозичення одиниці зі старшого розряду замість перенесення одиниці в старший розряд. Наприклад, у звичайній системі числення ми віднімаємо 9 з 11 - йде запозичення 1 з розряду десятків, а якщо з 10000 віднімаємо 9 - процес запозичення трохи складніше.

    Procedure Sub (Var A: TLong; Const B: TLong; Const sp: Integer);

    Var i, j: Integer;

    (з А віднімаємо В з урахуванням зсуву sp, результат віднімання в А)

    Begin

    For i: = l To B [0] Do

    Begin Dec (A [i + sp], B [i ]);

    j: = i ;{*}

    (реалізація складного запозичення)

    while (A [j + sp] <0) and (j Ost             

    8         

    9         

    504 = 63 * ((8 + 9) Div 2)         

    C     

    Отже, результат - Ціла частина приватного - рівний (Up + Down) Div 2, залишок від ділення - різниця між значеннями Ost і С. Нижню кордон (Down) змінюємо, якщо результат (С) менше залишку, верхню (Up), - якщо більше.

    Ускладнимо приклад. Нехай А одно 27856, а В - 354. Підставою системи числення є не 10, а 10000.        

    Down         

    Up         

    С         

    Ost = 27856             

    0         

    10000         

    1770000         

    C> Ost             

    0         

    5000         

    885000         

    C> Ost             

    0         

    2500         

    442500         

    C> Ost             

    0         

    1250         

    221250         

    C> Ost             

    0         

    625         

    110448         

    C> Ost             

    0         

    312         

    55224         

    C> Ost             

    0         

    156         

    27612         

    C             

    78         

    156         

    41418         

    C> Ost             

    78         

    117         

    34338         

    C> Ost             

    78         

    97         

    30798         

    C> Ost             

    78         

    87         

    29028         

    C> Ost             

    78         

    82         

    28320         

    C> Ost             

    78         

    80         

    27966         

    C> Ost             

    78         

    79         

    27612         

    C<   Ost     

    Ціла частина приватного дорівнює 78, залишок від ділення - 27856 мінус 27612, тобто 244.

    Пора приводити процедуру. Використовувані "цеглинки": функція порівняння чисел (More) з урахуванням зсуву і функція множення довгого числа на короткий (Mul) описані вище.

    Function FindBin (Var Ost: Tlong; Const В: TLong; Const sp: Integer): Longint;

    Var Down, Up: Word; C: TLong;

    Begin

    Down: = 0; Up : = 0sn;

    (основа системи числення)

    While Up - l> Down Do

    Begin

    (Є можливість викладачу зробити

    свідому помилку. Змінити умова

    циклу на Up> Down. Результат - зациклення програми.)

    Mul (В, (Up + Down) Div 2, С);

    Case More (Ost, C, sp) Of

    0: Down: = (Down + Up) Div 2;

    1: Up: = (Up + Down) Div 2;

    2: Begin Up: = (Up + Down) Div 2; Down: = Up End;

    End;

    End;

    Mul (B, (Up + Down) Div 2, C);

    If More (Ost, C, 0) = 0 Then Sub (Ost, C, sp)

    (знаходимо залишок від ділення)

    Else begin Sub (C, Ost, sp); Ost: = C end;

    FindBin: = (Up + Down) Div 2;

    (ціла частина приватного)

    End;

    Залишилось розібратися зі зрушенням, значенням змінної sp в нашому викладі. Знову повернемося до звичайної системі числення і спробуємо розділити, наприклад, 635 на 15. Що ми робимо? Спочатку ділимо 63 на 15 і формуємо, підбираємо в розумі першим цифру результату. Підбирати за допомогою комп'ютера ми навчилися. Підібрали - це цифра 4, і це старша цифра результату. Змінимо залишок. Якщо спочатку він був 635, то зараз став 35. Віднімати з урахуванням зсуву ми вміємо. Знову підбираємо цифру. Другу цифру результату. Це цифра 2 і залишок 5. Отже, результат (ціла частина) 42, залишок від ділення 5. А що зміниться, якщо підставою буде не 10, а 10000? Логіка співпадає, тільки в розумі вважати дещо важче, але ж у нас же є молоток під назвою комп'ютер - нехай він забиває цвяхи.

    Procedure MakeDel (Const А, В: TLong; Var Res, Ost: TLong);

    Var sp: Integer;

    Begin

    Ost: = A; (первинне значення залишку)

    sp: = А [0] - В [0];

    If More (А, В, sp) = l Then Dec (sp);

    (B * Osn> A, в результаті одна цифра)

    Res [0]: = sp + l;

    While sp> = 0 Do

    Begin

    (знаходимо чергову цифру результату)

    Res [sp + 1]: = FindBin (Ost, B, sp);

    Dec (sp)

    End

    End;

    Методичні рекомендації. Представлений матеріал викладається на чотирьох заняттях з відомою схемою: 10-15-хвилинне виклад ідей, а потім робота учнів під керівництвом викладача.

    1-е заняття. Введення, висновок і складання довгих чисел (завдання 1, 2, 3).

    2-е заняття. Функції порівняння (задача 4).

    3-е заняття. Множення і віднімання довгих чисел (завдання 5, 6).

    4-е заняття. Розподіл довгих чисел (завдання 7). Безумовно, ця схема не догма. Залежно від рівня підготовки учнів на самостійне виконання може бути винесена значна частина матеріалу. Зазначу тільки, що в силу традицією, що склалася в ряді випадків допускаються при викладі свідомі помилки. У результаті роботи кожен учень повинен мати власний модуль для роботи з "довгими" числами.

    Теми для досліджень

    1. Рішення задач: пошук найбільшого загального дільника двох "довгих" чисел; пошук найменшого спільного кратного двох "довгих" чисел; витяг квадратного кореня з "довгого" числа і т.д.

    2. "Довгі" числа можуть бути негативними. Як зміняться описані вище операції для цього випадку?

    3. Для зберігання "довгих" чисел використовується не масив, а стек, реалізований з допомогою списку. Змінити модуль роботи з "довгими" числами.

    Список літератури

    С.М. Окулов / "Довга" арифметика/

    Для підготовки даної роботи були використані матеріали з сайту http://www.comp-science.narod.ru/

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status